R/B Tree分析

1、红黑树是一棵平衡二叉搜索树，每个节点或是红色或是黑色2、根节点是黑色3、每个叶子节点都是黑色的4、每个红色的节点的两个子节点都是黑色的，      不能 有两个连续的红色节点5、从根节点到每个叶子的所有路径都包含相同数量的黑色节点。     黑高度

60

20

30

25

21

10

else if (!xp.red || (xpp = xp.parent) == null)                    return root;

  if ((xp = x.parent) == null) { x.red = false; return x; }

35

5

总结：1、只有一个节点，即为根节点设置黑色2、父节点为红色节点：2.1）叔叔的空的，旋转+变色(G、P)2.2）叔叔是红色的，父节点+叔叔节点变成黑色，祖父节点变成红色2.3）叔叔是黑色的，旋转+变色，递归

40

15

null

50

22

45

X

XPP

插入流程1、插入的节点必须是红色的。如果插入是黑色的违反第5条规则因为被插入前的树结构是构建好的，一但我们进行添加黑色的节点，无论添加在哪里都会破坏原有路径上的黑色节点的数量平等关系，所以插入红色节点是正确的选择

插入40

 if (xppl != null && xppl.red) {                        xppl.red = false;                        xp.red = false;                        xpp.red = true;                        x = xpp;                    }

70

XPPL

情况一：只有一个点，插入的点为根节点。原树是空树，此情况只会违反性质2。对策：直接把此节点涂为黑色 

x

情况三：违背规则4、红黑树被破坏父节点是红色、叔叔节点是空的情况下对策：左旋+变色（XPP/XP）

插入20

轴点

xp

把10也设置成黑色，黑高度相同原则

uncle

插入25、50

性质1、红黑树是一棵平衡二叉搜索树，每个节点或是红色或是黑色2、根节点是黑色3、每个叶子节点都是黑色的4、每个红色的节点的两个子节点都是黑色的，      不能有两个连续的红色节点5、从根节点到每个叶子的所有路径都包含相同数量的黑色节点。     黑高度相同。

插入60，破坏规则

if ((xp = x.parent) == null) {                    x.red = false;                    return x;                }

XP/XPPR

xpp

左旋+变色

插入35不破坏任何规则

情况四当前节点的父节点是红色且祖父节点的另一个子节点（叔叔节点）是红色 此时父节点的父节点一定存在，否则插入前就已不是红黑树。与此同时，又分为父节点是祖父节点的左子还是右子，对于对称性，我们只要解开一个方向就可以了。在此，我们只考虑父节点为祖父右子的情况。同时，还可以分为当前节点是其父节点的左子还是右子，但是处理方式是一样的。我们将此归为同一类。对策：将当前节点的父节点和叔叔节点涂黑，祖父节点涂红，把当前节点指向祖父节点，从新的当前节点重新开始算法。

插入30

情况二：插入的节点的父节点是黑色此不会违反性质2和性质4，红黑树没有被破坏。 对策：什么也不做。