阿粉带你3分钟看完关于树的故事

在计算机中,树随处可在,可说是图论和计算机科学中的重中之重,理解树的结构、树的思想和树的优异性质对于程序设计大有裨益!

一、前言

我们都知道,数组的特点是查询快,直接可以通过下标获取元素,时间复杂度为O(1);但是当我们在指定的位置插入元素或者删除元素的时候,数组下标和所对应的元素是需要重新排列的,所需要的时间复杂度为O(n)

所以对于频繁的插入、删除的场景,不建议采用有序数组!

可能有的朋友会想到,对于需要频繁的插入、删除的场景,可以使用链表结构,因为对于链表结构来说,在进行插入或者删除的时候,只需要改变元素的前驱或者后继节点的引用就可以了,所需要的时间复杂度为O(1);但是如果我们想查询指定的内容时候,需要遍历链表元素并逐步判断,直到查找到目标元素为止,所需要的时间复杂度为O(n)

所以对于查找频繁的数据,不建议使用链表!

哪有没有一种查询速度快、插入删除也很快的一种数据结构呢?

就是其中一个!这种数据结构,在计算机领域中有着很多的实际应用!比如说:

  • mysql 数据库的索引就是 B+ 树结构,查找效率极高;
  • Windows OS 的文件系统结构也是采用 B+ 树进行存储的;
  • Linux 的文件系统结构同样也是采用 B+ 树进行存储的;

二、树介绍

说到这种数据结构,相信很多人首先想到的就是二叉树

不错,二叉树作为一个很重要的数据结构,在某些情况下既可以满足我们要求查询快的特点同时也可以满足插入删除也快的要求。

当然,在生活中我们可以看到树,其实是分很多种类的,我们刚刚也说了在某些情况下,假如一个树是任意自由的结构,那么它可能既达不到查询快也达不到插入删除快的要求,因此我们需要给树作出一些定义。

在现实中,树是一个根朝下、叶朝上的结构,而在计算机科学中,树是由n个有限节点组成一个具有层次关系的集合,看起来像一颗倒挂的树,根朝上、叶朝下,特点如下:

  • 每个节点都只有有限个子节点或无子节点;
  • 没有父节点的节点称为根节点;
  • 每一个非根节点有且只有一个父节点;
  • 除了根节点外,每个子节点可以分为多个不相交的子树;
  • 树里面没有环路;

计算机科学中,树的定义:

如下图,看起来像一颗树,但不是树结构:

虽然树做出了一些基本定义,但是不足以满足我们的需求,在计算机科学中,树可以被分为以下几种类型:

  • 无序树:树中任意节点的子节点之间没有顺序关系,这种树称为无序树,也称为自由树;
  • 有序树:树中任意节点的子节点之间有顺序关系,这种树称为有序树;

对于无序树,也就是那种自由树结构,没有任何规律,所以无从查找,这种结构一般不考虑;而有序树,因为各个子节点存在一个的顺序关系,那么在查询的时候,就可以以此为基础进行查找!

当然,有序树又可以进行种类细分,内容如下:

  • 二叉树:每个节点最多含有两个子树的树称为二叉树;
  • B 树:一种平衡的多路查找(又称排序)树,能够保持数据有序,拥有多于两个子树;

上文说到的二叉树其实就是有序树的一种,在程序开发中,用的也是最多的一种树形结构!

而对于B 树,主要在文件系统和数据库领域中有所应用,像 Linux 操作系统的文件系统就是使用 B+ 树进行文件的存储。

三、二叉树

在计算机科学中,二叉树(英文名:Binary Tree)是每个结点最多有两个子树的树结构,通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。

按照这个定义,在逻辑上二叉树可以进行五种基本形态的分类:

  • 1、空二叉树;
  • 2、只有一个根结点的二叉树;
  • 3、只有左子树的二叉树;
  • 4、只有右子树的二叉树;
  • 5、拥有左、右子树的二叉树;

3.1、树的种类

对于 1~4 种形态的二叉树,形状比较简单,对于第 5 种既有左子树又有右子树的二叉树,在形态上比较复杂,我们也可以进行特殊类型细分,内容如下:

  • 完全二叉树:若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第h层有叶子结点,并且叶子结点都是从左到右依次排布,这样的二叉树被称为完全二叉树;
  • 满二叉树:所有叶节点都在最底层的完全二叉树
  • 平衡二叉树:当且仅当任何节点的两棵子树的高度差不大于1的二叉树;
3.1.1、完全二叉树

完全二叉树是一种特殊的二叉树,特性如下:

  • 所有叶子节点都出现在 k 或者 k-1 层,而且从 1 到 k-1 层必须达到最大节点数;
  • 第 k 层可以不是满的,但是第 k 层的所有节点必须集中在最左边;
  • 任何一个节点不能只有左子树没有右子树;
  • 叶子节点出现在最后一层或者倒数第二层,不能再往上;

在实际的开发中也有所应用,完全二叉树会使用二叉查找树算法(会在下文介绍),来保证查找的数据是有序的,叶子节点可以按从上到下、从左到右的顺序依次添加到数组中。知道一个节点的位置,就可以轻松地算出它的父节点、孩子节点的位置。

当我们用数组存储一个完全二叉树时,以上面图中完全二叉树为例,标号为 2 的节点,它在数组中的位置也是 2,它的父节点就是 (k/2 = 1),它的孩子节点分别是 (2k=4) (2k+1=5),别的节点也是类似。

因为叶子节点的位置比较规律,所有查询排序效率比较高,比如堆排序就使用了它。

3.1.2、满二叉树

除最后一层结点均无任何子节点外,每一层的所有结点都有两个子结点的树,称为满二叉树!

也就是说,如果一个二叉树的层数为K,且结点总数是(2^k) -1,满二叉树形状:

满二叉树,特性完全同完全二叉树,但是比完全二叉树更严格,每个叶节点到达根路径所需的长度都相同!而完全二叉树k-1层可以为叶节点!

3.1.3、平衡二叉树

平衡二叉树的提出就是为了保证树不至于太倾斜,尽量保证两边平衡,特性如下:

  • 平衡二叉树要么是一棵空树;
  • 要么保证左右子树的高度之差不大于 1;
  • 左右两个子树都是一棵平衡二叉树;

平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。

像 JDK1.8 中 HashMap、TreeMap 等就使用到了红黑树实现。

3.2、二叉查找树

上面介绍了完全二叉树、满二叉树、平衡二叉树都属于特殊类型的二叉树,需要我们从逻辑上去控制才可以满足要求!

上文中我们说到,二叉树的出现就是为了解决查询效率问题,按照二分进行查找,每次查询只需要选择其中一个子树就进行查找,从而减少查找次数,提升查询效率!

那么我们如何进行二分查找呢?

这就要求查找的数据必须是有序的,每次查找、插入删除时都要维护一个有序的数据集,于是就有了二叉查找树这个概念,英文全称 Binary Search Tree,简称 BST

二叉查找树,也被称为二叉排序树,可以说是从算法层面来定义二叉树结构,这种算法思路适用于所有的二叉树结构,特性如下:

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

二叉查找树,在最好的情况下,按照折半查找,查询效率得到提升,时间复杂度为O(logn);但是,如果构成的二叉排序树蜕变为单支树,树的深度为 n,其查找时间复杂度与顺序查找一样为O(n)

如果二叉查找树变成了单支树,查询效率就大大折扣了,于是就有平衡二叉查找树的出现!

3.3、平衡二叉查找树

平衡二叉查找树,又称 AVL 树,因为算法的发明者为Adel'son-Vel'skiiLandis,被称为 AVL 树来自于大神的姓名缩写组合。

它除了具备二叉查找树的基本特征之外,还具有一个非常重要的特点:

  • 它的左子树和右子树都是平衡二叉树;
  • 且它的左子树和右子树的深度之差的绝对值(平衡因子 ) 不超过1;

也就是说 AVL 树每个节点的平衡因子只可能是-1、0和1(平衡因子算法:左子树高度减去右子树高度)。

那么如何保证二叉查找树在添加元素的同时保证节点平衡呢?

基本思想就是:当在二叉排序树中插入一个节点时,首先检查是否因插入而破坏了平衡,若破坏,则找出其中的最小不平衡二叉树,在保持二叉查找树特性的情况下,调整最小不平衡子树中节点之间的关系,以达到新的平衡。

所谓最小不平衡子树是指:离插入节点最近且以平衡因子的绝对值大于1的节点作为根的子树。

当新插入的节点导致树结构发生失衡就会进行调整,主要操作有左旋转右旋转操作!

3.3.1、绕某元素左旋转

从图中可以看出,在插入数据 100 之前,左图 BST 树只有 80 节点的平衡因子是 -1(左子树高度减去右子树高度),但整棵树还是平衡的。

插入 100 之后,80节点的平衡因子就成为了-2,此时平衡被破坏,需要进行调整,绕节点 90 进行左旋转,最终树型结构变成右图。

左旋转场景:当树中节点 X 的右孩子的右孩子上插入新元素,且平衡因子从 -1 变成 -2 后,就需要绕节点 X 进行左旋转!

3.3.2、绕某元素右旋转

从图中可以看出,在插入数据 30 之前,左图 BST 树只有 80 节点的平衡因子是 1(左子树高度减去右子树高度),但整棵树还是平衡的。

插入 30 之后,80节点的平衡因子就成为了 2,此时平衡被破坏,需要进行调整,绕节点 50 进行右旋转,最终树型结构变成右图。

右旋转场景:当树中节点 X 的左孩子的左孩子上插入新元素,且平衡因子从 1 变成 2 后,就需要绕节点 X 进行右旋转。

3.3.3、绕某元素的左子节点左旋转,接着再绕该元素自己右旋转

很多时候,插入元素一次调整满足不了要求,如下图就是左旋与右旋的结合,具体操作时可以分解成这两种操作,只是围绕点不一样而已。

3.3.4、绕某元素的右子节点右旋转,接着再绕该元素自己左旋转

与之对应的,也有右旋与左旋的结合,如下图:

由此可见,通过左旋转、右旋转操作,平衡二叉树不会出现普通二叉查找树的最差情况,其查找的时间复杂度为O(logN)!

在查询的时候,操作与普通二叉查找树上的查找操作相同;插入的时候,每一次插入结点操作最多只需要单旋转或双旋转,总体上插入操作的代价仍然在O(logN)级别;如果是动态删除,删除之后必须检查从删除结点开始到根结点路径上的所有结点的平衡因子,最多可能需要O(logN)次旋转。

为了解决尽可能少的旋转调整,红黑树出现了!

3.4、红黑树

红黑树,英文名称:red-black tree,简称 RBT!红黑树也是基于平衡二叉树结构的一种实现,但是它的平衡指标没有像 AVL 算法那样要求很严格,并不是高度平衡但基本平衡,特性如下:

  • 每一个结点要么是红色,要么是黑色;
  • 根结点是黑色的;
  • 所有叶子结点都是黑色的(实际上都是Null指针,下图用NIL表示)。叶子结点不包含任何关键字信息,所有查询关键字都在非终结点上;
  • 每个红色结点的两个子节点必须是黑色的。换句话说:从每个叶子到根的所有路径上不能有两个连续的红色结点;
  • 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点;

红黑树,在查找方面,与普通二叉查找树上的查找操作相同;在插入、删除方面,调整方式和平衡二叉查找树类似,一样是左旋转、右旋转,其中红黑树还增加一个调整操作:节点颜色转换

从上面的特性可以看出,从每个叶子到根的所有路径上不能有两个连续的红色结点,对于不满足特性的节点颜色,只需要转换颜色一些即可,比较简单!

红黑树,在插入的时候,与 AVL 一样,结点最多只需要2次旋转;在删除的时候,因为没有像 AVL 那样高度平衡的要求,删除一个结点最多只需要3次旋转操,可见红黑树的删除操作代价要比 AVL 要好的多;因为不是高度平衡,在查询方面,红黑树在查询效率方面稍逊于 AVL,但是比二叉查找树强很多!

在 JDK 中就有很多红黑树的具体实现,最典型的就是 JDK1.8 中的 HashMap,当冲突链表长度大于 8 时,链表就会以红黑树结构存储。

3.5、哈夫曼树

哈夫曼树是一种特殊结构的二叉树,主要由哈夫曼编码实现,内容定义如下:

给定N个权值作为N个叶子结点,构造一棵二叉树,若这棵二叉树的带权路径长度达到最小,则称这样的二叉树为最优二叉树,也称为Huffman树。

哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

哈夫曼编码的由来!

1951年,哈夫曼在麻省理工学院(MIT)攻读博士学位,他和修读信息论课程的同学正在想选择是完成学期报告还是期末考试。此时的导师罗伯特·法诺(Robert Fano)出的学期报告题目是:查找最有效的二进制编码。

由于无法证明哪个已有编码是最有效的,哈夫曼放弃对已有编码的研究,转向新的探索,最终发现了基于有序频率二叉树编码的想法,并很快证明了这个方法是最有效的。

哈夫曼使用自底向上的方法构建二叉树,避免了次优算法香农-范诺编码(Shannon–Fano coding)的最大弊端──自顶向下构建树。

并于1952年,在论文《一种构建极小多余编码的方法》(A Method for the Construction of Minimum-Redundancy Codes)中发表了这个编码方法。

四、B树

在上文中讲的 BST、AVL、RBT 都是典型的二叉查找树结构,其查找的时间复杂度与树高相关。

降低树的高度可以提高查找效率,另外还有一个比较实际的问题:就是大量数据存储中,实现查询这样一个实际背景下,平衡二叉树由于树深度过大而造成磁盘IO读写过于频繁,进而导致效率低下。

那么如何减少树的高度,一个基本的想法就是:

  • 每个节点存储多个元素;
  • 摒弃二叉树结构,采用多叉树;

这样我们就提出来了一个新的查找树结构 ——多路查找树,根据 AVL 给我们的启发,一颗平衡多路查找树可以使得数据的查找效率保证在O(logN)这样的对数级别上。

在计算机科学中,平衡多路查找树,简称为B树,每个节点可以拥有2个以上的子节点,能够保持数据有序。

这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作,都在对数时间内完成。

与自平衡二叉查找树不同,B 树适用于读写相对大的数据块的存储系统,例如磁盘。

B树减少定位记录时所经历的中间过程,从而加快存取速度。这种数据结构常被应用在数据库和文件系统的实现上。

4.1、B- 树

B~树,也就是我们常说的 B 树,其实 B~树和 B 树是同一种树,我们知道 B 树是多叉结构,假如给定一个变量 m 来指定多叉,一棵 m 阶的 B~树(m叉树)的特性如下:

  • 排序方式:所有节点关键字是按递增次序排列,并遵循左小右大原则;
  • 子节点数:非叶节点的子节点数>1,且<=M ,且M>=2,空树除外(注:M阶代表一个树节点最多有多少个查找路径,M=M路,当M=2则是2叉树,M=3则是3叉);
  • 关键字数:枝节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个(注:ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2);
  • 所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子;

例如:下面就是一棵3阶B~树,如图所示:

B树相对于平衡二叉树的不同是,每个节点包含的关键字增多了,特别是在 B 树应用到数据库中的时候,数据库充分利用了磁盘块的原理,把节点大小限制和充分使用在磁盘快大小范围;把树的节点关键字增多后树的层级比原来的二叉树少了,减少数据查找的次数和复杂度。

4.2、B+ 树

B+树是B树的一个升级版,相对于B树来说B+树更充分的利用了节点的空间,让查询速度更加稳定,其速度完全接近于二分法查找。

一棵m阶的B+树和m阶的B-树的差异,内容如下:

  • 有n棵子树的结点中含有n个关键字;(B~树是n棵子树有n+1个关键字)
  • 所有的叶子结点中包含了全部关键字的信息,及指向含有这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大的顺序链接;(B~树的叶子节点并没有包括全部需要查找的信息)
  • 所有的非终端结点可以看成是索引部分,结点中仅含有其子树根结点中最大(或最小)关键字;(B~树的非终节点也包含需要查找的有效信息)

例如:下面就是一棵3阶B+树,我们可以和B~树做一个明显的对比,如图所示:

B+ 树相比B树的优势如下:

  • B+树的层级更少:相较于B树,B+每个非叶子节点存储的关键字数更多,树的层级更少所以查询数据更快;
  • B+树查询速度更稳定:B+所有关键字数据地址都存在叶子节点上,所以每次查找的次数都相同,所以查询速度要比B树更稳定;
  • B+树天然具备排序功能:B+树所有的叶子节点数据构成了一个有序链表,在查询大小区间的数据时候更方便,数据紧密性很高,缓存的命中率也会比B树高。
  • B+树全节点遍历更快:B+树遍历整棵树只需要遍历所有的叶子节点即可,而不需要像B树一样需要对每一层进行遍历,这有利于数据库做全表扫描。

但B树也不是完全没有优势,B树相对于B+树的优点是:如果经常访问的数据离根节点很近,而B树的非叶子节点本身存有关键字其数据的地址,所以这种数据检索的时候会要比B+树快。

4.3、B*树

B*树,是 B+树的变体,在 B+树的非根和非叶子结点上增加了指向兄弟的指针,不同之处如下:

  • 先是关键字个数限制问题,B+树初始化的关键字初始化个数是cei(m/2),B*树的初始化个数为(cei(2/3*m));
  • B+树节点满时就会分裂,而B*树节点满时会检查兄弟节点是否满(因为每个节点都有指向兄弟的指针),如果兄弟节点未满则向兄弟节点转移关键字,如果兄弟节点已满,则从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来;

B*树相比B+树的优势:在B+树的基础上因其初始化的容量变大,使得节点空间使用率更高,而在非根和非叶子结点上增加指向兄弟的指针,可以向兄弟节点转移关键字的特性使得B*树的分解次数变得更少!

五、总结

关于树的故事,基本介绍完了,内容比较多,尤其B树模型,比较深奥复杂,有兴趣的朋友可以自己研究一些,如果有理解不当的地方,欢迎网友指出!

六、参考

1、百度百科 - 树

2、维基百科 - 树

3、掘金 - 西召 - 树结构与Java实现

4、掘金 - 张拭心 - 二叉树、平衡二叉树、二叉查找树

5、iteye - Heart.X.Raid - 动态查找树比较

6、知乎 - 勤劳的小手 - 平衡二叉树、B树、B+树、B*树

Java Geek Tech wechat
欢迎订阅 Java 极客技术,这里分享关于 Java 的一切。