数据结构与算法笔记(四)

平衡二叉树

二叉查找树支持快速插入、删除、查找操作,各个操作时间跟树的高度成正比,理想情况下,时间复杂度为 O(logn)。但是,在极端的情况下,二叉树会退化成链表(比如按顺序插入一组数据),时间复杂度会退化到 O(n)

为了解决这种问题,就有了平衡二叉树,红黑树就是平衡二叉树中的一种。

平衡二叉树的严格定义:二叉树中任意一个节点的左右子树的高度差不能大于 1。示意图如下:

最先被发明的平衡二叉查找树是 AVL 树,它严格符合上述定义,是一种高度平衡的二叉查找树。但是,很多平衡二叉查找树并未严格符合上述定义,比如经典的红黑树。

PS: 平衡二叉树发明的初衷是为了解决普通二叉查找树在极端情况下退化成链表,插入、删除等操作复杂度增加的问题。而“平衡”的意思就是让整棵树的左右子树比较均衡,从而使整棵树的高度相对低一些,插入、删除等操作效率更高。因此,尽管有些二叉树没有严格符合平衡二叉查找树的定义,但只要树的高度没有比 logn 大很多,仍然可以认为它是一棵平衡二叉树。

红黑树

红黑树(Red-Black Tree),简称 R-B Tree,它的每个节点都有颜色(红与黑)属性,是“出场率”很高的二叉树,它是一种不严格的平衡二叉树。示意图如下:

红黑树需要满足以下几个约束:

1. 节点是红色或黑色;

2. 根节点是黑色;

3. 所有叶子节点都是黑色(叶子是 NIL 节点);

4. 每个红色节点必须有两个黑色的子节点(从每个叶子到根节点的所有路径上不能有两个连续的红色节点);

5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

PS: 上面说的“叶节点”或“NIL节点”,不包含数据而只是充当树在此结束的指示,绘图中通常被省略。

平衡性调整

红黑树在插入删除节点的过程中,上述第 3、4 点性质可能会被破坏,为了让它重新保持红黑树的性质,需要进行平衡性调整。

平衡性调整操作主要包括旋转(结构调整)和着色(红黑转换),其中旋转又分为左旋(rotate left)和右旋(rotate right)两个操作,左旋指的是围绕某个节点的左旋,右旋同理。左旋和右旋的操作示意图如下:

插入操作

红黑树规定,插入的节点必须是红色的。插入的情况分为多种,下面两种情况无须进行旋转操作:

1. 若插入节点的父节点是黑色的,则无需操作,仍满足红黑树的定义;

2. 若插入节点是根节点,那么直接将它变为黑色即可。

除此之外的其他情况都会违背红黑树的定义,需要进行平衡性调整(旋转和着色)。

case1

关注节点为 a,它的叔叔节点 d 为红色。则进行如下操作:

1. 将 a 的父节点 b、叔叔节点 d 的颜色都设置为黑色;

2. 将 a 的祖父节点 c 的颜色设置为红色;

3. 关注节点变成 a 的祖父节点 c;

4. 跳到 case2 或 case3。

操作示意图如下:

case2

关注节点是 a,它的叔叔节点 d 是黑色,a 是其父节点 b 的右子节点。则进行如下操作:

1. 关注节点变成 a 的父节点 b;

2. 围绕 b 左旋;

3. 跳到 case3。

操作示意图如下:

case3

若关注节点是 a,它的叔叔节点 d 是黑色,a 是其父节点 b 的左子节点。则进行如下操作:

1. 围绕 a 的祖父节点 c 右旋;

2. 将 a 的父节点 b、兄弟节点 c 的颜色互换。

操作示意图如下:

小结:插入后的修复操作是一个向 root 节点回溯的操作过程,一旦涉及的节点都符合了红黑树的定义,则修复操作结束。之所以会向上回溯是由于 case1 操作会将父节点、叔叔节点和祖父节点的颜色进行互换,可能会导致祖父节点不平衡,此时需要对祖父节点进行修复,以此类推。

删除操作

若删除的是叶子节点就直接删除;若不是叶子节点,会用对应的中序遍历的后继节点来顶替要删除的节点的位置。

删除操作的总体思想:从兄弟节点借调黑色节点使树保持局部的平衡,如果局部的平衡达到了,就看整体的树是否平衡,若不平衡则继续向上追溯调整。

删除节点的平衡性调整大概分为四种情况(对称情况下的操作类似):

case1

待删除节点的兄弟节点是红色。则进行如下操作:

1. 围绕父节点 A 进行左旋;

2. 将父节点 A 和祖父节点 C 颜色互换;

3. 跳转到 case2、case3 或 case4。

操作示意图如下:

case2

待删除节点的兄弟节点是黑色,且兄弟节点的子节点都是黑色。则进行如下操作:

1. 将兄弟节点 C 的颜色设置为红色;

2. 关注节点上溯为父节点 A。

操作示意图如下:

case3

待调整节点的兄弟节点是黑色,且左子节点是红色、右子节点是黑色(兄弟节点在右边的情况。若兄弟节点在左边,就是右子节点是红色,左子节点是黑色)。则进行如下操作:

1. 围绕兄弟节点 C 右旋;

2. 将节点 C 和 D 变换颜色;

3. 跳到 case4。

操作示意图如下:

case4

待调整节点的兄弟节点是黑色,且右子节点是红色、左子节点是黑色(兄弟节点在右边的情况。若兄弟节点在左边,就是左子节点是红色、右子节点是黑色)。则进行如下操作:

1. 围绕父节点 A 进行左旋;

2. 删除 B 节点。

操作示意图如下:

删除修复操作是针对删除黑色节点才有的,需要从兄弟节点上借调黑色的节点过来,如果兄弟节点没有黑色节点可以借调的话,就只能向上追溯。

小结

红黑树是一种常见的平衡二叉树,结构稍微复杂了点,主要体现在插入和删除的时候需要进行旋转和变色的平衡性调整操作。

在 JDK 1.8 的源码中,TreeMap 和 HashMap 都用到了红黑树,以后打算根据相关代码做分析。

主要参考内容: 1. 极客专栏 2. https://zh.wikipedia.org/zh-hans/%E7%BA%A2%E9%BB%91%E6%A0%91 3. https://tech.meituan.com/2016/12/02/redblack-tree.html

相关阅读

数据结构与算法笔记(三)

Stay hungry, stay foolish.

本文分享自微信公众号 - WriteOnRead(WriteOnRead)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-04-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏灵魂画师牧码

图文详解二叉堆,实现优先级队列

二叉堆(Binary Heap)没什么神秘,性质比二叉搜索树 BST 还简单。其主要操作就两个,sink(下沉)和swim(上浮),用以维护二叉堆的性质。其主要...

10310
来自专栏方丈的寺院

初级算法-树

树的大部分问题都可以通过递归解决,即求一个树的某个值可以转化为求左子树/右子树的值

6520
来自专栏完美Excel

基础扩展 | 21. 遍历二叉树

二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中的所有结点,使得每个结点被访问一次且仅被访问一次。下面,以图1所示的二叉树为例,讲解二叉树的前序遍历、...

9840
来自专栏牛客网

字节跳动 深圳抖音 提前批前端 三面+HR面 已拿意向书

emmm  7.17提前批截止的前一天投递的简历 7.28hr面加意向书  秋招第一个offer

51940
来自专栏算法工程师之路

二叉树遍历的应用:判断二叉树的类别

昨天的文章讲述了二叉树的先序、中序和后序的遍历方法(递归和非递归),但是这种遍历方法有什么意义么?今天来讲讲这些算法可以用来做什么,只要稍加更改,我们就可以得到...

12920
来自专栏海仔技术驿站

java实现数据结构

一.数据结构和算法简介 数据结构是指数据在计算机存储空间中的安排方式,而算法时值软件程序用来操作这些结构中的数据的过程. 二. 数据结构和算法的重要性 几...

20970
来自专栏完美Excel

基础扩展 | 20. 建立二叉树

先看看下图1所示的一棵完全二叉树,图中标出了结点的内容、结点编号以及上下层子树之间的关系。

13320
来自专栏linux驱动个人学习

图解数据结构树之AVL树

AVL树本质上是一颗二叉查找树,但是它又具有以下特点:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。在AVL树中任...

8510
来自专栏算法工程师之路

面试中的排序算法(Part 3)

今天来谈一种十分重要的堆排序的算法,其在STL中的数据结构也就是Priority_Queue。也是一种十分高效的排序方式,虽然其算法模型为二叉树结构,但是可以使...

7230
来自专栏算法工程师之路

聊聊二叉树的遍历(递归和非递归)

二叉树也是常用的数据结构,通过使用二叉树可以快速的对数据进行排序或者查找,在常用的堆排序算法中,堆的底层实质就是一个模拟的完全二叉树!等等,什么是完全二叉树?二...

20330

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励