数据结构Java版之红黑树（八）

红黑树是一种自动平衡的二叉查找树，因为存在红黑规则，所以有效的防止了二叉树退化成了链表，且查找和删除的速度都很快，时间复杂度为log(n)。

什么是红黑规则？

1.根节点必须是黑色的。

2.节点颜色要么是红要么是黑。

3.树的每一个分叉存在相同黑色节点。

4.不允许存在两个连续的红色节点。

为不断适应红黑规则，在写程序中如何调整？

1.旋转

---单旋转

外侧节点单旋转。外侧节点指的是左子树的左孩子节点，右子树的右孩子节点。

---双旋转

内侧节点双旋转。内侧节点指的是左子树的右孩子节点，右子树的左孩子节点。

2.变色

---节点颜色进行更改。

---强制将根节点颜色变为黑色。

博文参考链接：http://www.cnblogs.com/skywang12345/p/3245399.html　　（红+黑节点指的是父节点红色，当前节点黑色。黑+黑是父节点黑色，当前节点黑色。前面的颜色可看做是通过继承来的）。