查找——树表——>二叉排序树

树表

• 表结构在查找过程中动态生成
• 对于给定值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（单支树）