适度平衡树,是指将树高限制为“渐进地不超过 O(logn)”。
举例:
- AVL 树:兄弟节点的高度之差不超过 1(≤1)
- 伸展树;
- 红黑树;
- kd-树;
当然这些都可以归入平衡二叉搜索树(BBST,Balanced Binary Search Tree)之列。
1. 旋转调整
最基本的修复手段(使适度平衡),就是将围绕特定点的旋转,实现(中序遍历)等价前提下的拓扑调整。
- zig 和 zag
zig 和 zag 旋转均属局部操作,仅涉及常数个节点及其之间的连接关系,故均可在常数时间内完成。正因如此,在此后的众多实现二叉搜索树平衡化算法时,它们都是支撑性的基本操作。
就与树相关的指标而言,经一次 zig 或 zag 旋转之后:
- 节点 v 的深度加 1;
- 节点 c 的深度减 1;
这一局部子树(乃至全树)的高度可能发生变化,但上下幅度均不超过 1 层;
2. AVL 树
通过合理设定适度平衡的标准,并借助以上等价变换,AVL 树(AVL tree)可以实现近乎理想的平衡。在渐进意义下,AVL 树可始终将其高度控制在 O(logn) 以内,从而保证每次查找、插入或删除操作,均可在 O(logn)。
从平衡因子(balance factor)的角度来看 AVL 树。任一节点 v 的平衡因子定义为“其左、右子树的高度差”(显然可以为负)。
因此,从平衡因子的角度说,AVL 树是平衡因子受限(|bf|≤1⇒ bf = -1, 0, 1)的二叉搜索树(BST)⇒ AVL 继承自 BST。