大家好，我是讯享网，很高兴认识大家。



  红黑树久闻大名，一直没能好好理解。  最趁着近有换工作的念头，想着从根本上把它理解透了。为了比较深入的对红黑树有比较深入的认识，用python实现，并将结构进行了可视化操作。 本文使用的红黑树的图，都是在 代码生成的图(rb目录)里面。

插入红黑树的顺序： [5, 14, 16, 3, 18, 2, 9, 15, 6, 17, 10, 19, 4, 1, 12, 8, 7, 11, 13]

删除的顺序列为：  [1, 3, 11, 12, 8, 15, 18, 9, 5, 13, 7, 14, 10, 6, 2, 16, 19, 17, 4]

图像生成使用 matplotlib ，实现方式可自行查看代码。 这里只对红黑树的性质进行分析。

  红黑树是一棵二叉树， 有五大特征：

   特征一： 节点要么是红色，要么是黑色（红黑树名字由来）。

    特征二： 根节点是黑色的

    特征三： 每个叶节点(nil或空节点)是黑色的。

     特征四： 每个红色节点的两个子节点都是黑色的（相连的两个节点不能都是红色的）。

    特征五： 从任一个节点到其每个叶子节点的所有路径都是包含相同数量的黑色节点。

  从五大特征直观上总结出来几个点：

 1 对每个红色节点，子节点只有两种情况：要么都没有，要么都是黑色的。（不然会违反特征四）

 2 对黑色节点，如果只有一个子节点，那么这个子节点，必定是红色节点。（不然会违反特征五）

3 假设从根节点到叶子节点中，黑色节点的个数是h, 那么树的高度H范围 h<= H <= 2H（特征四五决定）。

正因为总结的第3点，决定的红黑树的查找不会退化到线性查找。查找时间复杂度为O(lgn)。

讯享网

红黑树例中插入后，需要调整红黑树，调整方法就是左旋(节点5），来重新平衡

在插入节点2时，采用右旋（节点5）操作来重新平衡

基本代码：

如果插入的是黑色节点时，则每次插入都会违返性质5, 都需要重新调整树。

所以 插入时，每次都认为只插入红色节点。这样调整的次数就会减少很多。 倡但是还是有要调整的情况

1 如果插入的是根节点，则直接把点变成黑色（性质二）， 示例中插入第一个节点5的情况

2 如果插入的节点的父节点是黑色节点，则不调整颜色。 示例中 插入点10 就属于这种情况

3 如果插入节点的父节点的红色节点（违反性质四），且父节点的兄弟节点为红色节点。 

    1) 把父节点及其兄弟节点变成黑色，把组父节点变成红色（使其不违反性质五）。 

   2 )再检查祖父节点是否违反红黑树的性质（一或四）

    处理方法： 把父节点变成黑色节点，把祖父节点变成红色节点， 同时反向旋转祖父节点（同左则，右旋； 同右则左旋）

   示例中，插入 节点12, 节点7就是此种变行。

 5 如果插入节点的父节点的红色节点（违反性质四），且父节点的兄弟节点为黑色节点。  并且插入节点，父节点，及祖父节点同则。

    处理方法：旋转父节点，使期变成同则（第4种情况）， 再根据情况4来处理。

    示例中 插入节点6就属于这种情况

        

两个概念： 

前驱节点： 节点的左子树中， 最大值的节点。

后继节点： 节点的右子树中，最小值的节点。

我写的示例中，把删除操作分成了三个步骤：

    1  获取要真正删除的叶子节点（把删除操作都归为删除叶子节点操作）

            目的：把要删除的点，往叶子节点推。使删除操作变成删除叶子节点的操作。

            找到要删除节点的后继节点或前驱节点，如果存在，则替换掉当前节点。

            再以替换后的节点，的后续或前驱节点。替换掉，直到无后继或前驱节点。

2 对红黑树进行调调整，使删除节点后的树，不违反红黑树的性质。

3  真正的删除节点。

获取真正删除的节点操作 示例中删除16时为例做下说明

如图所示的变换中，把节点16,推到了叶子节点，使删除节点16时，不破坏二叉树的性质。

总共进行了两步变换： 16与17(后继节点）互换。 16与19（后续节点）互换 变成了后面图的样子

将问题由删除根节点16,变成了删除叶子节点16.

目的： 使删除节点后的树还是一棵红黑树

注： 这使用的删除示例图中将包含把删除节点往叶子节点推的过程。

1 ） 删除的节点是红色节点，可不需要调整直接删除 （如上图的16节点, 及删除节点3时）

2 )  删除的节点是根直接，直接删除

3)  如果是黑色节点，兄弟节点是红色节点， 旋转父节点： 把你节点变成黑色，兄弟节点变黑色。 重新平衡。

注：演示示例中没有此按例，另外示例中找到的示例。

4 ) 删除黑色节点，兄弟结点也是黑色节点，  且兄弟节点的要么没有子节点，要么所有子节点都是黑色节点。 

        1 直接将兄弟节点变成红色节点

         2 如果父节点是红色节点，直接把父节点变成黑色节点（调整结束）。 

         3 如果父节点是黑色节点，再检查当前节点（递归检查）（示例中删除14节点，19 变红色后，再递归把6也变成红色）。

5) 删除黑色节点，兄弟结点也是黑色节点，  兄弟节点的同则子节点（如果兄弟节点为左节点，则为史弟节点的左节点，右节点同理）为红色节点

        操作： 1 变色： 兄弟同则子节点设置成黑色。 兄弟节点（黑色）和父节点（可能是红色，也可能是黑色）互换颜色

                    2  旋转父节点。

    示例中删除节点15 就属于此种情况。

6)        删除黑色节点，兄弟结点也是黑色节点， 兄弟节点的同则子节点 为黑色节点或无节点， 而兄弟节点 异则子节点为红色子节点

操作：1  变色： 兄弟节点变成红黑， 兄弟节点的异则子节点变成黑色。

          2 旋转兄弟节点： 可使节点变成  情况5.

 如示例中删除节点18， 18_delete_1,到18_delete_2 是由两步转换成成。

删除前调整代码

红黑树的插入，删除情况已经说完了，明白上面的流程，可以构建一棵红黑树。

需要说明的上，上述的变换并不是为一的方案， 只要能够满足红黑树的性质，都是可行方案。

 如上面删除节点18的示例中， 查找替换的而子节点时， 我们查找替换子节点时，直接找了后续节点19.   这就造成了我们得变换两次（第一次转成删除中的第5种情况， 第二次处理第5种情况）。 如果我们拿的是前驱节点 17时， 可直接不需要变换就可直接删除。

所以寻找替换子节点时 步聚可调整为： 如果前驱节点或后续节点如果有红色节点，可优先选择。

同时，有些变换，也会多种变换方法