用 Rust 实现一个 AVL 树
什么是 AVL 树以及 AVL 树的一些原理就不介绍了,我们直接讲如何用 Rust 来实现它。
结构体及 trait 定义
参考一般 AVL 树的实现,我定义了一个结构体 TreeNode
以及一个类型别名 AvlTreeNode
:
pub type AvlTreeNode<T> = Option<Box<TreeNode<T>>>;
#[derive(Clone, Debug)]
pub struct TreeNode<T: PartialOrd> {
val: T,
height: i32,
left: AvlTreeNode<T>,
right: AvlTreeNode<T>,
}
使用类型别名可以了少打几个字母以及好看一点。
还定义了一个 trait AvlTree
:
pub trait AvlTree<T: PartialOrd> {
fn new(val: T) -> Self;
fn height(&self) -> i32;
fn insert(&mut self, val: T);
fn delete(&mut self, val: T) -> Self;
}