当前位置：首页 > news >正文

总结下各种常见树形结构的定义及特点（二叉树、AVL树、红黑树、Trie树、B树、B+树）

news 来源：原创 2024/5/4 1:42:39

文章目录

前言
一棵普通的树
- 相关术语
二叉树
- 二叉树性质
- 二叉树特例
二叉查找树
- AVL树
- - 特点及应用
- 红黑树
- - 特点
  - 应用
Trie树
- 特点及应用
B树
- 定义及特点
- 应用
B+树
- B+树的优势及应用
总结

前言

树形结构相比于数组、链表、队列和栈等线性结构要复杂的多，因为树本身的概念就比较多，通过设定一些条件和限制就可以定义出一种新类型的树，结果造成了树的“变化多端”，所以要学习一种树要从树的定义入手，然后根据定义和特点来熟悉各种树适合的场景，这样就可以做到“树尽其用”目的了。

一棵普通的树

树形结构和现实中的树很像，只不过现实中的树根长在地上，而树形结构再展示的时候一般把树根画在“天上”，树形结构中数据元素之间存在着“一对多”的关系，具有以下特点：

没有父节点的节点称为根节点
除空树外每棵树只有一个根节点
每个节点都只有有限个子节点或无子节点
每个非根节点有且只有一个父节点
树里面没有环路，如果从一个节点出发，除非往返，否则无法回到起点

基础的树

二叉树

二叉树是对普通树形结构进行限定得到的一种特殊的树，规定树中节点的度不大于2，当节点有两个子节点，也就是有两颗子树时，它们有左右之分，分别被称为左子树和右子树，左子树和右子树又同样都是二叉树。

二叉树性质

二叉树的第i层上至多有2^(i-1)（i≥1）个节点
深度为h的二叉树中至多含有2^h-1个节点
若在任意一棵二叉树中，有n个叶子节点，有m个度为2的节点，则必有n=m+1
具有n个节点的满二叉树深为log(2n+1)
若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点
- 当i=1时，该节点为根，它无双亲节点
- 当i>1时，该节点的双亲节点的编号为i/2
- 若2i≤n，则有编号为2i的左节点，否则没有左节点
- 若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点

二叉树特例

完美二叉树（Perfect Binary Tree）：除了叶子结点之外的每一个结点都有两个孩子，每一层都被完全填充

完美二叉树

完全二叉树（Complete Binary Tree）：除了最后一层之外的其他每一层都被完全填充，并且所有结点都保持向左对齐

完满二叉树（Full Binary Tree）：除了叶子结点之外的每一个结点都有两个孩子结点

完满二叉树

二叉查找树

二叉查找树是一种特殊的二叉树，又称为排序二叉树、二叉搜索树、二叉排序树等等，它实际上是数据域有序的二叉树，即对树上的每个结点，都满足其左子树上所有结点的数据域均小于或等于根结点的数据域，右子树上所有结点的数据域均大于根结点的数据域。

AVL树

平衡二叉树是由前苏联的两位数学家G.M.Adelse-Velskil和E.M.Landis联合提出，因此一般也称作AVL树，AVL树本质还是一棵二叉查找树，只是在其基础上增加了“平衡”的要求，需保证其左子树与右子树的高度之差的绝对值不超过1，其中左子树与右子树的高度因子之差称为平衡因子。

对于AVL树，不管我们是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡。由于旋转比较耗时，所以AVL树适合用于插入与删除次数比较少，但查找多的情况。

特点及应用

所有节点的左右子树高度差不超过1，广泛用于Windows NT内核中

红黑树

红黑树也是一颗二叉查找树，需要为每个节点存储节点的颜色，可以是红或黑。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，来确保没有一条路径会比其它路径长出两倍，因此，红黑树是一种弱平衡二叉树。

由于是弱平衡二叉树，那么在相同的节点情况下，AVL树的高度小于等于红黑树的高度，相对于要求严格的AVL树来说，它的旋转次数少，所以对于插入，删除操作较多的情况下，用红黑树的查找效率会更高一些。

特点

每个节点非红即黑
根节点是黑的
每个叶子节点（叶子节点即树尾端NULL节点）都是黑的
每条路径都包含相同的黑节点
如果一个节点是红的，那么它的两儿子都是黑的
对于任意节点而言，其到叶子点的每条路径都包含相同数目的黑节点

应用

广泛用于C++的STL中，如 map 和 set 是用红黑树实现的
Linux的进程调度用红黑树管理进程控制块，进程的虚拟内存空间都存储在一颗红黑树上，每个虚拟内存空间都对应红黑树的一个节点
IO多路复用的 epoll 采用红黑树组织管理socket fd，以支持快速的增删改查
Nginx中用红黑树管理定时器，可以快速得到距离当前最小的定时器
Java的TreeMap的用红黑树实现

Trie树

Trie树又被称为前缀树、字典树是一种用于快速检索的多叉树结构。字典树把字符串看成字符序列，根据字符串中字符序列的先后顺序构造从上到下的树结构，树结构中的每一条边都对应着一个字符。字典树上存储的字符串被视为从根节点到某个节点之间的一条路径，并在终点节点上做个标记"该节点对应词语的结尾"，正因为有终点节点的存在，字典树不仅可以实现简单的存储字符串，还可以实现字符串的映射，只需要将相对应的值悬挂在终点节点上即可。

特点及应用

Trie的核心思想是空间换时间，有如下基本性质：

根节点不包含字符，除根节点外每一个节点都只包含一个字符
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串
每个节点的所有子节点包含的字符都不相同

字典树能够利用字符串中的公共前缀，这样可能会节省内存，利用字符串的公共前缀可以减少查询字符串的时间，能够最大限度的减少无谓的字符串比较，同时在查询的过程中不需要预知待查询字符串的长度，沿着字典树的边进行匹配，查询效率比较高，但是如果系统中存在大量字符串并且这些字符串基本没有前缀，相应的字典树内存消耗也会很大。正是由于字典树的这些特点，字典树被用于统计、排序和保存大量的字符串（不仅限于字符串），还可用于搜索引擎的关键词提示功能。

B树

B树是一个多路平衡查找树，B树的出现是为了弥合不同的存储级别之间的访问速度上的巨大差异，实现高效的I/O。平衡二叉树的查找效率是非常高的，并可以通过降低树的深度来提高查找的效率。但是当数据量非常大，树的存储的元素数量是有限的，这样会导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下，同时数据量过大会导致内存空间不够容纳平衡二叉树所有结点的情况，而B树是解决这个问题的很好的结构。

要想了解B树需要了解一个很重要的概念，B树中所有节点的度的最大值称为B树的阶，记为m，这是一个跟重要值，也就是说m阶B树指的是节点度最大为m的B树。

定义及特点

每个节点最多只有m个子节点
根结点的儿子数为[2, m]
除根结点以外的非叶子结点的儿子数为[m/2, m]，向上取整
非叶子结点的关键字个数=子节点数-1
所有叶子都出现在同一层
k个关键字把节点拆成k+1段，分别指向k+1个儿子，同时满足查找树的大小关系
非叶子节点中不仅包含索引，也会包含数据

应用

B树是一种平衡的多路查找树，主要用作文件的索引。其优势是当你要查找的值恰好处在一个非叶子节点时，查找到该节点就会成功并结束查询，有很多基于频率的搜索是选用B树，越频繁查询的结点越往根上走，前提是需要对查询做统计，而且要对key做一些变化。

B+树

B+树是b树的一种变体，查询性能更好，m阶的b+树具有以下特征：

有n棵子树的非叶子结点中含有n个关键字（b树是n-1个），这些关键字不保存数据，只用来索引，所有数据都保存在叶子节点（b树是每个关键字都保存数据）
所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接
所有的非叶子结点可以看成是索引部分，结点中仅含其子树中的最大（或最小）关键字
通常在b+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点
同一个数字会在不同节点中重复出现，根节点的最大元素就是b+树的最大元素

B+树的优势及应用

B+tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多，相对来说IO读写次数也就降低了。
由于非叶子结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
B+树支持范围遍历，只要遍历叶子节点就可以实现整棵树的遍历，而在数据库中基于范围的查询是非常频繁的，这一点要明显由于B树。

由于拥有以上特点，B+广泛应用于文件存储系统以及数据库系统中。