数据结构之红黑树（图文并茂版、一篇足够版）_红黑树的原理 图

• 为什么会出现红黑树
• 红黑树的原理

网络上关于红黑树的资料很多，但是总是上来就给出红黑树的特点，弄的人云里雾里，索性自己学习整理，写一篇较为完整的红黑树文章，文章从上面二个标题来展开，首先介绍红黑树的由来。
红黑树动态插入演示

红黑树的由来

你应该听说过：二叉树、平衡二叉树、B树、B+树、红黑树。
说到底红黑树还是一种二叉树，是为了解决普通树存在的问题而诞生的。
先来看二叉树

1.左子树上所有结点的值均小于或等于它的根结点的值。
2.右子树上所有结点的值均大于或等于它的根结点的值。
3.左、右子树也分别为二叉排序树。

二叉树的本质是进行二分查找，具有优越的查找性能。对于普通的二叉树，我们按顺序插入9、8、7、6、5、4、3、2、1会出现什么情况呢？

根据二叉树原理来插入，这棵树会显得很不平衡，其查找性能随之下降，这里我要查找3，几乎是线性遍历了。所以，在普通二叉树的基础上，我们还需要一定的理论，让树可以自己保持平衡，于是出现了AVL树，也就是平衡二叉树。平衡二叉树的理论可以让我们再插入图二的数据时，生成一个图一中的数据结构。AVL是一颗完美平衡的树，非常好非常理想化，但实际数据结构中我们仿佛听到的更多的是红黑树，为什么？
简而言之是，AVL具有完美的查找性能，但进行插入、删除时，需要进行的旋转操作次数不可控，有些效率问题。但红黑树保证的不是完美平衡，而是比较平衡，提高了插入、删除节点的效率，而查找性能并没有降低(红黑树log2N，AVL树logN)，任何不平衡都会在三次旋转之内解决。所以实际工程中使用红黑树较多。

红黑树的原理

为了保证大致平衡这个理念，这才有了下面这几个到处都有的红黑树性质。

1.　根节点是黑色的；
2.　每个叶子节点都是黑色的空节点，也就是说，叶子节点不存储数据；
3.　任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
4.　每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

为什么要有颜色区分？为了限制旋转次数。当颜色满足时就可停止旋转，当然节点的值也是影响旋转的因素之一。我们看下面这个例子：
插入3，此时3是黑色

插入1，此时1是红色

插入2，经过两次旋转，如下几步
第一步：

根据规则，插入的2是红色，不满足规则3
第二步：

不满足规则3
第三步：

不满足规则3，改变颜色
第四步：

这时我们继续插入4，会发生什么事情？



到这里基本是按照规则进行改变颜色，为了形象说明红黑树中颜色的作用，我们用AVL平衡树来做一个对照，在后面数据插入的过程中，会看到这个变化。
从001-004这个过程是一样的，用同样的办法构建一个AVL树：

接着看如下变化，插入节点5，在结构上看不出什么，但是平衡树进行的遍历次数要比红黑树多了。

接着插入006

经过对比，此时已经能看出变化，红黑树只是继续在005后追加006，而平衡树却经过遍历，进行了一次旋转。
具体的动画效果包含的信息也非常丰富

红黑树可视化
AVL树可视化
说真的这里不得不吐槽，我们国家的计算机教育怎么没有这么好的学习资源，这么好的学习资源甚至还没有普及，还很少人知道。

经过动画展示，以及可以看出来，红黑树的插入效率要比AVL树高，但不绝对平衡这件事。

下面我们看一下jdk1.8中，HashMap在处理hash冲突使用的红黑树源码。

红黑树源码

位置：HashMap.class 2214行开始
这里是红黑树的插入方法

        static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                    TreeNode<K,V> x) {
            //新插入的节点为红色
            x.red = true;
            //定义变量和循环
            //xp：当前节点的父节点
            //xpp：爷爷节点
            //xppl：左叔叔节点，这里的变量名起的不好，应该是xpl更合适，下同
            //xppr：右叔叔节点
            for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
            	//如果当前节点父节点为空，直接返回插入的x，并置成黑色（false），说明白点就是插入第一个节点
                if ((xp = x.parent) == null) {
                    x.red = false;
                    return x;
                }
                //如果父节点不是红色或爷爷节点不为空，直接返回根节点。基本上是插入第二行和其他不需要变换的情况。请见下注释一说明情况。
                else if (!xp.red || (xpp = xp.parent) == null)
                    return root;
                // 如果父节点是爷爷节点的左孩子Condition_1（和下面Condition_2对应），见注释二
                if (xp == (xppl = xpp.left)) {
                	//Condition_1_1 如果其右叔叔不为空，且为红色，则改变右叔叔的颜色，改变父亲的颜色，改变爷爷的颜色，见注释二
                    if ((xppr = xpp.right) != null && xppr.red) {
                        xppr.red = false;	//叔叔节点置黑
                        xp.red = false;		//父亲置黑
                        xpp.red = true;		//爷爷置红
                        x = xpp;			//进入下一次循环
                    }
                    //Condition_1_2 右叔叔为空 或者 为黑色
                    else {
                    	// 如果当前节点是父节点的右孩子	Condition_1_2_1，见注释三
                        if (x == xp.right) {
                        	// 父节点左旋
                            root = rotateLeft(root, x = xp);
                            // 见注释三
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                        // 如果父节点不为空 Condition_1_2_2 ，见注释三
                        if (xp != null) {
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                root = rotateRight(root, xpp);
                            }
                        }
                    }
                }
                // 如果父节点是爷爷节点的右孩子Condition_2
                else {
                	// 如果左叔叔是红色 Condition_2_1
                    if (xppl != null && xppl.red) {
                        xppl.red = false;// 左叔叔置为 黑色
                        xp.red = false;// 父节点置为黑色
                        xpp.red = true;// 爷爷置为红色
                        x = xpp;// 运行到这里之后，就又会进行下一轮的循环了，将爷爷节点当做处理的起始节点
                    }
                    // 如果左叔叔为空或者是黑色Condition_2_2
                    else {
                    // 如果当前节点是个左孩子 Condition_2_2_1
                        if (x == xp.left) {
                        // 针对父节点做右旋
                            root = rotateRight(root, x = xp);
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                        //Condition_2_2_2
                        if (xp != null) {
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                // 针对爷爷节点做左旋
                                root = rotateLeft(root, xpp);
                            }
                        }
                    }
                }
            }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

源码是左右互偶的，不太明白网上说红黑树最多旋转3次以内。通过阅读源码可以看出来，判断是否旋转的条件包括节点颜色、节点的左右性，节点是否为空三种条件。

上面我们有张图

这时如果插入007节点会发生什么事？
首先007是006的右子节点，且父节点为爷爷节点右孩子，直接进入Condition_2_2_2，一次旋转，父节点和爷爷节点变色即可。我们看结果



以上

---

注释一

条件一 !xp.red有这样一颗树，现在要插入一个大小为0.9的节点


我们会发现，当父节点为黑色，是可以直接插入，且不用旋转的。
条件二 (xpp = xp.parent) == null
初始树：

插入001

这种情况直接可以插入成功，不需要变换。所以可以直接返回root（该函数的返回值就是返回当前树的root节点）

注释二

有如下初始树

现在要插入004，则4的父亲005节点是其爷爷节点（006）的左孩子，满足该条件

xp == (xppl = xpp.left)

然后这里也满足第二个条件Condition_1_1

xppr = xpp.right) != null && xppr.red

现在插入004，按照代码里的规则，会改变007的颜色为黑，005的颜色黑，006的颜色为红。我们看动画分解：


完全按照代码的逻辑实现的，但是真里有人问了，006根节点不应该是黑色么，注意看这里面的代码是一个for循环，改变颜色后并没有return，而是进入下一次循环，第二次就会将爷爷节点当作当前处理的节点来处理，也就是006，然后就会执行注释一的逻辑，将其置黑，并return。

if ((xp = x.parent) == null) {
    x.red = false;
    return x;
}
1
2
3
4

注释三

Condition_1_2_1 如果当前节点是父节点的右孩子
初始化树

现在要插入003，003的位置会在002的右侧（永远往叶节点插入数据，然后再旋转）

条件满足了，这时候父节点左旋

进入下一个条件，此时002满足Condition_1_2_2，

将父节点置黑，爷爷节点置红，爷爷节点右旋转