平衡二叉树

平衡二叉树的背景

由于一些众所周知的原因, 我们选择了平衡二叉树, 好吧, 其实就是因为对二叉搜索树的限制太少了, 导致在一些特殊的情况下, 二叉搜索树不太听话, 查找, 插入与删除的时间均变成了 \(O(n)\) 也可以认为, 熵增就会更加有序, 熵减就会更加自由, 这里我们追求的是有序的查找, 但是啊, 年轻人, 为了自由而战吧.

平衡二叉树的定义

1. 平衡二叉树首先满足二叉搜索树的特征: 对于任何一颗子树的根结点而言, 它的左子树任何节点的key一定比root小, 而右子树任何节点的key 一定比root大.
2. 对于AVL树而言, 其中任何子树仍然是AVL树;
3. 每个节点的左右子节点的高度之差的绝对值最多为1(平衡特性);

显然, 由于上述第三点的限制, 很容易计算出它的查找时间为 \(O(log\ n)\). 它的最坏的情况也很容易计算与模拟, 最坏的情况如下:
假设树的高度为 \(h\), 节点的个数为 \(n\), 平衡二叉树最坏的情况如下, 我们再补充 \(n\) 个节点, 将这棵树变成一个满二叉树, 那么.