数据结构之红黑树

---

红黑树介绍：

红黑树是一个平衡的二叉树，但不是一个完美的平衡二叉树。虽然我们希望一个所有查找都能在~lgN次比较内结束，但是这样在动态插入中保持树的完美平衡代价太高，所以，我们稍微放松逛一下限制，希望找到一个能在对数时间内完成查找的数据结构。这个时候，红黑树站了出来。

1：红黑树性质

先上图性质一：所有节点要么是红色要么是黑色。这里只是对节点进行区分，也就是说节点只有2种状态性质二：根节点必须是黑色。性质三：所有叶子节点（NIL或者空节点）必须为黑色。性质四：红节点的2个子节点必须都为黑色。这里是杜绝出现连续的红节点性质五：从任一节点到其它每个叶节点的所有路径都包含相同数目的黑色节点。只有满足以上5个性质的二叉树才是红黑树。

2：红黑树预备知识

红黑树是一棵特殊的树二叉搜索树，正常情况下，二叉树的插入，查找的时间复杂度都是O(logn)，但是在极端情况下，二叉搜索树会退化成链表，导致插入，查找的复杂度回达到O(logn)，理想情况下，是实现一棵完全平衡树，但是因为调整一棵二叉树成为一棵完全平衡树，代价太大，得不偿失。因此红黑树作为一种权衡替代了完全平衡树。红黑树插入操作和二叉搜索树无异，不同在于插入之后怎么调整使其成为一棵红黑树，即满足上文提及的5条红黑树性质。

3：红黑树基本操作

改变颜色：黑 -> 红 红-> 黑

左旋：

右旋：

4：红黑树调整操作

假设插入节点是N，插入节点父亲节点是P，祖父节点是G，叔父节点是S

情形一：插入节点是根节点，则根据性质二，直接将插入节点置为黑色

情形二：如果插入节点父节点是黑色，则因为插入节点默认是红色。所以不需要做任何操作，即可满足红黑树平衡条件，之所以插入节点默认是红色，因为如果插入节点是黑色，则直接违背性质五，基本上所有的子树都需要做调整，代价太大。

情形三:：如果插入节点是红色，父亲节点是红色，叔父节点也是红色，这种情形下，祖父节点肯定是黑色，先把祖父节点变为红色，父亲节点，叔父节点变为黑色，这样即不会违背性质四，又同时协调了规则五，因为所有经过节点P，S 的支路要么以P，S为根节点，要么必须经过G；但是祖父节点颜色改变了，所以需要对祖父节点进行插入节点调整操作，这是一个迭代的过程。

情形四：如果插入节点N是红色，父亲节点是红色，叔父节点是黑色，父亲节点P是祖父节点的左孩子；这种情形下，祖父节点G一定是黑色节点。如果插入节点N是父亲节点P的右孩子，需要先以父亲节点P为中心进行左旋，然后以祖父节点G为中心进行右旋。这个时候，因为新祖父节点和新祖父节点的左孩子都是红色，新祖父节点的右孩子是黑色，只需要新祖父节点置为黑色，新祖父节点的右孩子置为红色，即可满足红黑树条件。

情形五：如果插入节点N是红色，父亲节点是红色，叔父节点是黑色，父亲节点P是祖父节点的右孩子；这种情形下，祖父节点G一定是黑色节点。如果插入节点N是父亲节点P的左孩子，需要先以父亲节点P为中心进行右旋，然后以祖父节点G为中心进行左旋。这个时候，因为新祖父节点和新祖父节点的左孩子都是红色，新祖父节点的右孩子是黑色，只需要新祖父节点置为黑色，新祖父节点的右孩子置为红色，即可满足红黑树条件。