这是我参与「第五届青训营 」笔记创造活动的第10天

本系列文章将会以 MySQL 中 InnoDB 存储引擎的 B+ 树为导引,从最基本的树一步步学习到高级的 B树 B+树等高级数据结构.本篇文章首要介绍树和二叉树类.

树不同于链表或哈希表，是一种非线性数据结构，树分为二叉树、二叉查找树、B树、B+树、红黑树等等。本文企图从最基本的树开端研究各种类型的树的原理和特色。

树的介绍

树是一种数据结构，它是由n个有限节点组成的一个具有层次关系的集合。用图片来表示的话，可以看到它很像一棵倒挂着的树。因此咱们将这类数据结构统称为树，树根在上面，树叶在下面。一般的树具有以下特色：

  • 每个节点有0个或者多个子节点
  • 没有父节点的节点被称为根节点
  • 每个非根节点有且只要一个父节点
  • 每个子结点都可以分为多个不相交的子树

下面的图片展示了一棵三层的树，其间，A是根节点。它看起来像一棵倒挂的树。

graph TD
	A --> B
	A --> C
	B --> D
	B --> E
	C --> F
	C --> G
	C --> H

有关树的术语如下：

  • 如果一个节点有子树，则这个节点称为子树根节点的双亲，子树的根节点是该节点的孩子。有相同双亲的节点互为兄弟。一个节点上的一切子树的任何节点都是该节点的后裔。例如，B是A的孩子，A是B的双亲，B和C互为兄弟。BCDEFGH都是A的后裔。

  • 节点的度：指的是节点具有的子节点的数目。例如，C节点的度为3。

  • 叶子节点：顾名思义，叶子节点的意思即为它没有子节点。它的度为0。

  • 层：指示一个节点在这棵树上的方位。根节点的层为1，其他节点的层值为父节点的层+1。

  • 无序树：若一棵树中每个节点的子节点在父节点中的次序不重要，则这棵树被称为无序树。

  • 有序树：一棵树中每个节点的子节点在父节点中的次序重要，则为有序树。

二叉树

二叉树的界说是：每个节点最多有两个子节点。即每个节点只能有以下四种情况：

  1. 左子树和右子树均为空
  2. 只存在左子树
  3. 只存在右子树
  4. 左子树和右子树均存在

性质

  1. 二叉树第 ii 层上的节点数目最多为 2i−12^i-1
  2. 深度为 kk 的二叉树中最多有 2k−12^k-1 个节点
  3. 包含 nn 个节点的二叉树的高度至少为 log2(n+1)log_2(n+1)
  4. 二叉树中,设叶子节点数为 n0n_0 ,度为2的节点数为 n2n_2 ,则 n0=n2+1n_0=n_2+1

不同形状的二叉树

满二叉树

高度为 hh ,并且由 2h−12^h-1 个节点组成的二叉树,被称为满二叉树. 满二叉树的特色在于,每个节点的度只能是0或者2

graph TD
	A --> B
	A --> C
	B --> D
	B --> E
	C --> F
	C --> G

彻底二叉树

一棵二叉树中,只要最下面两层节点的度可以小于2,并且最下一层的叶子节点集中在靠左的若干方位上.

graph TD
	A --> B
	A --> C
	B --> E
	B --> F
	E --> G
	E --> H
	F --> I
	C --> J
	C --> K

疑问:为什么要提出彻底二叉树?

ChatGPT 的答复:

彻底二叉树的概念被提出主要是由于它具有以下的特别性质：

  1. 关于深度为 k 的彻底二叉树，它的节点个数是 2k−12^k-1，其间 kk 是非负整数。这个特性使得咱们可以快速地计算出彻底二叉树的节点个数，而不用遍历整棵树。
  2. 彻底二叉树可以使用数组来存储，具有十分高的空间利用率，由于节点之间没有空地。关于彻底二叉树的第 ii 个节点（根节点为第 1 个节点），它的左子节点为 2i2i，右子节点为 2i+12i+1，父节点为 i/2i/2（向下取整）。这种存储方法可以大大简化二叉树的操作，如查找、刺进和删除等。
  3. 在堆（Heap）这种数据结构中，彻底二叉树也扮演着十分重要的角色。在大根堆（Max Heap）中，每个节点的值都大于或等于其子节点的值；而在小根堆（Min Heap）中，每个节点的值都小于或等于其子节点的值。由于彻底二叉树具有上述的性质，所以堆一般选用彻底二叉树来实现。

因此，彻底二叉树不仅具有本身的特别性质，并且还与其他数据结构和算法密切相关，是计算机科学中十分重要的概念之一。

二叉查找树

又被称为二叉查找树,特色是: 左子节点比节点小,右子节点比节点大,如下图所示:

graph TD
	8 --> 4
	8 --> 10
	4 --> 2
	4 --> 6
	2 --> 1
	2 --> 3
	6 --> 5
	6 --> 7
	10 --> 9
	10 --> 11