红黑树——动态+静态图
作者 | 陌无崖
转载请联系授权
目录
概念引入折半法二叉查找树AVL红黑树特点维持平衡变化规则变色左旋右旋示例动态旋转
概念引入
假如我们遇到一个猜数字的题，即给定一个序列，猜出该序列中的某个数字。一般该序列是有序的，用户猜出一个数字之后提示该数字是大了还是小了。
折半法
这种方法最容易想到，每次猜出该序列中的中位数，然后将序列分成了两个序列，这样每猜一次，将排除掉一般的数字。
缺点是必须保证序列有序
二叉查找树
使用这种方法我们可以将原始的数据存储到二叉查找树中，在二叉查找树中，任意结点的左子树的值都比该结点小，右子树的值都比该结点大。同样也可以快速定位到某个数字。但是有没有缺点？
当我们建立二叉树的时候，假如我们传入的序列如下：
9,8,7,6,5,4,3,2,1
上述序列构建的二叉树就成为了一个线性的链表，没有右子树。这样查找效率随数据的变化而降低。因此我们需要一种平衡的二叉树，即左右子树的高度相差不大。
AVL
由于二叉查找树的缺点，AVL树解决了上述问题，AVL是一种有着特殊条件的二叉树，即平衡二叉树。它的特点是所有结点的左右子树高度不超过1，由于该二叉树平衡度最高，因此查找的效率也很高，但是同样也带来了新的问题，插入数据和删除消耗时间，因此这种数据结构只能适合较少的插入和删除的应用场景。
红黑树
红黑树是在AVL的基础上进行改进，通过使每个结点有颜色来保证二叉树的平衡。如下图所示：
红黑树
特点
- 每个结点要么是红色，要么是黑色
- 每个红色结点的两个子节点都是黑色
- 根节点永远是黑色
维持平衡
当插入数据的时候，因为不知道该结点会插入到哪个地方，因此也不知道该结点应该是什么颜色。通常我们将结点置为红色，然后再去更正我们的二叉树，为什么还需要更正呢?因为当我们插入一个红色的结点的时候，有可能会打破红黑树的第二个特点，将会出现两个连续的红色的结点。比如上图中插入21：
插入数字21
通常我们有三种方法维持平衡,分别是变色，左旋，右旋。
变化规则
变色
特点
- 当前结点的父亲是红色&& 它的祖父结点是另一个子节点
- 叔叔结点也是红色
规则
- 把父亲变成黑色
- 把叔叔设为黑色
- 把祖父也就是父亲的父亲设置为红色
- 把指针定义到祖父结点，设置为当前要操作的结点
左旋
特点
- 当前的父亲结点时红色，叔叔是黑色的时候，且当前的结点时右子树。
规则
- 左旋以父节点作为左旋
右旋
特点
- 当前的父节点时红色，叔叔是黑色，且当前结点是左子树，右旋
规则
- 把父节点变成黑色
- 把祖父变成红色
- 以祖父结点进行旋转
示例
高清大图可以公众号后台回复红黑树
动态旋转
旋转
关于旋转源码可以进入我的github仓库查看，点击阅读原文进入我的github