这是本文档旧的修订版!
未完待续..(例题代码什么的再补)
如果树中节点的数量为 n,则一棵满足O($log_2{n}$) 渐进运行时间的树的高度应接近于比$log_2{n}$小的最大整数。
对于一棵二叉查找树,往往不能事先知道所有的数据从而并不能保证树的形状合适,例如在不断输入数据并且不断查询的情况下。
如果我们能实时调整树使其满足最高效率的形状就好了。为此我们有自平衡二叉查找树。
有多种自平衡结构,如AVL树、红黑树、2-3树、2-3-4树、伸展树、B树等等。
首先是节点具有颜色:红、黑二色;其次是存在一种NIL节点,作为伪叶子节点连接着内点。 满足性质:
按照BST的插入方式在计算出的位置插入一个红节点。设该节点为K,父节点为P,P父节点为G,P的兄弟节点为S。
1.若P为黑色,则符合红黑树的性质,不需要做改动。
2.若P为红色:
$\quad\quad $2a.若S是黑色或为空,则需要进行旋转,分为四种情况,前两种情况是P是G的左孩子,后两种情况为P是右孩子。
$\quad\quad $2b.若S是红色,则需要对P、S、G重新着色:将P和S着色为黑色,将G着色为红色。
这样的重新着色不会影响G及以下的性质,但可能出现G与其父节点同红的情况,此时需要遵循上述方式向上递归地进行调整。
对于每一个节点,其左右子树的高度差不超过1。
按照二叉查找树