初识红黑树
网站首页 文章专栏 初识红黑树
初识红黑树
编辑时间:2019-05-06 18:10 作者:毛毛小妖 浏览量:129 评论数:0

    学过数据结构的人都知道红黑树这个东东,可是一提起它,很多人都头疼,因为太难懂了,特别是那五条性质,还有旋转啊、插入啊、删除啊这些操作。相信没几个人能真正看完的,因为看完之后整个人都不好了。红黑树因为其性能十分优秀,现在很多的底层实现都是红黑树了。本文就带大家来一步一步了解一下这个神奇的东东。

    红黑树的起源自然是二叉树了,二叉树就不说了,我们都很熟悉,无非就是以根节点为中心,左边的节点小于根节点,右边的节点大于根节点,所以它是一种非常好的数据结构,查找起来非常方便。但是经常会出现偏向一侧的问题,这样子查找起来性能就不行了。比如下图这样,就跟链表没啥区别了:

这个时候,平衡二叉树就出现了。其每个节点对应的左子树和右子树的树高度差不超过1,如下图:

红黑树就是一种平衡二叉树。理解平衡二叉树之前先来了解一下2-3树吧,因为红黑树其实就是2-3树的变形,而2-3树是二叉查找树的变形。树中的2和3代表两种节点,以下表示为2-节点和3-节点。
2-节点即普通节点:包含一个元素,两条子链接。
3-节点则包含2个元素和三条链接:两个元素A、B,左边的链接指向小于A的节点,中间的链接指向介于A、B值之间的节点,右边的链接指向大于B的节点。


在这两种节点的配合下,2-3树可以保证在插入值过程中,任意叶子节点到根节点的距离都是相同的。下面来看2-3树的构造过程:
如果将值插入一个2-节点,则将2-节点扩充为一个3-节点。
如果将值插入一个3-节点,分为以下几种情况。

1>3-节点没有父节点,即整棵树就只有它一个三节点。此时,将3-节点扩充为一个4-节点,即包含三个元素的节点,然后将其分解,变成一棵二叉树。

2>3-节点有一个2-节点的父节点,此时的操作是,3-节点扩充为4-节点,然后分解4-节点,然后将分解后的新树的父节点融入到2-节点的父节点中去。

3>3-节点有一个3-节点的父节点,此时操作是:3-节点扩充为4-节点,然后分解4-节点,新树父节点向上融合,上面的3-节点继续扩充,融合,分解,新树继续向上融合,直到父节点为2-节点为止,如果向上到根节点都是3-节点,将根节点扩充为4-节点,然后分解为新树,至此,整个树增加一层,仍然保持平衡。

从上面描述来看,2-3树的代码实现要考虑的情况比较多。所以红黑树出现了,因为红黑树利用红色和黑色来标记节点,代码实现起来就比较简单了。

红黑树中,所有的节点都是标准的2-节点,为了体现出3-节点,这里将3-节点的两个元素用左斜红色的链接连接起来,即连接了两个2-节点来表示一个3-节点。这里红色节点标记就代表指向其的链接是红链接,黑色标记的节点就是普通的节点。所以才会有那样一条定义,叫“从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点”,因为红色节点是可以与其父节点合并为一个3-节点的,红黑树实现的其实是一个完美的黑色平衡,如果你将红黑树中所有的红色链接放平,那么它所有的叶子节点到根节点的距离都是相同的。所以它并不是一个严格的平衡二叉树,但是它的综合性能已经很优秀了。

红链接放平:

 所以,红黑树还可以这样描述:
(1)红链接均为左链接。
(2)没有任何一个结点同时和两条红链接相连。
(3)该树是完美黑色平衡的,即任意空链接到根结点的路径上的黑链接数量相同。

推荐文章
来说两句吧
最新评论
    还没有人评论哦,快来坐沙发吧!