朝花夕拾
+Wiki
| 指标 | 平均 | 最差 |
|---|---|---|
| 空间 | \(O(n)\) | \(O(n)\) |
| 搜索 | \(O(log n)\) | \(O(log n)\) |
| 插入 | \(O(log n)\) | \(O(log n)\) |
| 删除 | \(O(log n)\) | \(O(log n)\) |
AVL树是一种自平衡搜索二叉树。在AVL树中，任何节点的两个子树的高度最多相差一个，当高度差超过一个时就要进行重新平衡。对于查找密集型应用，AVL树比红黑树更快，因为其更严格的平衡。其名字是由两位发明人的名字首字母而来。
平衡因子
在二叉树中，节点 \(X\) 的平衡因子 \(BF(X)\) 等于右子树最大高度减左子树最大高度。所以AVL树的平衡因子 \(BF(X) \in {\{-1,0,1\}}\)。
左子树比右子树高成为左倾。右子树比左子树高成为右倾。左右子树高度一致才是平衡。
操作
AVL树的搜索与传统二叉树一致。但是修改操作要附带平衡操作。