红黑树

定义

是一种特殊的AVL数（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的：它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。

特征

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

性质

从根节点到叶结点的最长路径不大于最短路径的2倍
有n个内部节点的红黑树高度h<=2Log(n+1)
红黑树查找操作时间复杂度=O(logn)

操作

在红黑树上只读操作不需要对用于二叉查找树的操作做出修改，因为它也是二叉查找树。但是，在插入和删除之后，红黑属性可能变得违规。恢复红黑属性需要少量(O(log n))的颜色变更（这在实践中是非常快速的）并且不超过三次树旋转（对于插入是两次）。这允许插入和删除保持为 O（log n)）次，但是它导致了非常复杂的操作。

旋转

当我们在对红黑树进行插入和删除等操作时，对树做了修改，那么可能会违背红黑树的性质。
为了保持红黑树的性质，为了保持红黑树的性质，通过对树进行旋转（例如左旋和右旋操作），即修改树中某些结点的颜色及指针结构，以达到对红黑树进行插入、删除结点等操作时，红黑树依然能保持它特有的性质（五点性质）。

查找

与BST、AVL相同，从根出发，左小右大，若查找到一个空叶节点，则查找失败

插入

由一般二叉树的查找步骤，把新节点z插入到某个叶子节的位置上
z染为红色
while(z 不是根结点 &&color[z->parent]= =RED) {Insert-Fixup(T,z);}//保证红黑树的性质能继续，再对有关结点重点着色并旋转
color[root[T]]=BLACK；根节点设置成黑色

如果新插入的是黑色结点，那么它所在的路径上就多出一个黑色的结点，所以新插入的结点一定要设成红色。

但是如果 z 的父结点也是红色，这就违反了每个红色结点的两个子结点都黑色的性质。

删除

与红黑树的的插入算法一样，对一个结点的删除算法要花 O(log n)时间，只是删除算法略微复杂些

if (z 的左右子结点均为 NIL)
{ NIL 结点代替 z 的位置； delete(z); }\
else if (z 有一个子结点为 NIL)
{z 的非 NIL 子结点代替 z 的位置；delete(z); }\
else
{将红黑树中序遍历中 z 的后继结点 s 的值赋给 z; delete(s); }\
if (删除的结点是黑色的) Delete-Fixup(T,x); /*x 指向代替删除结点的结点 */ }

若删除的结点是红色，则不做任何操作，红黑树的任何属性都不会被破坏

若删除的结点是黑色的，显然它所在的路径上就少一个黑色结点，红黑树的性质就被破坏了，这时执行一个 Delete-Fixup（）来修补这棵树。一个结点被删除之后，一定有一个它的结点代替了它的位置，即使是叶结点被删除后，也会有一个空结点来代替它的位置。