专栏首页业余草动图展示,让你彻底理解红黑树!

动图展示,让你彻底理解红黑树!

你知道的越多,不知道的就越多,业余的像一棵小草!

你来,我们一起精进!你不来,我和你的竞争对手一起精进!

编辑:业余草

来源:cnblogs.com/linzworld/p/13720477.html

推荐:https://www.xttblog.com/?p=5112

二叉树

满足以下两个条件的树就是二叉树:

  • 本身是有序树(若将树中每个结点的各子树看成是从左到右有次序的(即不能互换),则称该树为有序树(Ordered Tree))。
  • 树中包含的各个节点的度不能超过 2,即只能是 0、1 或者 2。

简单地理解,二叉树(Binary tree)是每个节点最多只有两个分支(即不存在分支度大于 2 的节点)的树结构。通常分支被称作“左子树”或“右子树”。

二叉查找树

要了解红黑树之前,免不了先看下二叉查找树是什么。

维基百科上的定义:二叉查找树(英语:Binary Search Tree),也称为二叉搜索树、有序二叉树(ordered binary tree)或排序二叉树(sorted binary tree),是指一棵空树或者具有下列性质的二叉树。

若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;若任意节点的右子树不空,则右子树上所有节点的值均大于或等于它的根节点的值;任意节点的左、右子树也分别为二叉查找树。

图示理解:

上图为查找值为29的节点,有以下步骤:

  • 查看根节点 41。
  • 因为 41>29,所以查看 41 的左孩子 20。
  • 因为 20<29,所以查看 20 的右孩子 29,发现其正好是要查看的节点。

退化

二叉查找树有个非常严重的问题,如果数据的插入是从大到小插入的,或者是从小到大插入的话,会导致二叉查找树退化成单链表的形式,俗称“瘸子“。

左瘸子:例如,插入数据依次为 {5,4,3,2,1}(从大到小),则如下图所示:

右瘸子:例如,插入数据依次为{1,2,3,4,5}(从小到大),则如下图所示:

为了解决该问题,出现了一些解决方法,即平衡,能够使得树趋向平衡,这种自平衡的树叫做平衡树。

平衡树

平衡树(Balance Tree,BT)指的是,任意节点的子树的高度差都小于等于 1。

常见的符合平衡树的有 AVL 树(二叉平衡搜索树),B 树(多路平衡搜索树,2-3 树,2-3-4 树中的一种),红黑树等。

AVL 树

AVL 树(由发明者 Adelson-Velsky 和 Landis 的首字母缩写命名),是指任意节点的两个子树的高度差不超过 1 的平衡树。又称自平衡二叉搜索树。

AVL 树能解决上文二叉查找树中的右瘸子问题,例如,插入数据依次为 {1,2,3,4,5}(从小到大),则如下图所示:

AVL 树会对不符合高度差的结构进行调整,从而使得二叉树趋向平衡。

2-3 树

2-3 树,是指每个具有子节点的节点(内部节点,internal node)要么有两个子节点和一个数据元素,要么有三个子节点和两个数据元素的自平衡的树,它的所有叶子节点都具有相同的高度。

简单点讲,2-3 树的非叶子节点都具有两个分叉或者三个分叉,所以,称作 2 叉-3 叉树更容易理解。

另外一种说法,具有两个子节点和一个数据元素的节点又称作 2 节点,具有三个子节点和两个数据元素的节点又称作 3 节点,所以,整颗树叫做 2-3 树。

所有叶子点都在树的同一层,一样高:

  • 性质 1:满足二叉搜索树的性质。
  • 性质 2:节点可以存放一个或两个元素。
  • 性质 3:每个节点有两个或三个子节点。

创建 2-3 树的规则

插入操作如下:

向 2-节点中插入元素:

向一颗只含有一个 3-节点的树中插入元素:

2-3-4 树

含义如下:

  • 2 节点:包含两个子节点和一个数据元素。
  • 3 节点:包含三个子节点和一个数据元素。
  • 4 节点:包含四个子节点和一个数据元素。

2-3-4 树,它的每个非叶子节点,要么是 2 节点,要么是 3 节点,要么是 4 节点,且可以自平衡,所以称作 2-3-4 树。

规则如下:

  • 规则 1:加入新节点时,不会往空的位置添加节点,而是添加到最后一个叶子节点上。
  • 规则 2:四节点可以被分解三个 2-节点组成的树,并且分解后新树的根节点需要向上和父节点融合。

插入操作

原本的 2-3-4 树,如下图:

对于上图的 2-3-4 树,插入一个节点 17,由于规则 1,节点 17 不会加入节点 [16,18,20] 的子树,而是与该节点融合。

由于规则 2,节点 [16,17,18,20] 是一个 4 节点,将该节点进行拆解成新的树,将 18 作为子树的根节点进行拆分。

此时树暂时失去了平衡,我们需要将拆分后的子树的根节点向上进行融合。

同理可得,由于规则 2,节点 [6,10,14,18] 是一个 4 节点,将该节点进行拆解成新的树,将 14 作为子树的根节点进行拆分,完成了 2-3-4 树的构建。

总结了下插入节点的过程,无非也就为了符合两条规则,那么,2-3 树,2-3-4 树都有了,那是不是也有 2-3-4-5 树,2-3-4-5--...-n 树的存在呢?

事实上是有的,世人把这一类树称为一个名字:B 树。

B 树

B 树,表示的是一类树,它允许一个节点可以有多于两个子节点,同时,也是自平衡的,叶子节点的高度都是相同的。

所以,为了更好地区分一颗 B 树到底属于哪一类树,我们给它一个新的属性:度(Degree):一个节点能有多少箭头指向其他节点。

具有度为 3 的 B 树,表示一个节点最多有三个子节点,也就是 2-3 树的定义。具有度为 4 的 B 树,表示一个节点最多有四个子节点,也就是 2-3-4 树的定义。

图为 4 的 B 树的示例图:

红黑树

R-B Tree,全称是 Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树。

红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black)。

如何理解红黑树

一个经典的红黑树,如下图所示(省略了叶子节点都是黑色的 NIL 节点):

如第二张图所示,将该红黑树与上文讲到的 2-3-4 树对比,是否发现,红黑树就是一个 2-3-4 树:

  • 每个节点或者是黑色,或者是红色。
  • 根节点是黑色。
  • 每个叶子节点(NIL)是黑色。注意:这里叶子节点,是指为空(NIL 或NULL)的叶子节点!
  • 如果一个节点是红色的,则它的子节点必须是黑色的。由于红黑树的每个节点都是由 2-3-4 树转化而来的,从而红色节点不能连续两个出现,不然会出现 4 节点的情况,导致违反了规则 2。 而且红黑树的每一个黑节点都是 3 节点中的最中间的那个值,或者是 2 节点中其中一个值。
  • 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

原因:红黑树这些黑色节点在 2-3-4 树中代表的是由 1 节点的一个 2-3-4 树,而 2-3-4 树是同一个子树的深度是相同的,平衡的,所以从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

如下图所示,蓝色代表是黑色节点:

注意如下几点:

  • 特性(3)中的叶子节点,是只为空(NIL 或 null)的节点。
  • 特性(5),确保没有一条路径会比其他路径长出俩倍。因而,红黑树是相对是接近平衡的二叉树。
  • 红黑树虽然本质上是一棵二叉查找树,但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡,从而保证了红黑树的查找、插入、删除的时间复杂度最坏为 O(log n)。

由上面的例子所示,我们只要把红黑树当做是 2-3-4 树来处理,并且对应的颜色进行改变或者进行左旋右旋的操作,即可达到使得红黑树平衡的目标。

如何保持红黑树的结构

当我们插入一个新的节点的时候,如何保证红黑树的结构依然能够符合上面的五个特性呢?

树的旋转分为左旋和右旋,下面借助图来介绍一下左旋和右旋这两种操作。

①左旋

原本的状态:

过程图:

结束图:

如上图所示,当在某个目标结点 E 上,做左旋操作时,我们假设它的右孩子 S 不是 NIL。

左旋以 S 到 E 之间的链为“支轴”进行,它使 S 成为该子树的新根,而 S 的左孩子则成为 E 的右孩子。

②右旋

原先状态图:

过程图:

结束图:

同左旋类似,当在某个目标结点 S 上,做右旋操作时,我们假设它的右孩子 S 不是 NIL。

左旋以 S 到 E 之间的链为“支轴”进行,它使 S 成为该子树的新根,而 S 的左孩子则成为 E 的右孩子。

应用

红黑树的应用比较广泛,主要是用它来存储有序的数据,它的时间复杂度是 O(logn),效率非常之高。

例如,Java 集合中的 TreeSet 和 TreeMap,C++ STL 中的 set、map,以及 Linux 虚拟内存的管理,都是通过红黑树去实现的。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 3主3从,Redis 集群搭建指南

    网上有很多文章讲 Redis 集群的,但是真正用来实战的很少。纯理论的文章看的太多了,缺乏实战。今天抽个时间,我们来把理论是实践一锅端了吧!

    业余草
  • Java HTTP Host 头攻击原理以及如何防御

    很对微信群里的网友,我都称他们为老铁,从来不称兄道弟的,因为我觉得不真实。不向某东,说一套做一套。

    业余草
  • 不讲武德,Java分布式面试题集合含答案!

    分布式分为分布式缓存(Redis)、分布式锁(Redis 或 Zookeeper)、分布式服务(Dubbo 或 SpringCloud)、分布式服务协调(Zoo...

    业余草
  • ignite TCP发现原理

    节点顺序 - 每个节点的内部属性(对于TcpDiscoverySpi,它只是一个统一增加的数字)。

    lilihongjava
  • 《Redis设计与实现》读书笔记(二十八) ——Redis集群节点结构与槽分配

    《Redis设计与实现》读书笔记(二十八) ——Redis集群节点结构与槽分配 (原创内容,转载请注明来源,谢谢) 一、概述 redis集群是...

    用户1327360
  • 数据结构:树与二叉树

    一颗高度为h,并含有2^h-1个节点的二叉树称为满二叉树,即树中的每一层都含有最多的节点。

    HLee
  • 《Redis设计与实现》读书笔记(三十) ——Redis集群节点复制与故障转移

    《Redis设计与实现》读书笔记(三十) ——Redis集群节点复制与故障转移 (原创内容,转载请注明来源,谢谢) 1、概述 redis集群的...

    用户1327360
  • 红黑树算法

    前情提要 红黑树是AVL树里最流行的变种,有些资料甚至说自从红黑树出来以后,AVL树就被放到博物馆里了。红黑树是否真的有那么优秀,我们一看究竟。红黑树遵循以下...

    机器学习算法工程师
  • 多叉树 & B树 & B+树 & B*树

    二叉树虽然操作效率比较高,但是如果数据一多,就会有好多好多的节点,需要进行好多次的I/O操作,构建出来的二叉树就会很高很高,也会降低操作速度。

    贪挽懒月
  • 像管理 Pod 一样管理 Node | TKE 节点池全面上线

    晏子怡,腾讯云产品经理,目前负责TKE集群、网络及调度模块。 从 K8s 的声明式设计理念谈起 Pod 模板 K8s 最优雅精妙的一个设计理念在于声明式  A...

    腾讯云原生

扫码关注云+社区

领取腾讯云代金券