红黑树

红黑树

红黑树和平衡二叉查找树（AVL树）类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。

红黑树是一种自平衡二叉查找树。它不是严格控制左、右子树高度或节点数之差小于等于1，但红黑树高度依然是平均log(n)，且最坏情况高度不会超过2log(n)。

本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。

红黑树的性质

1.红黑树是每个节点都带有颜色属性，或红色或黑色；

2.根节点是黑色；

3.叶节点（即指树尾端NIL指针或NULL结点）是黑色；

4.一个结点是红的，那么它的两个子节点都是黑色；

5.对于任意结点，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长，结果是这个树大致上是平衡的。

红黑树的操作

在对红黑树进行插入和删除等操作后，可能会违背、或破坏红黑树的原有的性质。为使插入、或删除结点后的树依然维持为一棵新的红黑树，需要做俩方面工作：

1、部分结点颜色，重新着色

2、调整部分指针的指向，即左旋、右旋。

注：对X左旋，意味着"将X变成一个左节点"。