概念引入

假如我们遇到一个猜数字的题,即给定一个序列,猜出该序列中的某个数字。一般该序列是有序的,用户猜出一个数字之后提示该数字是大了还是小了。

折半法

这种方法最容易想到,每次猜出该序列中的中位数,然后将序列分成了两个序列,这样每猜一次,将排除掉一般的数字。

缺点是必须保证序列有序

二叉查找树

使用这种方法我们可以将原始的数据存储到二叉查找树中,在二叉查找树中,任意结点的左子树的值都比该结点小,右子树的值都比该结点大。同样也可以快速定位到某个数字。但是有没有缺点?

当我们建立二叉树的时候,假如我们传入的序列如下:

1
9,8,7,6,5,4,3,2,1

上述序列构建的二叉树就成为了一个线性的链表,没有右子树。这样查找效率随数据的变化而降低。因此我们需要一种平衡的二叉树,即左右子树的高度相差不大。

AVL

由于二叉查找树的缺点,AVL树解决了上述问题,AVL是一种有着特殊条件的二叉树,即平衡二叉树。它的特点是所有结点的左右子树高度不超过1,由于该二叉树平衡度最高,因此查找的效率也很高,但是同样也带来了新的问题,插入数据和删除消耗时间,因此这种数据结构只能适合较少的插入和删除的应用场景。

红黑树

红黑树是在AVL的基础上进行改进,通过使每个结点有颜色来保证二叉树的平衡。如下图所示:
红黑树

特点

  • 每个结点要么是红色,要么是黑色
  • 每个红色结点的两个子节点都是黑色
  • 根节点永远是黑色

维持平衡

当插入数据的时候,因为不知道该结点会插入到哪个地方,因此也不知道该结点应该是什么颜色。通常我们将结点置为红色,然后再去更正我们的二叉树,为什么还需要更正呢?因为当我们插入一个红色的结点的时候,有可能会打破红黑树的第二个特点,将会出现两个连续的红色的结点。比如上图中插入21:
插入数字21

通常我们有三种方法维持平衡,分别是变色,左旋,右旋。

变化规则

变色

特点

  • 当前结点的父亲是红色&& 它的祖父结点是另一个子节点
  • 叔叔结点也是红色

规则

  • 把父亲变成黑色
  • 把叔叔设为黑色
  • 把祖父也就是父亲的父亲设置为红色
  • 把指针定义到祖父结点,设置为当前要操作的结点

左旋

特点

  • 当前的父亲结点时红色,叔叔是黑色的时候,且当前的结点时右子树。

规则

  • 左旋以父节点作为左旋

右旋

特点

  • 当前的父节点时红色,叔叔是黑色,且当前结点是左子树,右旋

规则

  • 把父节点变成黑色
  • 把祖父变成红色
  • 以祖父结点进行旋转

示例

高清大图可以公众号后台回复红黑树

动态旋转

旋转