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