红黑树
介绍
AVL是一颗二叉查找树，每个节点的平衡因子定义为这个节点两颗子树的高度差，这个值要么是0，要么是1或-1。其查询的最差时间复杂度为O(lgn)。
AVL树在构造和后续增删节点的过程中一直保持着其特性，但是维持平衡的开销比较大。
红黑树对平衡的要求条件没有AVL树那么苛刻。红黑树是一种确保拥有对数阶高度的二叉搜索树，每个节点都带有一些信息（color field)。
基本特性
1.每个节点是黑色或者是红色；
2.根节点和叶节点都是黑色的；
3.每个红色节点的父节点都是黑色的；
4.任何一个节点到其任何叶节点简单路径上的黑色节点数量相同。
修改和查找
因为是二叉查找树，查找步骤和其它二叉查找树一样：
通过比较输入key与根节点val的大小关系，如果key<val,进入左子树，key>val，进入右子树，key=val,则根节点是目标。
伪代码如下：
1 search (key, root) 2 if root = null 3 return root 4 if root.val = key 5 return root 6 else if root.val < key 7 return search (key, root.left) 8 else 9 return search (key, root.right)
增加节点
先找到增加节点的位置，插入新增节点，然后根据情况调整其它节点的位置和色域。每一个新增的节点颜色初始都为红色。
增加的节点有以下这些情况：
1）节点为根节点
将节点颜色修改为黑色，然后结束流程。
2）父节点为黑节点
没有破坏红黑树的四个特性任一个。可以直接结束。
3）父节点为红色：隐藏条件是有祖父节点并且祖父节点为黑色。（由特性2和特性3决定）
case 1.叔父节点为红节点（或不存在）:
将祖父节点的黑色下移，使得祖父节点变为红色，父节点和叔父节点变为黑色。这样就没有破坏特性3和特性4。如下图所示：
因为祖父节点变为了红色，有可能破坏了条件。所以之后再把当前节点设置为祖父节点，对当前节点进行上述同样的判断。
case 2.叔父节点为黑节点且插入节点为父节点左孩子（父节点也为祖父节点左孩子），右孩子的情况为映像：
对父节点A进行右旋操作，然后交换父节点A与祖父节点C的颜色，如下图所示：
我们可以看到条件3和条件4仍然遵守，而且祖父节点变为了黑色，意味着可以结束操作了。
case 3.叔父节点为黑节点且插入节点为父节点右孩子（父节点为祖父节点左孩子）
对A左旋，此时会发现变成了case2的情况。然后后续步骤和case2一样。如下图所示：
删除节点
和插入节点一样，先找到待删除节点。删除节点后，再调整其它节点的位置和色域。
待删除的节点可以分为三种情况：没有孩子节点、只有一个孩子节点、有两个孩子节点。
1）没有孩子节点
如果是红色的话，可以直接删除（不破坏基本特性）。
如果是黑色节点话，删除之后还需要调整剩余节点使之恢复平衡。（这里的情况比较多）
2）只有一个孩子节点
一定是黑色的节点，而且孩子节点一定是红色节点。 反证：如果该节点是红色节点且只有一个孩子，那孩子节点需要为黑色节点，但这破坏了相同黑色深度的条件。
可以直接将孩子节点替换待删除的节点，然后修改孩子节点的颜色为黑色。
3）有两个孩子节点
和二叉查找树类似，找左子树最右节点或右子树最左节点（暂称为X）替换待删除的节点。将节点X替换的过程其实可以理解成删除X的过程，变成了情况1和情况2。
为何能保持平衡
红黑树的特性3和4决定了红黑树的根节点到叶子的最长长度（路径上黑红节点交替出现）最多是最短长度（路径上全是黑节点）的两倍。
在增加节点和删除节点后对相关节点进行位置和色域上的修改来保持红黑树的四个特性。
版权声明：本文为ningbing原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。