1.红黑树的基本概念与数据结构表示

　　红黑树定义：红黑树又称红-黑二叉树，它具体二叉树所有的特性。同时红黑树更是一颗自平衡的排序二叉树（平衡二叉树的一种实现方式）。

　　一颗基本的二叉排序树都需要满足一个基本性质：即树中的任何节点的值大于它的左子节点，且小于它的右子节点。

　　那按照这个基本性质使得树的检索效率大大提高。我们知道在生成二叉树排序树的过程是非常容易失去平衡的，最坏的情况就是一边倒（只有右/左子树），这样势必会导致二叉树的检索效率大大降低（o(n)），所以为了维持二叉树的平衡，提出了各种平衡二叉树的实现算法，如：AVL，SBT，伸展树，TREAP，红黑树等等。

　　平衡二叉树必须具备如下特性：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。也就是说该二叉树的任何一个子节点，其左右子树的高度都相近。下面给出平衡二叉树的几个示意图：

　　红黑树顾名思义就是节点是红色或者黑色的平衡二叉树，它通过颜色的约束来维持着二叉树平衡。对于一颗有效的红黑树而言我们必须增加如下规则，这也是红黑树最重要的5点规则：

　　1.每个节点都只能是红色或者黑色中的一种。

　　2.根节点是黑色的。

　　3.每个叶节点（NIL节点，空节点）是黑色的。

　　4.如果一个节点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色节点。

　　5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这些约束强制了红黑树的关键性质: 从根到叶子最长的可能路径不多于最短的可能路径的两倍长。结果是这棵树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。所以红黑树它是复杂而高效的，其检索效率O(lg n)。下图为一颗典型的红黑二叉树：

 

2.红黑树的三个基本操作

红黑树在插入，删除过程中可能会破坏原本的平衡条件导致不满足红黑树的性质，这时候一般情况下要通过左旋、右旋和重新着色这个三个操作来使红黑树重新满足平衡化条件。

旋转

　　旋转分为左旋和右旋。在我们实现某些操作中可能会出现红色右链接或则两个连续的红链接，这时候就要通过旋转修复。

　　通常左旋操作用于将一个向右倾斜的红色链接(这个红色链接链连接的两个结点均是红色结点)旋转为向左链接。对比操作前后，可以看出，该操作实际上是将红线链接的两个结点中的一个较大的结点移动到根结点上。

左旋转：

对x进行左旋，意味着"将x变成一个左节点"。

右旋转：

对y进行右旋，意味着"将y变成一个右节点"。

 

颜色反转

当出现一个临时的4-node的时候，即一个节点的两个子节点均为红色

 我们需要将E提升至父节点，操作方法很简单，就是把E对子节点的连线设置为黑色，自己的颜色设置为红色。

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有