简介

红黑树是一种自平衡的二叉查找树。和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。它查找、插入和删除的时间复杂度为O(logn)，这里的n是树中元素的数目。

特性

除了二叉查找树的特性外，红黑树还具有下列特性：

节点是红色或黑色
根节点是黑色
每个叶子节点都是黑色的空节点（NIL节点）
每个红色节点的两个子节点都是黑色。（即从每个叶子到根的所有路径上都不能有两个连续的红色节点）
从一个节点（该节点任意）到其每个叶子的所有路径都包含相同数量的黑色节点。

下图是一棵典型的红黑树：

红黑树的调整

查找和修改的操作并不会改变红黑树的结构，但是当插入或删除节点的时候，红黑树的规则有可能被打破。这时就需要进行一些调整来维持红黑树的特性。

调整有两种方法：变色和旋转，旋转又分为左旋转和右旋转

变色

当插入一个节点的时候，由于插入的节点为红色（如果是黑色就违背了规则5），所以如果其父节点也为红色的话，为了不破坏规则4，就需要将其父节点变为黑色，这就是其中一种变色。例如插入节点21后，要将节点22变色。

可以看到，这时又破坏了其他规则，所以要继续进行变色或旋转，直至满足所以规则为止。

左旋转

逆时针旋转红黑树的两个节点，父节点被自己的右孩子取代并成为其左孩子，原右孩子的左孩子成为原父节点的右孩子。如图：

右旋转

顺时针旋转红黑树的两个节点，父节点被自己的左孩子取代并成为其右孩子，原左孩子的右孩子成为原父节点的左孩子。如图：

例子

插入节点

继续以刚才插入节点21为例：

首先，把节点25及其以下节点变色：

此时节点17和节点25是连续的两个红色节点，可以把节点17变为黑色节点吗？不可以。因为这样就违背了规则4，并且不能再通过变色来维持规则4（假如将节点17变为黑色，由于17的父节点就是根节点，根据规则2，根节点必须是黑色，所以不能够将其父节点变色，这样从根节点到其右子树的叶子所经过的黑色节点数肯定大于到其左子树的叶子所经过的黑色节点数）。

既然变色无法解决问题，那么就应该通过旋转了，把节点1.看作X，节点17看作Y，然后像刚才的示意图那样进行左旋转：