jasono11111/rbtree

红黑树C++实现

RBTree

红黑树C++实现 一、二叉查找树（二叉排序树） 二叉排序树性质： 元素可比较相等和大小，关键字互不相同。 结点，左子树元素均小于该结点，右子树元素均大于该结点。 左、右子树也是二叉排序树。 中根次序遍历，升序序列

删除的总结：

删除叶子结点： 直接删除

删除度为1的结点： 即结点接到删除的结点的位置

删除度为2结点： 顶部根结点：其前驱或者后继都可以作为替换根节点删除的时候的值，因为前驱是左子树的最大值，一定是叶子结点或者度为1的结点，然后后继的话一定是最小值，也一定是叶子结点或者度为1结点。即将删除度2结点的转化为删除叶子结点或者度为1结点。（左子树最大值，是因为比左边都大，但是比右边都小，才可以替代他）

二、红黑树 1.节点是红色或黑色。 2.每个叶子节点都是黑色的空节点（NIL节点）。 3.根节点是黑色。 4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点) 5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

1>插入 分为五种局面 ①新结点（A）位于树根，没有父结点。

分析：插入节点就位于根结点上，没有父节点，直接绘制为黑色。（根结点变为黑色，只是每条路径到叶子结点的黑色结点数加1）

②新结点（B）的父结点是黑色。插入红色

分析：因为插入的时候肯定是插在叶子结点上，性质③不受影响；因为插入叶子后，该红色结点又补两个黑色的NIL结点；性质④也不影响，父节点是黑色，插入红色，补的是黑色，无影响；性质⑤不受影响，因为插入红色，路径上黑色结点数不增加。

③新结点（D）的父结点和叔叔结点都是红色。（不论插入结点是位于左边还是右边）

分析：此时出现连续两红，违背规则④；则我们可以将父节点和叔父结点绘制为黑色（同时绘制为黑色，将性质④变为正常，但是两边子树的黑色结点数都增加1），考虑如果（1）祖父结点位于根结点上的话，就五影响，因为就是两边子树增加一个黑色结点；（2）祖父结点不在根结点上，祖父结点这颗子树增加了黑色结点数，但是祖父的兄弟结点没有，所以此时需要将祖父结点重新绘制为红色。（保持左右两边子树路径上的黑色结点数目不变）。代码上可以直接将祖父结点绘制为红色，然后重新递归情况1。（因为将祖父结点绘制为红色以后，有可能祖父结点的父节点也是红色，需要重新递归情况1；相当于重新插入祖父结点的父节点）

④新结点（D）的父结点是红色，叔叔结点是黑色或者没有叔叔，且新结点是父结点的右孩子，父结点（B）是祖父结点的左孩子。

分析：情况4是为了将子节点和父节点的出现位置调成一致。（父结点在祖父结点的出现位置（左或者右）和子结点在父节点的出现位置（左或右））。 即可能情况： 父节点在祖父结点的左边，则子节点必须在父节点右边（不然就是情况5） 父节点在祖父结点的右边，则子节点必须在父节点左边（不然就是情况5）

子情况①：父节点在左边，子节点绕父节点左旋转变为情况5

子情况②：父节点在右边，子节点绕父节点右旋转变为情况5

⑤新结点（D）的父结点是红色，叔叔结点是黑色或者没有叔叔，且新结点是父结点的左孩子，父结点（B）是祖父结点的左孩子。

分析：两种情况，（1）左左型（2）右右型 （1）左左型：通过绕祖父节点进行右旋转（让左边的一个红色加到右边，右旋转增加右边结点个数）；然后将父结点和祖父结点进行颜色交换。（因为右旋转之后，左子树少了一个黑色结点，即父节点绘制为黑色，但是右边多了一个，则将祖父结点绘制为红色），祖父节点肯定为黑色（否则之前就违背了性质4）

（2）右右型：绕祖父结点进行左旋转，然后也是父节点和祖父结点进行颜色交换。

2>删除 ①如果待删除结点有两个非空的孩子结点，转化成待删除结点只有一个孩子（或没有孩子）的情况。

（1）根据二叉排序树删除一样，找删除节点的中序前驱或者后继替换，再考虑待删除节点的情况

情况1，自身是红色，子结点是黑色；此情况无影响

情况2，自身是黑色，子结点是红色：删除后将子节点红色变为黑色即可

情况3，自身是黑色，子结点也是黑色，或者子结点是空叶子结点（较多情况）

子情况1，删除之后结点处于根结点的位置，删除无影响

子情况2，结点2的父亲、兄弟、侄子结点都是黑色；只要修改兄弟结点为红色即可

子情况3，结点2的兄弟是红色；左旋转+变色，可能出现子情况4，5，6

子情况4，结点2的父亲是红色，兄弟和侄子都是黑色；将父亲和兄弟颜色对调即可

子情况5，结点2的父亲随意，然后兄弟节点B黑色，左侄子红色，右侄子黑色；即以兄弟结点进行右旋转，再将兄弟结点位置和右侄子位置的变色，转化为情况6

子情况6，结点2的父亲随意，然后兄弟结点为黑色，右侄子红色；以根节点进行左旋转，再让根节点和左孩子颜色交换，右孩子变为黑色

情况4，自身不论是什么颜色，无子节点，直接删除