红黑树学习笔记

这篇文章是红黑树学习过程中的笔记,主要涉及到二叉搜索树、二叉平衡树、2-3树、红黑树,前面的每一种树都存在着各自的缺点,科学家们通过对这些缺点进行改进(现实世界不一定是按照这个顺序、过程来的,这里是我自己的理解,推导的过程),最终得到了红黑树这种数据结构

红黑树是一种高性能的二叉搜索树,提供了在极端情况下,插入、删除、查找都是O(Log(N))的性能,同时也是Java中TreeMap,以及JDK1.8中HashMap用于提高性能的重要实现依据

二叉搜索树

二叉树搜索树(BST,Binary-Search-Tree)是二叉树的一个变种,在存储的时候,每个节点的左节点的值比该节点的值小,右节点的值比该节点的值大,在建立二叉树的时候,通过该策略进行插入节点即可保障该性质的成立

通过该性质,BST可以实现在理想情况下O(Log(N))的查找性能,这里的理想情况是指颗BST是接近平衡的(任意叶子节点到root的距离差不大于1),原因就在于数据完全被打散到各个节点中,并且节点中的顺序已经是维护好了(通过中序遍历即可获得一个递增序)

理想情况下的BST

然而,BST在极端的情况下则会退化为链表,如数据本身就是有序(递增、递减),那么节点的插入会一直发生在最左/最右的位置,因而检索性能会退化为O(N),单数据量稍微大一些的时候,这两者的差距就很明显了,log(1024) = 10,已经接近100倍的差距了

极端情况下的BST

二叉平衡树

二叉检索树的理想情况下的O(Log(N))的检索性能是非常吸引人的,只是在极端情况下容易蜕变成链表,只要能解决这个问题,那么该数据结构就变得非常好用了

常用的解决方式是通过“平衡”的方式,将一颗不平衡的树通过某些操作在不违背该树的性质的情况下转换为平衡的树,那么问题就能得到解决了

常用的平衡操作是旋转,将某节点的左节点作为自己的父节点,自己成为该节点的右节点(右旋),或者将该树的右节点作为自己的父节点,自己成为该节点的左节点(左旋),如下图所示

右旋

左旋

二叉平衡树(AVL)就是通过旋转操作来实现“平衡”的一种二叉树,BST结合平衡操作就能构造出理想的BST,该BST在极端情况下也能达到O(Log(N))的检索性能

然而AVL也有比较明显的缺点,AVL为了实现平衡,定义了平衡的概念:任意叶子节点到root的距离差不大于1,这也就意味着,当某一个分支插入节点之后,不满足平衡条件时,就需要进行旋转操作,而基本上所有的插入操作都会导致旋转,这会带来严重的问题,为了平衡而实现的平衡操作,占据了大部分的操作时间,几乎抵消了平衡本身多带来的优势了

2-3树

虽然AVL理想情况下非常的完美,但是由于AVL的旋转操作带来太大的性能损耗了,使得AVL本身并不太适合用于实际的使用,这也恰恰是AVL能够改进的地方,既然旋转的频率太高而带来性能损耗,那么不用旋转,而采用其他方式来实现就可以了,2-3树就是这样的一种数据结构

注:由于下面的图实在是太难画了,囧,下面出现的图来自《Algorithm 4th》里头的图,向作者大大表示感谢:),作者的图画得真的超级好看,手残党表示非常羡慕了

2-3树通过定义两种类型的节点:两个分叉的节点(2节点)、三个分叉的节点(3节点),并且通过节点之间的转换来实现树本身的平衡,从而抵消AVL频繁旋转带来的消耗

2-3树

2-3的平衡操作有两种

  1. 节点分裂

    节点分裂,目标节点是3节点时(插入后新元素后变成4节点),进行节点分裂,将一个3节点分裂成两个2节点(中间元素向上合并到父节点中)

    节点分裂

  2. 节点合并

    1. 当插入节点时,如果当前父节点是2节点,则将其转换为3节点,并且将新元素放在该节点即可

      节点合并-父节点是2节点

    2. 当目标节点是3节点,并且父节点时2节点时,当前3节点分裂,并且中间的元素合并到父节点(等价于拆分当前节点,然后往父节点插入元素,向上重复操作,只是插入操作变成了父节点)

      节点分裂并且合并到父节点

    其他的情况都是上面三种情况的重复,比如父节点是三节点,子节点也是三节点,此时依次往上拆分、合并即可

    2-3树节点变化情况

通过2-3树的拆分、合并操作,同样能使得树达到平衡状态,这个非常直观,也挺好证明的:

假设原先的2-3树是平衡树(0(nil)、1(2节点)、2(3节点)元素)

当2节点插入元素时,树高保持不变,所以树是平衡的

当3节点插入元素时:

​ 如果父节点是2节点,拆分当前3节点,并且合并中间元素到父节点,此时树高没有发生变化,所以树是平衡的

如果父节点是3节点,拆分当前3节点,并且将中间元素合并到父节点,父节点继续向上完成该操作,此时如果每个父节点都是3节点,则root会拆分,形成新的左右两个节点,此时树高+1,但树本身依旧是平衡的

由此可以证明,2-3树和AVL一样,都是平衡的,然而,事情到这里并没有结束,2-3树的操作实在是太复杂了,一会2节点‘一会3节点的,还各种合并、分裂,维护起来特别复杂,所以实际上的应用中,也没有使用2-3树作为平衡树使用

红黑树

由于AVL、2-3树本身要么是操作太多,导致插入性能不佳,要么是操作复杂,不实际,因此科学家们想出了一种新的等效方案,红黑树

红黑树是2-3树的一个等效方案,或者说,红黑树是AVL与2-3树完美融合的一个实现,既保障了性能、实现起来也不太复杂(其实也非常复杂,囧…..)

红黑树的特性:

  1. 每个节点有两种颜色:黑色、红色,分别对应2-3树中的2节点、3节点
  2. 根节点是黑色的
  3. 从根节点出发到叶子节点,每条路径下没有相邻的两个红色节点(2-3树节点拆分、合并操作,通过AVL的旋转以及红黑树自身的变色操作进行等效变换)
  4. 从根节点触发到叶子节点,每个节点路径上的黑色节点个数相同(“平衡树”)

红黑树通过红黑节点来替代2-3树中的2、3节点,然后通过旋转、变色来替换2-3树的节点分裂、合并

从本质上来说,红黑树是2-3树

红黑树、2-3树的等价变换

红黑树、2-3树的等价变换

(上面的红色连接表示的左端表示的是红节点,将红色连接链接的节点合并在一起,并且消除红色连接,则可以得到对应的2-3树),由于2-3树是平衡的,所以红黑树也是平衡的

从上面可以看到,红色节点其实是由2-3树中的3节点拆分得到,因此,2-3树中的2-3节点可以规约为一种节点,并且通过颜色变换来得到

《Algorithm 4th》中,作者规定了在等效的红黑树中,红色线条只能出现在左侧,而不能出现在右侧,其实是可以出现在右侧的,但是一棵树中,只能同时存在一个方向,要么都在左侧,要么都在右侧,这里同样约定只能出现在左侧

默认插入的节点都是红色节点,于是乎,会得到下面几种插入的情况

  1. 插入到单个节点的某一侧(相当于2-3树中的新插入节点)

    1. 插入到左侧,满足情况,无需任何变化
    2. 插入到右侧,违背了红色只能在左侧的情况,通过旋转进行调整

    插入到单节点

  2. 插入到2节点(等效2-3树的2节点,前面提到的)的某一侧

    1. 插入到左侧,同样满足
    2. 插入到右侧,不满足,通过旋转调整

    插入到2节点中

  3. 插入到3节点的某一侧(前面提到的2-3树3节点的特性)

    1. 最左侧
      1. 父节点是黑色的,满足约束
      2. 父节点是红色的,违背了同一路径不能有两个相邻的红色节点,通过旋转,变色解决
    2. 中间,由于中间节点等效变换后,插入会直接在右侧,所以一定不满足,通过旋转,转换为1的形式,通过1的解决方式进行解决
    3. 最右侧,等效于2,通过2的方式进行解决

可以看到,2-3树的插入操作,可以通过红黑树进行完美的等效变化,红黑树的各个状态转换也能进行有效规约,因此,状态本身不存在膨胀情况,状态转换图如下

红黑树插入节点时,状态转换图

作者

大黄蜂

发布于

2020-12-06

更新于

2021-04-28

许可协议