乐趣区

关于后端:了解红黑树的起源理解红黑树的本质

前言

本文收录于专辑:http://dwz.win/HjK,点击解锁更多数据结构与算法的常识。

你好,我是彤哥。

后面两节,咱们一起学习了对于跳表的理论知识,并手写了两种齐全不同的实现,咱们放一张图来简略地回顾一下:

实现跳表的要害之处是在有序链表的根底上加上各层索引,通过这些索引能够做到 O(log n)的工夫复杂度疾速地插入、删除、查找元素。

说起跳表,咱们就不得不提另一种十分经典的数据结构——红黑树,红黑树绝对于跳表来说,尽管工夫复杂度都是 O(log n),然而红黑树的应用场景绝对更宽泛一些,在晚期的 Linux 内核中就始终存在红黑树的实现,也使用在了更高效的多路复用器 Epoll 中。

所以,红黑树是每一个程序员不得不会的知识点,甚至有些变态的面试官,还会让你手写红黑树的一部分实现,比方左旋、右旋、插入均衡的过程、删除均衡的过程,这些内容非常复杂,靠死记硬背往往很难彻底把握。

彤哥也是始终在寻找一种红黑树的记忆法,总算让我找到了那么一种还算不错的形式,从红黑树的起源登程,了解红黑树的实质,再从实质登程,彻底把握不必死记硬背的办法,最初再把它手写进去。

从本节开始,我也将把这种办法传递给你,因而,红黑树的局部,我会分成三个大节来解说:

  • 从红黑树的起源,到红黑树的实质
  • 从红黑树的实质,找到不必死记硬背的办法
  • 不靠死记硬背,手写红黑树

好了,上面咱们就进入第一大节。

红黑树的起源

二叉树

说起树,咱们不得不说最有名的树,那就是二叉树,什么是二叉树呢?

二叉树(binary tree),是指树中的每个节点最多只有两个子节点的树。

当然,二叉树自身仿佛没什么用,咱们平时说的二叉树基本上都是指二叉查找树,或者叫有序二叉树、二叉搜寻树、二叉排序树。

二叉查找树

二叉查找树(BST,binary search tree),就是在二叉树的根底上减少有序性,这个有序性个别是指天然程序,有了有序性,咱们就能够应用二叉树来疾速的查找、删除、插入元素了。

比方,下面这颗二叉查找树,查找元素的均匀工夫复杂度为 O(log n)。

然而,二叉查找树有个十分重大的问题,试想,还是这三个元素,如果依照 A、B、C 的程序插入元素会怎么?

这是啥?单链表?没错,当依照元素的天然程序插入元素的时候,二叉查找树就进化成单链表了,单链表的插入、删除、查找元素的工夫复杂度是多少?O(n)。

所以,在极限状况下,二叉查找树的工夫复杂度是十分差的。

既然,插入元素后有可能导致二叉查找树的性能变差,那么,咱们是否能够减少一些伎俩,让插入元素后的二叉查找树仍然性能良好呢?

答案是必定的,这种伎俩就叫做 均衡,这种能够自均衡的树就叫做均衡树。

均衡树

均衡树(self-balancing or height-balanced binary search tree),是指插入、删除元素后能够自均衡的二叉查找树,使得它的工夫复杂度能够始终渐近于 O(log n)。

比方,下面那颗树,按 A、B、C 插入元素后,做一次旋转操作,就能够再次变成查找时间复杂度为 O(log n)的树。

然而,均衡树始终只是一个概念,直到 1962 年才由两个苏联人创造了第一种均衡树——AVL 树。

严格来说,均衡树是指能够自均衡的二叉查找树,三个关键词:自均衡、二叉、查找(有序)。

AVL 树

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

比方,下面这颗树,就是一颗 AVL 树,不信你能够数数看,是不是每个节点的两个子树的高度差都不超过 1。

是不是很难发现它真的是一颗 AVL 树,没错,这是 AVL 树的第一个毛病,不够直观,特地是节点个数多的时候。

第二个毛病,就是插入、删除元素的时候自均衡的过程非常复杂,比方,下面这颗树插入一个节点T

咱们从 T 往上找,它的父节点 U,U 的两颗子树的高度差为 1,满足 AVL 树的规定,再往上,S 的两颗子树的高度差为 1,也满足规定,再往上,V 的两颗子树的高度差为 2,不满足规定,此时,须要一个自均衡的过程,该如何自均衡呢?

我上面给出图示,你能够试着了解一下:

红色节点示意旋转的轴。

通过两次旋转,让这颗树再次变成了 AVL 树,而且这只是其中一种插入场景,实在的状况还要依据插入的地位的不同做不同的旋转,你能够多插入几个节点本人尝试均衡一下。

同样地,AVL 树的代码也不是那么好实现的,反正,到目前为止,彤哥是没搞懂 AVL 树的各种规定。

基于这些毛病,所以,起初又倒退进去了各种各样的神奇的均衡树。

2- 3 树

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

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

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

2- 3 树,插入元素后自均衡的过程绝对于 AVL 树就要简略得多了,比方,下面这颗树,再插入一个元素 K,它会先找到 I J 这个节点,插入元素 K,造成长期节点 I J K,不合乎 2 - 3 树的规定,所以决裂,J 往上移,F H这个节点变成了 F H J 了,也不合乎 2 - 3 树的规定,持续上移H,根节点变为D H,同时,上移的过程中,子节点也要相应的决裂,过程大抵如下:

画图辛苦了,关注一波:彤哥读源码。

能够看到,下面自均衡的过程中,呈现了一种节点,它具备四个子节点和三个数据元素,这个节点能够称作 4 节点,如果把 4 节点当作是能够容许存在的,那么,就呈现了另一种树:2-3- 4 树。

2-3- 4 树

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

2 节点、3 节点、4 节点的定义在下面曾经提及,咱们再重申一下:

2 节点:蕴含两个子节点和一个数据元素;

3 节点:蕴含三个子节点和两个数据元素;

4 节点:蕴含四个子节点和三个数据元素;

当然,2-3- 4 树插入元素的过程也很好了解,比方,下面这颗树,插入元素 M,找到 K L 这个节点,插入即可,造成 4 节点,满足规定,不须要自均衡:

再插入元素 N 呢?过程与 2 - 3 树一样,向上决裂即可,此时,两头节点有两个,取任意一个上移都是能够的,咱们这里以左中节点上移为例,大抵过程如下:

是不是挺简略的,至多比 AVL 树那种左旋右旋简略得多。

同样地,在 2 -3- 4 树自均衡的过程中呈现了长期的 5 节点,所以,如果容许 5 节点的存在呢?

嗯,2-3-4- 5 树由此诞生!

同样地,还有 2 -3-4-5- 6 树、2-3-4-5-6- 7 树……子子孙孙,无穷尽也~

所以,有人就把这一类树演绎为一个新的名字:B 树。

B 树

B 树,示意的是一类树,它容许一个节点能够有多于两个子节点,同时,也是自均衡的,叶子节点的高度都是雷同的。

所以,为了更好地区分一颗 B 树到底属于哪一类树,咱们给它一个新的属性:度(Degree)。

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

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

B 树,一个节点能够存储多个元素,有利于缓存磁盘数据,整体的工夫复杂度趋向于 O(log n),原理也比较简单,所以,常常用于数据库的索引,包含晚期的 mysql 也是应用 B 树来作为索引的。

然而,B 树有个大缺点,比方,我要按范畴查找元素,以下面的 2 -3- 4 树为例,查找大于 B 且小于 K 的所有元素,该怎么实现呢?

很难,简直无解,所以,前面又呈现代替 B 树的计划:B+ 树。

当然了,B+ 树不是本节的重点,本节的重点是红黑树。

纳尼,红黑树在哪里?写了 3000 多字了,还没见到红黑树的影子,我尬了~

来了来了,有意思的红黑树来了~~

红黑树

先上一张图,请认真领会:

看明确了没有?红黑树是啥?红黑树就是 2 -3- 4 树!!!

OK,本节到此结束。

后记

本节,咱们一起从二叉树登程,一路通过二叉查找树、均衡树、AVL 树、2- 3 树、2-3- 4 树、B 树,最初终于得出了红黑树的实质,红黑树的实质就是一颗 2 -3- 4 树,换了个皮肤而已。

那么,为什么要再造一个红黑树呢?间接用 2 -3- 4 树它不香么?

咱们下一节解答,同时,下一节,咱们将从红黑树的实质登程,彻底了解红黑树插入、删除、查找、左旋、右旋的全过程,再也不必死记硬背了,还不来关注我 ^^

关注公主号“彤哥读源码”,解锁更多源码、根底、架构常识。

退出移动版