什么是红黑树


一.红黑树介绍

1.二叉查找树介绍
在介绍红黑树之前我们要先理解二叉查找树的数据结构。下面简单介绍一下。


上面这张图就是一个二叉查找树。二叉查找树有如下几条特性

(1).左子树上所有结点的值均小于或等于它的根结点的值。

(2).右子树上所有结点的值均大于或等于它的根结点的值。

(3).左、右子树也分别为二叉排序树

那既然他名字中是有“查找”的,那么他是怎么查找的呢?比如我们要查找10这个元素,查找过程为:首先找到根节点,然后根据二叉查找树的第一二条特性,我们知道要查找的10>9所以是在根节点的右边去查找,找到13,10<13,所以接着在13的左边找,找到11,10<11,继续在11的左边查找,这样就找到了10.这其实就是二分查找的思想。最后我们要查出结果所需的最大次数就是二叉树的高度!(二分查找的思想:找到数组的中间位置的元素v,将数组分成>v和<v两部分,然后将v和要查找的数据进行一个比较,如果大于v那么就在>v的部分再次进行二分查找,否则就在<v的部分进行二分查找,直到找到对应的元素。)

那既然要查出结果所需的最大次数就是二叉树的高度,那这个高度会不会有时候很长呢?

比如我们依次插入 根节点为9如下五个节点:7,6,5,4,3。依照二叉查找树的特性,结果会变成什么样呢?7,6,5,4,3一个比一个小,那么就会成一条直线,也就是成为了线性的查询,时间复杂度变成了O(N)级别。为了解决这种情况,该红黑树出场了。

2.红黑树介绍
红黑树其实就是一种自平衡的二叉查找树。他这个自平衡的特性就是对HashMap中链表可能会很长做出的优化。

红黑树是每个节点都带有颜色属性的二叉查找树,颜色或红色或黑色。在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求:

性质1. 节点是红色或黑色。

性质2. 根节点是黑色。

性质3 每个叶节点(NIL节点,空节点)是黑色的。

性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

下面这棵树就是一个典型的红黑树


红黑树那么多规则,那么在插入和删除元素会不会破坏红黑树的规则呢?什么情况下会破坏?什么情况下不会?

比如我们向原红黑树插入为14的新节点就不会破坏规则


向原红黑树插入值为21的新节点就破坏了规则


那么红黑树是怎么维护这个二叉查找树的自平衡性的呢?

红黑树通过“变色”和“旋转”来维护红黑树的规则,变色就是让黑的变成红的,红的变成黑的,旋转又分为“左旋转”和“右旋转”。这个比较复杂,容易晕,我们就只要知道红黑树就是通过这种方式来实现它的自平衡性就行了。

总结一下应该是 1. 当出现新的节点时默认为红色插入,如果其父节点为红色,则对其递归向上换色,如果根节点由此变为红色,则对根节点进行左旋(右侧过深)或右旋(左侧过深),之后从根节点向下修改颜色 2. 从根节点检查红色节点是否符合路径上的黑色节点数量一致,如果不一致,对该节点进行左旋(右侧黑色节点数量更多)或右旋(左侧黑色节点数量更多),并变换颜色,重复2操作直到符合红黑树规则。

声明:半夏有你|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 什么是红黑树


年轻的心,是被梦想撑大的