一、背景
不管是在阅读 jdk 源码的过程中,还是数据结构的课程学习过程中,亦或是在程序员的面试过程中,红黑树问题都是十分常见的考察数据结构功底的一个典型问题,因此决定一探究竟!
二、二叉查找树 BST
1、定义
- 左子树上所有结点的值均小于等于它的根结点的值
- 右子树上所有结点的值均大于等于它的根结点的值
- 左右子树也分别为二叉排序树
通俗地理解,所谓的二叉查找树,就是“左边小于等于根,右边大于等于根”这样一种树构造逻辑不断递归出来的一种树结构
2、优势
- 在查找时,则刚好是一种对二分查找思想的应用;查找所需的最大次数等同于二叉查找树的高度
- 插入结点时,也是类似于查找时的二分查找思想,通过一层层比较大小,最终找到新节点适合插入的位置
3、劣势
-
但是,主要是在插入新节点的时候:假设是按照待插入的序列本身是有序的如“9,8,7,6,5”且根结点值为 10,那么该二叉查找树就会变成左子树大幅不断延长,几乎就是变成了线性的了
-
即,二叉查找树,随着多次插入新节点而出现了不平衡
-
==>> 重点来了,,,然后就是身为主角的“红黑树”上场了;理所当然,红黑树就是一种自平衡的二叉查找树
三、红黑树 Red Black Tree
1、定义
- 首先红黑树是一个二叉查找树,也即满足二叉查找树的定义为前提条件,扩展的定义是为了保证其具有自平衡特性的
- 节点是红色或黑色
- 根节点是黑色
- 每个叶子节点都是黑色的空节点,即 NIL 节点
- 每个红色节点的两个子节点都是黑色(也即,从每个叶子到根的所有路径上不能有两个连续的红色节点,注意噢“没说黑色节点哈,因此可以出现两个连续的黑色节点”)
- 从任一节点到其每个叶子的所有路径均包含着相同数目的黑色节点
=> 也正是,上述的定义规则保证了红黑树可以具有自平衡的特性:在红黑树中,根结点到叶子结点的最大路径长度不会超过最短路径长度的 2 倍
2、调整
但是,在一般插入或删除节点的时候,红黑树可能会被打乱,导致其不符合其定义中的规则,因此需要做一些调整(变色和旋转【左旋转、右旋转】),以继续保证其仍然符合红黑树的定义规则
3、破坏
什么情况下会破坏红黑树的定义规则?什么情况下不会破坏红黑树的定义规则?
4、变色
也即,试图通过将红色节点变成黑色,或者将黑色节点变成红色,使得其重新满足红黑树的定义条件,这样的一种手段称之为变色
5、旋转
- 左旋转:逆时针旋转红黑树的两个节点,使得父节点被自己的右孩子取代,而自己成为自己的左孩子
- 右旋转:顺时针旋转红黑树的两个节点,使得父节点被自己的左孩子取代,而自己成为自己的右孩子
=> 注意:红黑树的插入和删除,有很多种情况,每一种情况可能都会需要不同的处理方式(详细多种情形,可自行先维基百科中学习!后续再完善添加)
6、应用
- TreeMap
- TreeSet
- HashMap(JDK8)
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于