平衡二叉树和红黑树最差情况性能分析_红黑树最大高度差

平衡二叉树和红黑树最差情况分析

1.经典平衡二叉树

平衡二叉树（又称AVL树）是带有平衡条件的二叉查找树，使用最多的定理为：一棵平衡二叉树是其每个节点的左子树和右子树的高度最多差为1的二叉查找树。因为他是二叉树的一种具体应用，所以他同样具有二叉树的性质。例如，一棵满二叉树在第k层最多可拥有个节点（性质1）。一棵树的高度为其从根节点到最底层节点经过的路径数（例如只含一个节点的树的高度为0）（性质2）。并且已被证明，一棵含有N个节点的平衡二叉树的高度最多（粗略来说）为。下面我们来尝试总结如何得到一个高度差最大的平衡二叉树（查找性能最差）。

由平衡二叉树的定义可知，左子树和右子树最多可以相差1层高度，那么多个在同一层的子树就可以依次以相差1层的方式来递减子树的高度，如下图所示是一个拥有4棵子树的树的层高最大差情形（图1）：

图1 拥有4颗子树的平衡二叉树最大高度差

该图虚线框中的子树，最左端的节点树高度为0，最右端的节点树的高度为2，因此该平衡二叉树的内部子树最大高度差为2。

利用这样的性质，我们就可以依次递推&#x