红黑树的理解

╰半夏微凉° 2022-06-17 05:25 218阅读 0赞

在JDK8中,为了防止HashMap出现最坏的情况

如果某个桶中的记录过 大的话（当前是TREEIFY\_THRESHOLD = 8），HashMap会动态的使用一个专门的treemap实现来替换掉它。这样做的结果会更好，是O(logn)，而不是糟糕的O(n)。它是如何工作 的？前面产生冲突的那些KEY对应的记录只是简单的追加到一个链表后面，这些记录只能通过遍历来进行查找。但是超过这个阈值后HashMap开始将列表升 级成一个二叉树，使用哈希值作为树的分支变量，如果两个哈希值不等，但指向同一个桶的话，较大的那个会插入到右子树里。如果哈希值相等，HashMap希 望key值最好是实现了Comparable接口的，这样它可以按照顺序来进行插入。这对HashMap的key来说并不是必须的，不过如果实现了当然最 好。如果没有实现这个接口，在出现严重的哈希碰撞的时候，你就并别指望能获得性能提升了。

这个性能提升有什么用处？比方说恶意的程序，如果它知道我们用的是哈希算法，它可能会发送大量的请求，导致产生严重的哈希碰撞。然后不停的访问这些 key就能显著的影响服务器的性能，这样就形成了一次拒绝服务攻击（DoS）。JDK 8中从O(n)到O(logn)的飞跃，可以有效地防止类似的攻击

以上这段转载自http://www.cnblogs.com/interdrp/p/3706056.html

下面这段转载自 http://blog.csdn.net/very\_2/article/details/5722682

红黑树是二叉查找树的一种，它每个结点都被标上了颜色（红色或黑色），红黑树满足以下5个性质：

**1、 每个结点的颜色只能是红色或黑色。**

**2、 根结点是黑色的。**

**3、 每个叶子结点都带有两个空的黑色结点（被称为黑哨兵），如果一个结点n的只有一个左孩子，那么n的右孩子是一个黑哨兵；如果结点n只有一个右孩子，那么n的左孩子是一个黑哨兵。**

**4、 如果一个结点是红的，则它的两个儿子都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。**

**5、 对于每个结点来说，从该结点到其子孙叶结点的所有路径上包含相同数目的黑结点。**

红黑树的这5个性质中，第3点是比较难理解的，但它却非常有必要。我们看图1中的左边这张图，如果不使用黑哨兵，它完全满足红黑树性质，结点50到两个叶结点8和叶结点82路径上的黑色结点数都为2个。但如果加入黑哨兵后（如图1右图中的小黑圆点），叶结点的个数变为8个黑哨兵，根结点50到这8个叶结点路径上的黑高度就不一样了，所以它并不是一棵红黑树。

![rb01.jpg][]

上面这张图就是想解释第3点性质的作用,假如说，没有第3点的话,光看左图,是满足第5点性质的,但是这样的树结构是不合红黑树的实际要求的,所以加了第3点性质,来规范红黑树

## 红黑树上结点的插入 ##

在讨论红黑树的插入操作之前必须要明白，任何一个即将插入的新结点的初始颜色都为红色。这一点很容易理解，因为插入黑点会增加某条路径上黑结点的数目，从而导致整棵树黑高度的不平衡。但如果新结点父结点为红色时（如图2所示），将会违返红黑树性质：一条路径上不能出现相邻的两个红色结点。这时就需要通过一系列操作来使红黑树保持平衡。

![rb02.jpg][]

下面这些图引自于http://blog.csdn.net/v\_JULY\_v/article/details/6105630

![1355319681_6107.png][]

当插入或删除节点,这时红黑树的性质有可能被破坏,所以要重新对节点进行着色与旋转操作(旋转操作其实就是改变指针的指向)

旋转有左旋与右转,

1.左旋

![8394323_1293614183gD0H.jpg][]

上图其实是Y节点进行左旋操作，即向左移动，由红黑树左小右大的性质可知，当Y节点向左移动时，取代pivot成为该子树的根节点，而pivot成为Y的左节点(因为Y本来就比pivot节点大),Y原先的右节点C保持不变,那Y原先的b节点呢？要放在哪？如果是Y-b-pivot这样的结构呢？这样的结构有个问题就是pivot是b的左节点还是右节点？因为这样的结构下,b只有pivot这一个节点,所以还是如上图那样,b成为了pivot的右节点(表示比pivot大)

2.右旋

![8394323_1293614183DSC3.jpg][]

同样的,Y节点向右移动

还有种叫双旋,无非就是先左旋再右旋或者先右旋再左旋

左旋右旋的原理知道了,那什么时候该进行左旋右旋，什么时候不用进行?

下面这段话引自 http://www.cnblogs.com/abatei/archive/2008/11/17/1335031.htm

每插入一个结点后，首先检查是否破坏了树的平衡性，如果因插入结点而破坏了二叉查找树的平衡，则找出离插入点最近的不平衡结点，然后将该不平衡结点为根的子树进行旋转操作，我们称该不平衡结点为旋转根，以该旋转根为根的子树称为最小不平衡子树,怎么判断哪个结点是最不平衡结点?

AVL树中的每个结点都有一个平衡因子（balance factor，以下用BF表示），它表示这个结点的左、右子树的高度差，也就是左子树的高度减去右子树的高度的结果值。AVL树上所有结点的BF值只能是\-1、0、1。反之，只要二叉树上一个结点的BF的绝对值大于1，则该二叉树就不是平衡二叉树

虽然红黑树不是AVL树，但我觉得也可以用这套理论来理解,只要是红黑树上,这个结点的左树减右树的高度差的绝对值大于1,这个节点就是不平衡结点,就要进行旋转操作

我刚才看到一段话,通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其它路径长出俩倍，就在想，要是某个子树的节点全都是黑色的呢？又想到这是不可能的，因为所有新生节点都是红色的（除了根节点），我想，又为了防止某个子树的节点全都是红色的，所以才加了红节点的子节点不能是红色这个要求，因为有了这个要求，红节点才有变成黑色节点的可能（重新着色）

为了清楚地表示插入操作以下在结点中使用“新”字表示一个新插入的结点；使用“父”字表示新插入点的父结点；使用“叔”字表示“父”结点的兄弟结点；使用“祖”字表示“父”结点的父结点。插入操作分为以下几种情况：

**1、黑父**

如图3所示，如果新点的父结点为黑色结点，那么插入一个红点将不会影响红黑树的平衡，此时插入操作完成。红黑树比AVL树优秀的地方之一在于黑父的情况比较常见，从而使红黑树需要旋转的几率相对AVL树来说会少一些。

![rb03.jpg][]

**2．红父**

如果新点的父结点为红色，这时就需要进行一系列操作以保证整棵树红黑性质。如图3所示，由于父结点为红色，此时可以判定，祖父结点必定为黑色。这时需要**根据叔父结点的颜色来决定做什么样的操作**。青色结点表示颜色未知。由于有可能需要根结点到新点的路径上进行多次旋转操作，而每次进行不平衡判断的起始点（我们可将其视为新点）都不一样。所以我们在此使用一个蓝色箭头指向这个起始点，并称之为判定点。

![rb03-1.jpg][]

**2.1 红叔**

当叔父结点为红色时，如图4所示，无需进行旋转操作，只要将父和叔结点变为黑色，将祖父结点变为红色即可。但由于祖父结点的父结点有可能为红色，从而违反红黑树性质。此时必须将祖父结点作为新的判定点继续向上进行平衡操作。

![rb04.jpg][]

需要注意，无论“父”在“叔”的左边还是右边，无论“新”是“父”的左孩子还是右孩子，它们的操作都完全一样。

**2.2 黑叔**

当叔父结点为黑色时，需要进行旋转，以下图示了所有的旋转可能

这就是为什么要考虑叔父结果颜色的原因了,因为叔父结点是黑色的话，你再改变原来父节点的颜色，就会产生我们上面说的不平衡结点,因为原本父节点是红色的，现在要重新着色成黑色，那就意味着父节点这边的子树多了父节点这一个黑结点，那就打破平衡了

**LL意思是新节点插在根节点的左孩子树的左子树里,RR,LR,RL同样道理**

情形1：直接右旋再重新着色

![rb05.jpg][]

情形2：先左旋再右旋然后重新着色,先左旋就变成情况1那样子,然后像情况1那样右旋就好了

![rb06.jpg][]

情形3：左旋再重新着色

![rb07.jpg][]

情形4：先右旋再左旋，然后重新着色,

![rb08.jpg][]

可以观察到，当旋转完成后，新的旋转根全部为黑色，此时不需要再向上回溯进行平衡操作，插入操作完成。需要注意，上面四张图的“叔”、“1”、“2”、“3”结点有可能为黑哨兵结点。

其实红黑树的插入操作不是很难，甚至比AVL树的插入操作还更简单些。但删除操作就远远比AVL树复杂得多，下面就介绍红黑树的删除操作。

先了解下二叉树的几个名词 先序 中序 后序 前驱 后继

树的遍历的三种情况，是根据左子树、右子树、根这3者的不同访问次序来定义的。

根左右（根先访问），则为先序遍历

左根右，则为中序遍历；

左右根，则为后序遍历

例如：求下面树的三种遍历

![Center][]

前序遍历：abdefgc

中序遍历：debgfac

后序遍历：edgfbca

拿中序来讲,为什么中序遍历的顺序是debgfac,我们要将上图分成几部分来看就理解了,首先 d-e是一个子树 g-f是一个子树，e-d-b-f-g是一个子树,因为中序是先从左子树取然后就是根然后才轮到右子树,d-e这个子树是整个大树中最左的,所以先从这取起,因为d-e没有左树，所以先从d这个根取起,de,然后从e-d-b-f-g这个子树来讲,左边的子树d-e已经取了，轮到根了,那就是b，所以就是deb,然后根取完了,就轮到右边这个子树了,在右边子树g-f中，g是左子树,所以先取,那就是debg了,然后左子树取完取中，即f,那就是debgf,之后的逻辑就是这样推了

前驱结点：节点val值小于该节点val值并且值最大的节点   
后继节点：节点val值大于该节点val值并且值最小的节点

回归到红黑树的删除操作

在二叉查找树中删除一个给定的结点p有三种情况

(1)  结点p无左右子树，则直接删除该结点，修改父节点相应指针

(2)  结点p有左子树（右子树），则把p的左子树（右子树）接到p的父节点上

(3)  左右子树同时存在，则有三种处理方式

a.      找到结点p的中序直接前驱结点s，把结点s的数据转移到结点p，然后删除结点s，由于结点s为p的左子树中最右的结点，因而s无右子树，删除结点s可以归结到情况(2)。严蔚敏[数据结构][Link 1]P230-231就是该处理方式。

b.     找到结点p的中序直接后继结点s，把结点s的数据转移到结点p，然后删除结点s，由于结点s为p的右子树总最左的结点，因而s无左子树，删除结点s可以归结到情况(2)。[算法][Link 1]导论第2版P156-157该是该处理方式。

c.      找到p的中序直接前驱s，将p的左子树接到父节点上，将p的右子树接到s的右子树上，然后删除结点p。

![Center 1][]

[rb01.jpg]: /images/20220617/44a086ba4b894d309374a9e4e012a539.png
[rb02.jpg]: /images/20220617/51f7b1e882c8453583dc28891aa7bf1c.png
[1355319681_6107.png]: https://img-my.csdn.net/uploads/201212/12/1355319681_6107.png
[8394323_1293614183gD0H.jpg]: /images/20220617/12cbeec0fada44a783f4f8e823641792.png
[8394323_1293614183DSC3.jpg]: /images/20220617/4fc2c4c820b04afabe356fa5c151a5ac.png
[rb03.jpg]: /images/20220617/c588b05bbc47491a95383f4a9786a749.png
[rb03-1.jpg]: /images/20220617/2b98dc67243f4f2d99bdea353ac05090.png
[rb04.jpg]: /images/20220617/a78b6ff65b064ba3881a257eb1b00d0a.png
[rb05.jpg]: /images/20220617/a246c9abe81d4b40832fdc676b64b35f.png
[rb06.jpg]: /images/20220617/0ec08e6f1e0d4397af159768d1291349.png
[rb07.jpg]: /images/20220617/93390f24a4dd47c9b40f26a062113ed0.png
[rb08.jpg]: /images/20220617/82cd107427a44606b17e51661372d82b.png
[Center]: /images/20220617/d386774f61084d92b2d5b7dae0f5ff7a.png
[Link 1]: http://lib.csdn.net/base/datastructure
[Center 1]: /images/20220617/a3c478bc93ac406b9a1e9fbfa1007fd4.png