第19讲 动态查找表.pptVIP

特点： 表结构在查找过程中动态生成的， 即对于给定的值Key，若表中存在其关键字等于Key的记录，则查找成功返回，否则插入关键字等于Key的记录。 二叉排序树 定义：二叉排序树或是一棵空树，或是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值 它的左、右子树也分别为二叉排序树 要删除二叉排序树中的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的右子树为空，将S的左子树成为S的双亲Q的右子树，用S取代p； (5) 若C无右子树，用C取代p。 (6) * 动态查找表 二叉排序树又称二叉查找树 45 12 53 3 37 24 100 61 90 78 按中序遍历： 3，12，24，37，45，53，61，78，90，100 递增 中序遍历二叉排序树可得到一个关键字的有序序列 例 若查找的值等于根结点的关键字的值，成功； 若小于根结点的关键字值，查其左子树； 若大于根结点的关键字值，查其右子树。在左右子树上的操作类似。 122 250 300 110 200 99 105 230 216 1、查找过程 显然，在二叉排序树中查找某结点其实是从根结点出发走了一条从根到待查结点的路径。 40 24 55 12 37 12 24 37 40 55 40，24，12，37，55 12，24，37，40，55 考虑如下两种不同插入次序的序列构成的二叉排序树， 插入次序分别为： 插入次序分别为： 40 24 55 12 37 12 24 37 40 55 40，24，12，37，55 12，24，37，40，55 显然，第i 层结点需比较 i 次。在等概率的前提下，上述两图的平均查找长度为： 易知： 在二叉排序树中进行查找的平均查找长度和二叉树的形态有关，即， 最坏: （n+1）/2（与顺序查找相同） 最好：log2n（与折半查找的判定树相同） 插入原则： 若二叉排序树为空，则插入结点应为新的根结点；否则，继续在其左、右子树上查找，直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子. 45 12 53 3 37 24 100 61 90 78 20 2. 二叉排序树的插入 例如：在右图给定的二叉排序树中插入结点20 例 {10， 18， 3， 8， 12， 2， 7， 4} 10 10 18 10 18 3 10 18 3 8 10 18 3 8 12 10 18 3 8 12 2 10 18 3 8 12 2 7 10 18 3 8 12 2 7 4 二叉排序树生成：从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树 3. 二叉排序树的删除 S P Q S Q PL P 中序遍历：Q S PL P S Q PL 中序遍历：Q S PL (2) S P PL Q 中序遍历：PL P S Q S PL Q 中序遍历：PL S Q (1) 6 3 4 2 15 6 3 4 2 18 15 删除18 p只有左子树，用p的左孩子代替p 中序遍历：P PR S Q S PR Q 中序遍历：PR S Q (3) S P PR Q 中序遍历：Q S P PR S Q PR 中序遍历：Q S PR (4) S Q PR P 6 3 4 2 18 15 6 3 4 2 18 12 15 删除12 p只有右子树，用p的右孩子代替p 中序遍历：CL C ……QL Q SL S P PR F F P C PR CL Q QL S SL F S C PR CL Q QL SL 中序遍历：CL C ……QL Q SL S PR F (5) p左右 子树均 非空 F P C PR CL 中序遍历：CL C P PR F F C PR CL 中序遍历：CL C PR F (6) 10 3 6 2 4 18 12 15 6 3 4 2 18 12 15 删除10