【FX】红黑树的原理及操作
http://cdn.u1.huluxia.com/g4/M01/F4/09/rBAAdmDgHhuAde_1AAJTyikZ9mg310.jpg
介绍：
红黑树（ Red black tree）是种自平衡二叉查找树，在计算机科学中用到的一种数据结构。
它是在1972年由 Rudolf Bayer发明的当时被称为平衡二叉B树（ symmetric binary B-trees）。后来，在1978年被 Leo. guibas和 Robert sedgewick修改为如今的红黑树R-B Tree，全称是Red- Black tree，又称为“红黑树"，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红（Red或黑（Back）
性质：
红黑树是一棵平衡二叉搜索树，其中序遍历单调不减
节点是红色或黑色。
根节点是黑色。
每个叶节点（也有称外部节点的，目的是将红黑树变为真二叉树，即NULL节点，空节点）是黑色的。
每个红色节点的两个子节点都是黑色。（换句话说，从每个叶子到根的所有路径上不能有两个连续的红色节点）
从根节点到每个叶子的所有路径都包含相同数目的黑色节点（这个数值叫做黑高度）。
观察下面这颗红黑树（自行脑补外部节点NULL）http://cdn.u1.huluxia.com/g4/M01/F4/09/rBAAdmDgHhyAM5a-AAEEAJo3ajQ940.jpg
事实，每一颗红黑树都有等价的B-树，如上图的红黑树对应的等价B-树（2，3，4树）如下：http://cdn.u1.huluxia.com/g4/M01/F4/09/rBAAdmDgHhyAKF3cAAFQAH4QGw4109.jpg
因此，学好红黑树的诀窍就是：心中有B-树
左旋与右旋：
左旋： http://cdn.u1.huluxia.com/g4/M01/F4/09/rBAAdmDgHh2AMKz3AAKQAASAUkc662.jpg
右旋 ：http://cdn.u1.huluxia.com/g4/M01/F4/09/rBAAdmDgHh6AVXhdAAKUAAkD4_M565.jpg
插入的调整策略：
在对红黑树进行插入操作时，我们一般总是插入红色的节点，因为这样可以在插入过程中尽量避免对树的调。
那么，我们插入一个节点后，可能会使原树的哪些性质改变列？
如果插入的节点是根节点，性质2会被破坏，如果插入节点的父节点是红色，则会破坏性质4.
因此，总而言之，插入一个红色节点只会破坏性质2或性质4我们的恢复策略很简单，插入修复具体操作情况：
情况1：
插入的是根节点。
原树是空树，此情况只会违反性质2。
对策：直接把此节点涂为黑色。
情况2：
插入的节点的父节点是黑色
此不会违反性质2和性质4，红黑树没有被破坏。
对策：什么也不做。
情况3：当前节点的父节点是红色且祖父节点的另一个子节点（叔叔节点）是红色
此时父节点的父节点一定存在，否则插入前就已不是红黑树。与此同时，又分为父节点是祖父节点的左子还是右子，对于对称性，我们只要解开一个方向就可以了。在此，我们只考虑父节点为祖父左子的情况。同时，还可以分为当前节点是其父节点的左子还是右子，但是处理方式是一样的。我们将此归为同一类
对策：将当前节点的父节点和叔叔节点涂黑，祖父节点涂红，把当前节点指向祖父节点，从新的当前节点重新开始算法。
情况4：当前节点的父节点是红色叔叔节点是黑色，当前节点是其父节点的右子
对策：当前节点的父节点做为新的当前节点，以新当前节点为支点左旋。
情况5：当前节点的父节点是红色叔叔节点是黑色，当前节点是其父节点的左子
策略：父节点变为黑色，祖父节点变为红色，在祖父节点为支点右旋
页:
[1]