Last Regrets

Red Black Tree

半年前在研究HashMap的时候已经学习过红黑树的规则原理了. 不过现在又遇到就忘记是怎么实现的了.(只知道这玩意是用来平衡树的) 这次就把这个数据结构做一个了断.

性质

  • 性质1：每个节点要么是黑色，要么是红色。
  • 性质2：根节点是黑色。
  • 性质3：每个叶子节点（NIL）是黑色。
  • 性质4：每个红色结点的两个子结点一定都是黑色。
  • 性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

满足这5个性质就能保证红黑树是平衡的.

Insert

插入的节点默认是红色的.因为这样可以最大限度满足红黑树的5个性质.

请试想一下.如果插入的节点是红色:

  • 性质1可以满足.
  • 性质2可以满足.
  • 性质3可以满足(插入红色节点后自动衍生出2个黑色的NIL节点).
  • 性质4可能没法满足(新插入的节点的父节点也是红色).
  • 性质5可能没法满足(父节点是黑色时就不行).

然后是红黑树节点的左右旋.

看懂没? 节点的旋转大概就是这样。

然后就是要分插入的情况了.

  • 第一种：根节点为空。这种情况，将node的颜色改为黑色即可.

  • 第二种: node的父节点为黑色。这种情况不需要做修改.

  • 第三种: node的父节点为红色 (根据性质3，N的祖父节点必为黑色). 这种情况和变换规则都比较多.下面细说…

    • node的叔父节点为红色。这种情况，将N的父节点和叔父节点的颜色都改为黑色，若祖父节点是跟节点就将其改为黑色，否则将其颜色改为红色，并以祖父节点为插入的目标节点开始重新递归修复红黑树.

    • node的叔父节点为黑色，且node和node的父节点在同一边 (即父节点为祖父的左儿子时，N也是父节点的左儿子。父节点为祖父节点的右儿子时。N也是父节点的右儿子)。以父节点为祖父节的左儿子为例，将父节点改为黑色，祖父节点改为红色，然后以祖父节点为基准右旋。(N为父节点右儿子时做相应的左旋)

    • node的叔父节点为黑色，且node和node的父节点不在同一边 (即父节点为祖父的左儿子时，N是父节点的右儿子。父节点为祖父节点的右儿子时。N也是父节点左右儿子)。以父节点为祖父节点的左儿子为例。以父节点为基准，进行左旋，然后以父节点为目标插入节点进入情况3的b情况进行操作。

Delete

这个以后再说.

红黑树算是搜索二叉树的一个子集，Search方法是相同的。