树

树的定义

树是n（n>=0）个结点的有限集。当n = 0时，称为空树。在任意一棵非空树中应满足：

1. 有且仅有一个特定的称为根的结点。
2. 当 n>1 时，其余节点可分为m（m>0）个互不相交的有限集T1,T2,…,Tm，其中每个集合本身又是一棵树，并且称为根的子树。

显然，树的定义是递归的，即在树的定义中又用到了自身，树是一种递归的数据结构。树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：

1. 树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱。
2. 树中所有结点可以有零个或多个后继。

因此 n 个结点的树中有 n-1 条边。

基本术语

下面结合图示来说明一下树的一些基本术语和概念。

• 考虑结点 K。根 A 到结点 K 的唯一路径上的任意结点，称为结点 K 的祖先。如结点 B 是结点 K 的祖先，而结点 K 是结点 B 的子孙。路径上最接近结点 K 的结点 E 称为 K 的双亲，而 K 为结点 E 的孩子。根 A 是树中唯一没有双亲的结点。有相同双亲的结点称为兄弟，如结点 K 和结点 L 有相同的双亲 E，即 K 和 L 为兄弟。

• 树中一个结点的孩子个数称为该结点的度，树中结点的最大度数称为树的度。如结点 B 的度为 2，结点 D 的度为3，树的度为3。

• 度大于 0 的结点称为**分支结点(又称非终端结点)；度为 0 (没有子女结点)的结点称为叶子结点(又称终端结点)**。在分支结点中，每个结点的分支数就是该结点的度。

• 结点的深度、高度和层次。

  • 结点的层次从树根开始定义，根结点为第 1 层，它的子结点为第 2 层，以此类推。双亲在同一层的结点互为堂兄弟，图中结点 G 与 E,F,H,I,J 互为堂兄弟。
  • 结点的深度是从根结点开始自顶向下逐层累加的。
  • 结点的高度是从叶结点开始自底向上逐层累加的。
  • 树的高度(或深度)是树中结点的最大层数。图中树的高度为4。

• 有序树和无序树。树中结点的各子树从左到右是有次序的，不能互换，称该树为有序树，否则称为无序树。假设图为有序树，若将子结点位置互换，则变成一棵不同的树。

• 路径和路径长度。树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数。

  注意:由于树中的分支是有向的，即从双亲指向孩子，所以树中的路径是从上向下的，同一双亲的两个孩子之间不存在路径。

• 森林。森林是 m (m≥0) 棵互不相交的树的集合。森林的概念与树的概念十分相近，因为只要把树的根结点删去就成了森林。反之，只要给m棵独立的树加上一个结点，并把这m棵树作为该结点的子树，则森林就变成了树。

树的性质

树具有如下最基本的性质：

• 树中的结点数等于所有结点的度数加1.
• 度为 m 的树中第 i 层上至多有 m^(i-1) 个结点
• 高度为 h 的 m 叉树至多有( m^h − 1 ) / ( m − 1 )个结点。

二叉树

二叉树的定义

二叉树是另一种树形结构，其特点是每个结点至多只有两棵子树( 即二叉树中不存在度大于 2 的结点)，并且二叉树的子树有左右之分，其次序不能任意颠倒。

与树相似，二叉树也以递归的形式定义。二叉树是n (n≥0) 个结点的有限集合:

1. 或者为空二叉树，即 n=0。
2. 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

二叉树是有序树，若将其左、右子树颠倒，则成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。二叉树的5种基本形态如图所示。

几个特殊的二叉树

斜树

所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

满二叉树

一棵高度为 h，且含有 2^h-1 个结点的二叉树称为满二叉树，即树中的每层都含有最多的结点。满二叉树的叶子结点都集中在二叉树的最下一层，并且除叶子结点之外的每个结点度数均为 2。可以对满二叉树按层序编号：约定编号从根结点(根结点编号为1)起，自上而下，自左向右。这样，每个结点对应一个编号，对于编号为 i 的结点，若有双亲，则其双亲为 i / 2，若有左孩子，则左孩子为 2i；若有右孩子，则右孩子为 2i + 1。

完全二叉树

二叉排序树

左子树上所有结点的关键字均小于根结点的关键字；右子树上的所有结点的关键字均大于根结点的关键字；左子树和右子树又各是一棵二叉排序树。

平衡二叉树

树上任一结点的左子树和右子树的深度之差不超过1。又称 AVL 树。

平衡二叉树

定义

• 平衡二叉树，又称AVL树，用于解决二叉排序树高度不确定的情况，如果二叉排序树的子树间的高度相差太大，就会让二叉排序树操作的时间复杂度升级为O(n)，为了避免这一情况，为最坏的情况做准备，就出现了平衡二叉树，使树的高度尽可能的小，其本质还是一棵二叉搜索树。

• 平衡二叉树的性质：

  • 左子树和右子树的高度之差的绝对值小于等于1
  • 左子树和右子树也是平衡二叉树

• 为了方便起见，给树上的每个结点附加一个数字，给出该结点左子树与右子树的高度差，这个数字称为结点的平衡因子（BF）

• 平衡因子=结点左子树的高度-结点右子树的高度。

因此平衡二叉树所有结点的平衡因子只能是-1、0、1，如下图，是一个平衡二叉树

平衡二叉树的高度为 logn

失衡

当我们在一个平衡二叉树上插入一个结点时，有可能会导致失衡，即出现平衡因子绝对值大于1 的结点，如下图，当插入结点后，其中 key 为 53 的结点失去了平衡，我们称该结点为失衡结点，我们必须重新调整树的结构，使之恢复平衡。

不一定只有一个结点失去平衡，有可能插入一个结点会让多个结点失衡。这时候找 最小的失衡子树的根节点作为失衡结点。

恢复平衡

那如何去恢复平衡，使得二叉搜索树依然成立为一棵平衡树？先来看平衡调整的四种类型：

举个例子：如第一个，当平衡二叉树为 AB 时，插入一个 C 结点，使得失衡了，失衡结点为 A，此时因为 C 结点插入的位置为失衡结点的左孩子的左孩子，所以是LL型，以此类推。

为了恢复平衡，针对每一种都不一样，但目的都是调整为平衡的，且不能违背二叉搜索树的性质：如下图是每种失衡类型的解决方法，每个都不太一样，目的都是一样的，把 key 的值为中等的变为树的根，最小的放在左孩子，做大的放右孩子，通过这一目的，降低树的高度，也不用死记硬背。

2-3-4 树

红黑树

B树

• 树中每个节点最多含有 m 棵子树。

• 根结点至少有 2 个子树。

• 非根非叶节点至少有⌈m/2⌉(向上取整)棵子树。

• 如果一个节点有 n-1 个关键字，则该节点有 n 个分支，且这 n-1 个关键字按照递增顺序排列。

• 每个非终端结点中包含信息：（N，A0，K1，A1，K2，A2，…，KN，一）其中：

  • Ki（1≤i≤n）为关键字，且关键字按升序排序。
  • 指针Ai（0≤i≤n）指向子树的根结点，Ai-1指向子树中所有结点的关键字均小于Ki，且大于Ki-1;
  • 关键字的个数 n 必须满足：⌈m/2⌉-1≤n≤m-1。
  • 结点内关键字各不相等且按从小到大排列。
  • 所有叶子节点具有相同的深度，这也说明B树是平衡的

• 在搜索 B 树时，很明显，访问节点（即读取磁盘）的次数与树的高度呈正比，而 B 树与二叉查找树相比，虽然高度都是对数级的，但是显然 B 树中底数比 2 大。因此，和二叉树相比，极大地减少了磁盘读取的次数。

• 平衡m叉查找树是指每个关键字的左侧子树与右侧子树的高度差的绝对值不超过1的查找树，其结点结构与上面提到的B-树结点结构相同，由此可见，B 树是平衡 m 叉查找树，但限制更强，要求所有叶结点都在同一层。

B+树

一个 m 阶的 B+树 具有如下几个特征：

• 有 k 个子树的中间节点包含有 k 个元素（B树中是k-1个元素），每个元素不保存数据，只用来保存索引，所有数据都保存在叶子节点。
• 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
• 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

• 根节点的最大元素也就是整个 B+树 的最大元素，以后无论插入删除多少元素，始终要保持最大的元素在根节点当中。
• 由于父节点的元素都出现在子节点中，因此所有的叶子节点包含了全部元素信息，并且每一个叶子节点都带有指向下一个节点的指针，形成了一个有序链表。

B+树添加和删除数据