Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

Vinllen Chen


To be a better coder

红黑树和AVL树的个人总结

  以前一直想好好看看红黑树,但看着看着认为这种实现的东西直接调别人的包就可以了,我只要知道大概的时间空间复杂度就ok了。好吧,我承认我理解肤浅了,今天没啥事就把红黑树好好复习了一下。
  红黑树(RB-Tree)用途真是太广了,Linux内核,STL中的关联容器,nginx的实现……太多地方用到了。目前的AVL树已经快走入博物馆了,红黑树开始在历史舞台上发挥光和热了。好吧,废话扯多了。move on!

二叉搜索树

  首先回顾一下平衡二叉搜索树的祖先:二叉搜索树。它具有以下性质:

  • 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  • 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
  • 它的左、右子树也分别为二叉搜索树。

  它的优点我就不说了,缺点就是可能导致不平衡:某一边的子树高度远远大于另外一边的子树。这样在插入,删除,查找时最坏情况的复杂度达到了O(n)。
  由于它存在的缺点,诞生了平衡二叉搜索树,其实所谓的树形平衡与否,并没有一个绝对的测量标准。“平衡“的大概意义就是:没有任何一个节点过深。目前平衡二叉树有很多版本,比较有名的就是AVL书和红黑树,另外还有一些性能较好的树,但是代码实现复杂度比较高,所以没有流行开来。

AVL树

  来讲讲AVL树:它是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。
  节点的平衡因子是它的左子树的高度减去它的右子树的高度(有时相反)。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的,并需要重新平衡这个树。平衡因子可以直接存储在每个节点中,或从可能存储在节点中的子树高度计算出来.

插入操作

  插入分为以下四种:

  • 插入点位于X的左子节点的左子树--左左
  • 插入点位于X的左子节点的右子树--左右
  • 插入点位于X的右子节点的左子树--右左
  • 插入点位于X的右子节点的右子树--右右

  情况1,4彼此对称,称为外侧插入,可以采用单旋转操作调整解决:比如左左采用右旋。情况2,3彼此对称,称为内测插入,可以采用两次旋转操作调整解决:比如左右可以采用先左旋再右旋。

删除操作

  删除分为以下三种:

  • 叶子节点删除。如果删除该叶子节点影响高度,进行左右旋转调整,否则直接删除。
  • 只有一个儿子节点。直接删除,并将父节点的儿子指针指向该删除节点的儿子。并进行旋转调整。
  • 具有两个儿子节点。这种情况稍微复杂一点,寻找当前节点的中序遍历后继节点:即右子树中最小的节点。将该节点替换当前节点,并进行调整。

红黑树

  红黑树的性质如下:

  • 每个节点或是红的,或是黑的。
  • 根节点为黑的
  • 每个叶节点是黑的。
  • 如果一个节点是红的,则它的两个儿子都是黑的
  • 对每个节点,从该节点到其子孙节点的所有路径包含相同书目的黑节点

  红黑树的旋转操作与普通平衡二叉搜索树一致。由于前面5条条件限制,插入,删除节点时都得遵循这些条件。具体算法我就不分析了,大家可以参考《算法导论》或维基百科

插入操作

  插入之后,新节点颜色为红,如果违背以上条件则进行调整,调整过程为迭代。

删除操作

  同样删除操作也是,删除之后进行调整,使最后满足以上条件。

算法比较

  • 总体上来说,两者在删除和插入的复杂度一致,都为O(log n)。
  • AVL树的高度在~1.44log(n)级别,而红黑树的高度在~2log(n)级别。但是在插入之后旋转调整,AVL的复杂度在O(log n),即多次旋转。而红黑树调整的级别在O(1),因为其能保证在三次旋转之内达到稳定。
  • 相比较而言,因为树的高度的关系,红黑树适用于插入删除频繁,AVL树适用于查找频繁。但其实红黑树应用比AVL广很多。

About the author

vinllen chen

Beijing, China

格物致知


Discussions

comments powered by Disqus