经验分享 – 查找——树表——>二叉排序树

树表

  • 表结构在查找过程中动态生成
  • 对于给定值key
    若表中存在,则成功返回;
    否则插入关键字等于key 的记录

二叉排序树

  • 二叉排序树或是空树,或是满足如下性质的二叉树:
    – 若其左子树非空,则左子树上所有结点的值均小于根结点的值;
    – 若其右子树非空,则右子树上所有结点的值均大于等于根结点的值;
    – 其左右子树本身又各是一棵二叉排序树

    在这里插入图片描述

    在这里插入图片描述

    >中序遍历二叉排序树后**得到一个关键字的递增有序序列**


二叉排序树的操作-查找

  • 若查找的关键字等于根结点,成功
  • 否则
    – 若小于根结点,查其左子树
    – 若大于根结点,查其右子树
  • 在左右子树上的操作类似
  • 算法思想
    – 若二叉排序树为空,则查找失败,返回空指针。
    – 若二叉排序树非空,将给定值key与根结点的关键字T->data.key进行比较:
    – 若key等于T->data.key,则查找成功,返回根结点地址;
    – 若key小于T->data.key,则进一步查找左子树;
    – 若key大于T->data.key,则进一步查找右子树。
  • 算法描述 “`cpp
    BSTree SearchBST(BSTree T, KeyType key){
    if((!T) || key == T->data.key) return T;
    //在左子树中继续查找
    else if(key < T->data.key) return SearchBST(T->lchild, key);
    //在右子树中继续查找
    else return SearchBST(T->rchild, key);
    }
    “`

二叉排序树的操作-插入

  • 若二叉排序树为空,则插入结点应为根结点
  • 否则,继续在其左、右子树上查找
    – 树中已有,不再插入
    – 树中没有,查找直至某个叶子结点的左子树或右子树为空为止,则插入结点应为该叶子结点的左孩子或右孩子
  • 插入的元素一定在叶结点
    在这里插入图片描述

二叉排序树的操作-生成

从空树出发,经过一系列的查找、插入操作之后,可生成一棵二叉排序树

  • 不同插入次序的序列生成不同形态的二叉排序树
在这里插入图片描述

二叉排序树的操作-删除

  • 将因删除结点而断开的二叉链表重新链接起来
  • 防止重新链接后树的高度增加
在这里插入图片描述
  • 删除叶结点,只需将其双亲结点指向它的指针清零,再释放它即可。
  • 被删结点缺右子树,可以拿它的左子女结点顶替它的位置,再释放它。
  • 被删结点缺左子树,可以拿它的右子女结点顶替它的位置,再释放它。
  • 被删结点左、右子树都存在,可以在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删结点中,再来处理这个结点的删除问题

查找性能分析

在这里插入图片描述

第 i 层结点需比较 i 次

  • 上述两图的平均查找长度为:
    在这里插入图片描述
  • 平均查找长度和二叉树的形态有关
    – 最好:log2 n(形态匀称,与二分查找的判定树相似)
    – 最坏: (n+1)/2(单支树)
正文完