Skip to content

Latest commit

 

History

History
302 lines (240 loc) · 13.5 KB

15 二叉排序树BST与平衡二叉树AVL.md

File metadata and controls

302 lines (240 loc) · 13.5 KB

#数据结构 #算法 #C

【预先知识】
本章虽然属于树的章节内容，但是内容较难，并且与查找和排序的知识紧密相连，因此，建议先学习完毕 查找、排序 章节后，再结合这两个章节的知识，阅读本章。

[55] 二叉排序树

二叉排序树，又称二叉查找树、二叉搜索树（BST，Binary Search Tree），符合这样的特点：一棵是空二叉树，或者是具有如下性质的二叉树：

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

对二叉排序树，进行中序遍历，可以得到一个递增的有序序列。

1. BST 的查找

查找思路分析：

  1. 若树非空，目标值与根结点的值比较；
  2. 若相等，则查找成功；
  3. 若小于根结点，则在左子树上查找，否则在右子树上查找，重复该步骤。
  4. 查找成功，返回结点指针；查找失败返回NULL。
// BST结点定义
typedef struct BSTNode {
    int key;
    struct BSTNode *lchild, *rchild;
} BSTNode, *BSTree;

// 在BST中查找值为target的结点
BSTNode *BSTSearch(BSTree T, int target)
{   
    // 树若是空的或者等于根结点的值，就可以直接结束循环
    while (T != NULL && target != T->key) {
        if (target < T->key) {  // target小于根结点的值，查找其左子树
            T = T-> lchild;     // T 往下深一层，执行下一次循环
        } else {                // target大于根结点的值，查找其右子树
            T = T->rchild;      // T 往下深一层，执行下一次循环
        }
    }
    return T;
}

以上程序属于非递归（循环）的实现，如果使用递归同样可以实现：

// 递归实现二叉排序树查找
BSTNode *BSTSearch(BSTree T, int target)
{
    if (T == NULL) {
        return NULL;                        // 查找失败
    }

    if (target == T->key) {
        return T;                           // 查找成功
    } else if (target < T->key){
        return BSTSearch(T->lchild, target);   // 在左子树中找
    } else if (target > T->key){
        return BSTSearch(T->rchild, target);   // 在右子树中找
    }
}

综合比较，循环实现的最坏空间复杂度是 $O(1)$，递归实现的最坏空间复杂度是 $O(h)$。综合判断，循环实现效果更好。

2. BST 的结点插入

算法实现：

  • 若原二叉排序树为空，则直接插入结点；
  • 否则，若关键字k小于根结点值，则插入到左子树，若关键字k大于根结点值，则插入到右子树。

这里依靠递归实现：

// 在二叉排序树插入关键字为k的新结点(递归实现)
bool BSTInsert(BSTree &T, int data)
{
    // 原树为空，插入新结点
    if (T == NULL) {
        T = (BSTree)malloc(sizeof(BSTNode));
        T->key = data;
        T->lchild = T->rchild = NULL;
        return true;
    }

    // 已经存在相同关键字的结点，插入失败
    if (data == T->key) {
        return false;
    } else if (data < T->key) {
        return BSTInsert(T->lchild, data);     // 插入到T的左子树
    } else {
        return BSTInsert(T->rchild, data);     // 插入到T的右子树
    }
}

对于二叉排序树的插入而言，新插入的结点一定是叶子，并且使用递归，最坏空间复杂度为$O(h)$。

依靠循环迭代实现：

bool BSTInsert(BSTree &T, int data)
{
    while(T != NULL){
        if(data == T->key) {
            return false;
        } else if (data < T->key) {
            T = T->lchild;     // 继续找其左孩子
        } else {
            T = T->rchild;     // 继续找其右孩子
        }
    }

    T = (BSTree)malloc(sizeof(BSTNode));
    T->key = data;
    T->lchild = T->rchild = NULL;
    return true;
}

3. BST 的构造

【问题】
如何依照序列array[n]建立BST？
【实现】
按照序列，依次插入二叉排序树中。

// 按照array[]中关键词序列依次建立二叉排序树
void CreateBST(BSTree &T, int array[], int n)
{
    T = NULL;           // 二叉树初始化为空树
    int i = 0;
    while (i < n)
    {
        // 依次调用BST插入函数，插入数组每个元素
        BSTInsert(T, array[i]);
        i++;
    }
}

同一组数字，按照不同的先后顺序，可能构造的二叉树的形状会有区别。

4. BST 的数据删除

先搜索找到目标结点：

  1. 若被删除结点z是叶结点，则直接删除，不会破坏二叉排序树的性质。

  1. 若结点z只有一棵左子树或右子树，则让z的子树成为z父结点的子树，替代z的位置。

  1. 若结点z有左、右两棵子树，这个时候右两种方法：
    • 则令z的直接后继替代z，然后从二叉排序树中删去这个直接后继，这样就转换成了第一或第二种情况。
    • 或者令z的直接前驱替代z，然后从二叉排序树中删去这个直接前驱，这样也转换成了第一或第二种情况。

注意某个结点的直接前驱和直接后继：

  • z的后继：z的右子树中最左下结点（该结点一定没有左子树）。
  • z的前驱：z的左子树中最右下结点（该结点一定没有右子树）。

5. BST 的效率分析

查找长度，在查找运算中，需要对比关键字的次数称为查找长度，反映了查找操作时间复杂度。 查找成功的平均查找长度 $ASL, Average Search Length$：若树高 $h$，找到最下层的一个结点需要对比 $h$ 次。

  • 最好情况：n个结点的二叉树最小高度为 $⌊log_2{n}⌋+ 1$ 。平均查找长度= $O(log_2{n})$。

  • 最坏情况：每一个结点只有一个分支，树高度为h，结点树 n = h，平均查找长度= $O(N)$。

查找失败的的平均查找长度（ASL）也可以进行计算。每一个查找失败的可能性均等分布在叶子结点的左右孩子空指针，而查找长度是其所在的层数。

[56] 平衡二叉树的性质

平衡二叉树（Balanced Binary Tree），简称平衡树（AVL树），由G. M. Adelson-Velsky和E. M. Landis 于1962年发明。
AVL树上任一结点的左子树和右子树的高度之差不超过1。即：

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

平衡二叉树结点的平衡因子的值只可能是−1、0或1。只要有任一结点的平衡因子绝对值大于1，就不是平衡二叉树。

// 平衡二叉树结点
typedef struct AVLNode
{
    int key;            // 数据域
    int balance;        // 平衡因子
    struct AVLNode *lchild, *rchild;
} AVLNode, *AVLTree;

对于一个二叉排序树来说，如果它也刚好是平衡二叉树，那么它的查找时间复杂度，就能够保证在 $O(\log_{2}{N})$ 阶内。

[57] 平衡二叉树的插入与再平衡

1. AVL的插入

在二叉排序树中插入新结点后，查找路径上的所有结点都有可能受到影响。

【问题】 原先的平衡二叉树，现如今变成了非平衡状态。那么，如何调整二叉排序树，使其重新变成平衡二叉树？ 【解决方法】 从插入点往回找到第一个不平衡结点，调整以该结点为根的子树，这个子树叫做“最小不平衡子树”。

以上图为例，以70为根结点的子树，即是“最小不平衡子树”。调整完成，该BST又重新恢复平衡。

分析得出，调整最小不平衡子树，有以下四种情况：

  • 在A的左孩子的左子树中插入导致不平衡（LL）；
  • 在A的右孩子的右子树中插入导致不平衡（RR）；
  • 在A的左孩子的右子树中插入导致不平衡（LR）；
  • 在A的右孩子的左子树中插入导致不平衡（RL）；

2. 调整最小不平衡子树（LL）

【场景】A的左孩子的左子树中插入导致不平衡。
如图，使用方框代表一个抽象的子树，高度为H。经过LL型插入后左孩子的左子树高度变成了H+1。这个时候A的平衡因子由1变成2，导致了不平衡。 在这里使用三个抽象树都是高度H，原因是因为，这里刚好设置的高度满足，LL插入后可以立即形成一个最小不平衡树，可以举例AR的高度是H+1，试一试即可证明。

【调整方法】LL平衡旋转（右单旋转）。
二叉排序树的特性：左子树结点值 < 根结点值 < 右子树结点值，所以：BL < B < BR < A <AR。
由于在结点A的左孩子（L）的左子树（L）上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作。 将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树。

代码实现：

// 假设A的结点指针是f - father，父结点指针是gf - grandfather，B的结点指针是p。
f->lchild = p->rchild;      // 把BR变成AL
p->rchild = f;              // A成B的右子树
gf->lchild/rchild = p;      // B变成gf的子树 左右未知

3. 调整最小不平衡子树（RR）

【场景】A的右孩子的右子树中插入导致不平衡。
【调整方法】RR平衡旋转（左单旋转）。

由于在结点A的右孩子（R）的右子树（R）上插入了新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要一次向左的旋转操作。
将A的右孩子B向左上旋转代替A成为根结点，将A结点向左下旋转成为B的左子树的根结点，而B的原左子树则作为A结点的右子树。
代码实现：

// 假设A的结点指针是f - father，父结点指针是gf - grandfather，B的结点指针是p。
f->rchild = p->lchild;      // 把BL变成AR
p->rchild = f;              // A成B的右子树
gf->lchild/rchild = p;      // B变成gf的子树

4. 调整最小不平衡子树（LR）

【场景】A的左孩子的右子树中插入导致不平衡。
【分析】分解它的左孩子的右子树，提取出一个公共根结点和根结点的左右子树。

【调整方法】LR平衡旋转（先左旋，后右旋转）。 由于在A的左孩子（L）的右子树（R）上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。

  1. 先将A结点的左孩子B的右子树的根结点C，向左上旋转提升到B结点的位置。
  2. 然后再把该C结点向右上旋转提升到A结点的位置。 图中以插入结点在C的右子树CR中，等量换做到CL上依然可以按照相同方法保证调整成功。

4. 调整最小不平衡子树（RL）

【场景】A的右孩子的左子树中插入导致不平衡。
【分析】分解它的左孩子的右子树，提取出一个公共根结点和根结点的左右子树。
【调整方法】RL平衡旋转（先右旋，后左旋转）。
由于在A的右孩子（R）的左子树（L）上插入新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。

  1. 先将A结点的右孩子B的左子树的根结点C向右上旋转，提升到B结点的位置；
  2. 然后再把该C结点向左上旋转提升到A结点的位置。

图中以插入结点在C的左子树CL中，等量换做到CR上依然可以按照相同方法保证调整成功。

5. 总结

只有左孩子才能右上旋，右孩子才能左旋。每次旋转都会导致孩子成为父亲，父亲成为孩子。

在插入结点中，只要将最小不平衡子树调整平衡，则其他祖先结点都会恢复平衡。操作导致“最小不平衡子树”高度+1，经过调整后高度恢复。

6. 查找效率分析

若树高为h，则最坏情况下，查找一个关键字最多需要对比 h 次，即查找操作的时间复杂度不可能超过 $O(h)$。

平衡二叉树性质，树上任一结点的左子树和右子树的高度之差不超过1。
假设以 $n_h$ 表示深度为 $h$ 的平衡树中含有的最少结点数。 则有 $$n_0= 0, n_1 = 1, n_2 = 2$$ 并且有： $$n_h = n_{h−1} + n_{h−2} + 1$$ 可以证明，含有n个结点的平衡二叉树的最大深度为 $O(log_2n)$ ，平衡二叉树的平均查找长度为 $O(log_2n)$ 。

[58] 平衡二叉树的删除

#未完待续