算法精学--红黑树
红黑树小窥！
一、红黑树发展
- 二叉查找树可以提高查找的效率，但是最坏的情况下可能会退化为链表查找。平衡二叉树是高度平衡的，但是每一次插入和删除都可能引起旋转。因此引入红黑树。
- 查找红黑树是一种自平衡的二叉查找树，是一种数据结构。
- 1972年出现，当时被称为平衡二叉B树，1978年改为“红黑树”。
- 是一种特殊的二叉查找树，红黑树上面的每一个节点都有存储位表示节点的颜色。
- 每一个节点是红或者黑；红黑树不是高度平衡的，它的平衡是通过“红黑规则”进行实现的。
二、红黑树规则
- 每一个节点是红或者黑。
- 根节点必须是黑色的。
- 如果一个节点没有子节点，则该节点应该将指针的属性值设置为Nil，这些Nil视为叶节点，每一个叶节点(Nil)是黑的。
- 如果一个节点是红的，则它的子节点必须是黑的，即不能出现两个红色节点相连的情况。
- 对于一个节点，从该节点到其后代的叶节点的简单路径上，均含有相同数量的黑色节点。
三、红黑树的插入规则
- 根节点，直接设置为黑色
- 非根节点
- 父为黑色节点， 不需要进行任何操作
- 父为非黑色节点
- 叔叔为红色节点
- 将父节点设置为黑色，将叔叔设置为黑色
- 将祖父设置为红色
- 如果祖父为根，再将根变成黑色
- 如果祖父为非根，将祖父设置为当前节点再进行其他判断
- 叔叔为黑色节点，当前节点是父的右孩子
- 将父节点作为当前节点并左旋，再进行判断
- 叔叔为黑色节点，当前节点是父的左孩子
- 将父节点设置为黑色
- 将祖父节点设置为红色
- 以祖父为支点进行右旋
- 叔叔为红色节点