第9章查找 9.2 动态查找表《算法与数据结构（C＆Java）（第2版）》 同步教学（电子工业出版社）

9.1 基本概念 9.2 静态查找表 9.3 动态查找表 9.4 哈希表 第9章 查找 特点： 一、二叉排序树的定义 二、二叉排序树的插入与删除 三、二叉排序树的查找分析 四、平衡二叉树 五、B-树和B+树 9.3 动态查找表 表结构在查找过程中动态生成。 要求： 对于给定值key, 若表中存在其关键字等于key的记录，则查找成功返回； 否则插入关键字等于key 的记录。 典型的动态表———二叉排序树 一、二叉排序树的定义 （a） （b） 练：下列2种图形中，哪个不是二叉排序树 ？ ----或是一棵空树；或者是具有如下性质的非空二叉树： （1）左子树的所有结点均小于根的值； （2）右子树的所有结点均大于根的值； （3）它的左右子树也分别为二叉排序树。 讨论：对(a)中序遍历后的结果是什么？ 二、二叉排序树的插入与删除 将数据元素构造成二叉排序树的优点： ① 查找过程与顺序结构有序表中的折半查找相似，查找效率高； ② 中序遍历此二叉树，将会得到一个关键字的有序序列（即实现了排序运算）； ③ 如果查找不成功，能够方便地将被查元素插入到二叉树的叶子结点上，而且插入或删除时只需修改指针而不需移动元素。 注：若数据元素的输入顺序不同，则得到的二叉排序树形态也不同！ ——这种既查找又插入的过程称为动态查找。 二叉排序树既有类似于折半查找的特性，又采用了链表存储，它是动态查找表的一种适宜表示。 45 24 53 12 90 如果待查找的关键字序列输入顺序为： （24，53， 45，45，12，24，90）， 24 53 45 12 90 查找成功，返回 查找成功，返回 讨论1：二叉排序树的插入和查找操作 则生成二叉排序树的过程为： 例：输入待查找的关键字序列=（45，24，53，45，12，24，90） 则生成的二叉排序树形态不同： 查找成功，返回 查找成功，返回 二叉排序树的查找&插入算法如何实现？ 查找算法 静态查找算法 动态查找算法（插入） 二叉排序树的静态查找思想 若二叉排序树为空，则查找失败， 否则，先拿根结点值与待查值进行比较， 若相等，则查找成功， 若根结点值大于待查值，则进入左子树重复此步骤， 否则，进入右子树重复此步骤， 若在查找过程中遇到二叉排序树的叶子结点时，还没有找到待查结点，则查找不成功。 思考：如何编写算法？ 递归函数:  NODE *search(t,x) NODE *t; char x; { if(t==NULL) return(NULL);   else   {if(t->data==x) return(t); if(x<(t->data) return(search(t->lchild,x));   else  return(search(t->lchild,x)); } } 非递归函数见书: P196 二叉排序树的动态查找算法 查找算法： 若二叉排序树为空，则返回插入位置，否则，先拿根结点值与待查值进行比较，若相等，则查找成功，若根结点值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤。 插入算法： 若二叉排序树为空，则被查结点为新的根节点；否则，作为一个新的叶子结点插入在由查找返回的位置上。 二叉排序树的建立 对于已给定一待排序的数据序列,通常采用逐步插入结点的方法来构造二叉排序树,即只要反复调用二叉排序树的插入算法即可，算法描述为： BiTree *Creat (int n) //建立含有n个结点的二叉排序树 { BiTree *BST= NULL; for ( int i=1; i<=n; i++) { scanf(“%d”,&x); //输入关键字序列 InsertBST( BST,x); } return (BST); } 二叉排序树的删除: 要删除二叉排序树中的p结点，分三种情况： p为叶子结点，只需修改 p 双亲 f 的指针f->lchild=NULL 或 f->rchild=NULL p只有左子树或右子树 p只有左子树，用 p 的左孩子代替 p (1)(2) p只有右子树，用 p 的右孩子代替 p (3)(4) p左、右子树均非空 沿p左子树的根C的右子树分支找到S，S