参考教材：《算法设计与应用》 汪荣贵 杨娟 薛丽霞 机械工业出版社

第4章 树模型及其算法设计

本章系统地学习树模型及其算法设计的基本只是。首先学习树模型的基本概念和性质，然后学习树的若干基本模型和进阶模型，包括平衡树、红黑树、键树、B树、二项树等，最后学习树模型算法设计与应用，包括树的递归与非递归遍历算法、森林与树的转换算法、最优树的构造与编码算法等。

4.1 树的基本模型

在本节将介绍树的若干基本模型及相关的操作算法，包括二叉树、平衡树、红黑树等。

4.1.1 树与二叉树

所谓树模型，从本质上说就是一种连通无环的无向图。在结点数相同的条件下，树是所有连通图中边数最少的图模型，同时也是所有无环图中边数最多的图模型。

树模型的定义

树模型是一个n（n>0）元有限集，集合中所有数据元素具有如下层次关系：当n=0时，集合为空集，称之为空树；当n=1时，集合中有且仅有一个特点的结点，称之为树模型的根；当n>1时，除根以外的其余结点可分为m（m>0）个互不相交的有限集T，T，… ，T，其中每个集合本身又是一棵树，并称T，T，… ，T为根的子树。

二叉树的定义

二叉树是一种简单的树模型结构，它要求每个结点至多有两棵子树（即二叉树中不存在出度大于2的结点），且二叉树的子树有左右之分，其次序不能随意颠倒。二叉树是一种非常基本的树模型，广泛应用于决策、排序、查找等算法设计中，以二叉树为基础可以衍生处很多特殊而又重要的树模型，如平衡树、红黑树等。

3种特殊的二叉树

  • 斜树：即只有左子树或者只有右子树的二叉树
  • 满二叉树：如果所有的分支结点都有左孩子和右孩子结点，并且叶子结点集中在二叉树的最下一层，则这样的二叉树称为满二叉树。也可以理解为叶子结点外的所有结点均有两个子结点。满二叉树有如下两个特征：1、结点数达到最大值；2、所有叶子结点均在最下一层。
  • 完全二叉树：若设二叉树的深度为h，除第h层外，其他各层（1~h-1）的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。完全二叉树是由满二叉树引出来的。对于深度为h的、有n个结点的二叉树，当且仅当其每一个结点都与深度为h的满二叉树中编号从1~n的结点一一对应时称之为完全二叉树。

4.1.2 平衡树及其操作

平衡二叉树是一种特殊的二叉树，要求树中任意结点的两棵子树高度差不能超过1，如果插入或删除一个结点使得高度之差大于1，就要进行结点之间的旋转操作，将二叉树重新维持在平衡状态。

二叉树的基本数据结构如下：

  1. typedef struct Node* Tree;
  2. typedef struct Node* Node_t;
  3. typedef int Type;
  5. struct Node {
  6.     Node_t left;
  7.     Node_t right;
  8.     int height;
  9.     Type data;
  10. };
  12. int Height(Node_t node) {
  13.     return node->height;
  14. }

树模型中某结点左子树的高度减去该结点右子树的高度，所形成的差值称为该结点的平衡因子，即Balance Fector(BF)=左子树的高度-右子树的高度

平衡二叉树的平衡因子为-1，0或1。设计平衡二叉树操作算法的关键在于如何使得平衡二叉树保持平衡，以下4种情况下的插入操作可能会导致原有平衡二叉树变为不平衡。

  • LL：若某一结点的平衡因子为1，当在其左子树（Left）的左子树（Left）上插入一个新结点时会导致该结点的平衡因子由1变为2。
  • RR：若某一结点的平衡因子为-1，当在其右子树（Right）的右子树（Right）上插入一个新结点时会导致该结点的平衡因子由-1变为-2。
  • LR：若某一结点的平衡因子为1，当在其左子树（Left）的右子树（Right）上插入一个新结点时会导致该结点的平衡因子由1变为2。
  • RL：若某一结点的平衡因子为-1，当在其右子树（Right）的左子树（Light）上插入一个新结点时会导致该结点的平衡因子由-1变为-2。

平衡二叉树有4种基本的旋转方式，分别为左旋转、右旋转、先左旋转后右旋转、先右旋转后左旋转。


LL型调整

image.png
插入操作，当3个结点处于一条直线，并均是左结点时，需要以中间结点为旋转轴向右侧（顺时针）旋转一次，具体步骤如下：

  1. 将A的左子树B提升为新二叉树的根。
  2. 将原来的A连同其右子树A向下旋转，使其成为B的右子树。
  3. 将B的原右子树B作为左子树连接到A上

LL型具体调整算法如下：

  1. //右旋
  2. Node_t RightRotate(Node_t a) {
  3.     Node_t b;
  4.     b = a->left;
  5.     a->left = b->right;
  6.     b->right = a;
  7.     return b;
  8. }

RR型调整

image.png
插入操作，当3个结点处于一条直线，并均是右结点时，需要以中间结点为旋转轴向左侧（逆时针）旋转一次，具体步骤如下：

  1. 将A的右子树B提升为新二叉树的根。
  2. 将原来的A连同其左子树A向下旋转，使其成为B的左子树。
  3. 将B的原左子树B作为右子树连接到A上

LL型具体调整算法如下：

  1. //左旋
  2. Node_t LeftRotate(Node_t a) {
  3.     Node_t b;
  4.     b = a->right;
  5.     a->right = b->left;
  6.     b->left = a;
  7.     return b;
  8. }

LR型调整

image.png
插入操作，当3个结点不在一条直线，且均是左结点时，需要以插入结点为旋转轴向左侧（逆时针）旋转一次，然后向右侧（顺时针）旋转一次，即先做RR操作再做一次LL操作。具体步骤如下：
首先，执行RR旋转：

  1. 将B的右子树C提升为新二叉树的根。
  2. 将原来的B连同其左子树B向下旋转，使其成为C的左子树。
  3. 将C的原左子树C作为右子树连接到B上

然后，再执行LL旋转：

  1. 将A的左子树C提升为新二叉树的根。
  2. 将原来的A连同其右子树A向下旋转，使其成为C的右子树。
  3. 将B的原右子树C作为左子树连接到A上

LR型调整算法的具体过程如下：

  1. Node_t LeftRightRotate(Node_t a) {
  2.     a->left = LeftRotate(a->left);
  3.     return RightRotate(a);
  4. }

RL型调整

image.png
插入操作，当3个结点不在一条直线，且均是右结点时，需要以插入结点为旋转轴向右侧（顺时针）旋转一次，然后向左侧（逆时针）旋转一次，即先做LL操作再做一次RR操作。具体步骤如下：
首先，执行LL旋转：

  1. 将B的左子树C提升为新二叉树的根。
  2. 将原来的B连同其右子树B向下旋转，使其成为C的右子树。
  3. 将C的原右子树C作为右子树连接到B上

然后，再执行RR旋转：

  1. 将A的左子树C提升为新二叉树的根。
  2. 将原来的A连同其左子树A向下旋转，使其成为C的左子树。
  3. 将B的原左子树C作为右子树连接到A上

LR型调整算法的具体过程如下：

  1. Node_t RightLeftRotate(Node_t a) {
  2.     a->right = RightRotate(a->right);
  3.     return LeftRotate(a);
  4. }

插入操作

插入完成后需要从插入的结点开始维护一个到根结点的路径，每经过一个结点都要维护属的平衡，需要根据高度差的特点采取不同的旋转策略进行调整，使整棵树回复成平衡树。

  1. Node_t Insert(Type x, Tree t) {
  2.     if (t == NULL) {
  3.         t = new Node(x);
  4.     }
  5.     else if (x < t->data) {
  6.         t->left = Insert(x,t->left);
  7.         if (Height(t->left) - Height(t->right) == 2) {
  8.             if (x < t->left->data) {
  9.                 t = RightRotate(t);
  10.             }
  11.             else {
  12.                 t = LeftRightRotate(t);
  13.             }
  14.         }
  15.     }
  16.     else {
  17.         t->right = Insert(x, t->right);
  18.         if (Height(t->right) - Height(t->left) == 2) {
  19.             if (x > t->right->data) {
  20.                 t = LeftRotate(t);
  21.             }
  22.             else {
  23.                 t = RightLeftRotate(t);
  24.             }
  25.         }
  26.     }
  27.     t->height = max(Height(t->left), Height(t->right)) + 1;
  28.     return t;
  29. }
  31. int main() {
  32.     Tree t=new Node(1);
  33.     t=Insert(2, t);
  34.     t=Insert(3, t);
  35.     t=Insert(4, t);
  36.     t=Insert(5, t);    
  37.     cout << t->right->left->data << endl;
  38.     return 0;
  39. }

删除操作

首先定位要删除的结点，删除完成后，要从删除结点的父亲结点开始向上维护树的平衡一直到根结点，然后采取不同的旋转策略进行调整，使整棵树恢复成平衡树。
平衡二叉树删除操作算法的具体过程如下：