AVL树

朝花夕拾

+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树的搜索与传统二叉树一致。但是修改操作要附带平衡操作。