红黑树算法原理

红黑树算法原理

什么是红黑树?

  红黑树是一种自平衡二叉查找树,是计算机科学领域中的一种数据结构,典型的用途是实现关联数组,存储有序的数据。它是在1972年由Rudolf Bayer发明的,别称”对称二叉B树”,它现代的名字由 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的。它可以在O(logn)时间内做查找,插入和删除,这里的n是树的结点个数。

  红黑树和平衡二叉树(AVL树)都是二叉查找树的变体,但红黑树的统计性能要好于AVL树。因为,AVL树是严格维持平衡的,红黑树是黑平衡的。维持平衡需要额外的操作,这就加大了数据结构的时间复杂度,所以红黑树可以看作是二叉搜索树和AVL树的一个折中,维持平衡的同时也不需要花太多时间维护数据结构的性质。红黑树在很多地方都有应用,例如:

  • C++的STL,map和set都是用红黑树实现的。
  • 著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块。
  • epoll在内核中的实现,用红黑树管理事件块。
  • nginx用红黑树管理timer等。
  • Java的TreeMap实现。

红黑树简介:

  R-B Tree,全称是Red-Black Tree,又称为“红黑树”,是一种特殊的二叉查找树。红黑树的每个结点上都有存储位表示结点的颜色,可以是红(Red)或黑(Black)。

红黑树的特性:

  1. 每个结点是黑色或者红色。
  2. 根结点是黑色。
  3. 每个叶子结点(NIL)是黑色。 [注意:这里叶子结点,是指为空(NIL或NULL)的叶子结点!]
  4. 如果一个结点是红色的,则它的子结点必须是黑色的。
  5. 每个结点到叶子结点NIL所经过的黑色结点的个数一样的。[确保没有一条路径会比其他路径长出俩倍,所以红黑树是相对接近平衡的二叉树的!]

红黑树的基本操作是添加、删除。在对红黑树进行添加或删除之后,都会用到旋转方法。为什么呢?道理很简单,添加或删除红黑树中的结点之后,红黑树的结构就发生了变化,可能不满足红黑树的5条性质,也就不再是一颗红黑树了,而是一颗普通的树。而通过旋转和变色,可以使这颗树重新成为红黑树。简单点说,旋转和变色的目的是让树保持红黑树的特性:自平衡二叉树。
旋转包括两种:左旋 和 右旋。下面分别对它们进行介绍:

左旋:以某个结点作为支点(旋转结点),其右子结点变为旋转结点的父结点,右子结点的子结点变为旋转结点的右子结点,其左子结点保持不变。如图2。

右旋:以某个结点作为支点(旋转结点),其左子结点变为旋转结点的父结点,左子结点的子结点变为旋转结点的左子结点,其右子结点保持不变。如图3。

变色:结点的颜色由红变黑或由黑变红。

详细参见截图

感谢这位娜娜姐为我们CSer提供帮助,非常感激。如有侵权行为,请联系删除。

Leave a reply

Your email address will not be published.

You may use these HTML tags and attributes:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>