数据结构第9章查找2动态查找表ppt课件

1、武汉科技大学Wuhan University of Science and Technology张 凯计算机学院 软件工程系2019年3月12日:第第9 9章章 查找查找查找的根本概念静态查找表动态查找表哈希表:v动态查找表动态查找表 9.2 动态查找表动态查找表 特点：表构造本身是在查找过程中动态生成的，即对于给定值 key ，假设表中存在关键字等于 key 的记录，那么查找胜利前往；否那么，插入关键字等于 key 的记录。 :v动态查找表动态查找表 9.2 动态查找表动态查找表 动态查找表主要有二叉树构造和树构造两种类型。二叉树构造有二叉排序树、平衡二叉树等。树构造有B-树、B+树等。:v

2、二叉排序树二叉排序树9.2 动态查找表动态查找表定义：二叉排序树或者是一棵空树；或者是具有如下特性的二叉树： 1假设它的左子树不空，那么左子树上一切结点的值均小于根结点的值； 2假设它的右子树不空，那么右子树上一切结点的值均大于根结点的值； 3它的左、右子树也都分别是二叉排序树。 :v二叉排序树二叉排序树9.2 动态查找表动态查找表45 12 53 3 37 61 99 24 90 78 caozhaodingchenwang二叉排序树 例： :v二叉排序树二叉排序树9.2 动态查找表动态查找表45 12 53 3 4861 99 24 90 78 caozhaobangchenwang例：

3、非二叉排序树 48bang:v二叉排序树的查找算法二叉排序树的查找算法9.2 动态查找表动态查找表 假设二叉排序树为空，那么查找不胜利；否那么1)假设给定值等于根结点的关键字，那么查找胜利； 2)假设给定值小于根结点的关键字，那么继续在左子树上进展查找； 3)假设给定值大于根结点的关键字，那么继续在右子树上进展查找。 :v二叉排序树二叉排序树9.2 动态查找表动态查找表30802090854035883250查找关键字：50, 35, 90, 95 503590例： 从根结点 出发，沿着左 分支或右分支 逐层向下直至 关键字等于给 定值的结点。 查找胜利 从根结点出 发，沿着左分支 或右分支逐

4、层向 下直至指针指向 空树为止。 查找失败:v二叉排序树的数据类型描画二叉排序树的数据类型描画9.2 动态查找表动态查找表struct BtreeNode ElemType key; /关键字关键字 BtreeNode *lchild, *rchild;/左、右孩子左、右孩子 BtreeNode, *Bitree;:v二叉排序树的查找算法描画二叉排序树的查找算法描画9.2 动态查找表动态查找表BiTree SearchBST(BiTree T, KeyType key) /假设查找胜利，那么前往指向该数据元素结点的指针假设查找胜利，那么前往指向该数据元素结点的指针 /否那么前往空指针。否那么前

5、往空指针。 if ( (!T) | key = T- data.key ) return(T); else if ( key data.key) return(SearchBST (T- lchild, key); /在左子树中继续查在左子树中继续查找找 else return(SearchBST (T- rchild, key); /在右子树中继续查在右子树中继续查找找 / SearchBST:v二叉排序树的插入算法二叉排序树的插入算法9.2 动态查找表动态查找表1) 假设二叉排序树为空树，那么新插入的结点为根结点； 2) 假设二叉排序树非空，那么新插入的结点必为一个新的叶子结 点，并且是查

6、找不胜利时查找途径上访问的最后一个结点 的左孩子或右孩子结点。 :v二叉排序树的插入算法二叉排序树的插入算法9.2 动态查找表动态查找表例： 插入 40， 插入 50， 是 37 的右孩子。 是 53 的左孩子。 45 12 53 3 37 61 99 24 90 78 5040:v二叉排序树的查找算法二叉排序树的查找算法9.2 动态查找表动态查找表Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree &p ) /假设查找胜利，那么指针假设查找胜利，那么指针 p 指向该数据元素结点，并前往指向该数据元素结点，并前往 TRUE

7、 /否那么指针否那么指针 p 指向查找途径上访问的最后一个结点，并前往指向查找途径上访问的最后一个结点，并前往 FALSE /指针指针 f 指向指向 T 的双亲，其初始调用值为的双亲，其初始调用值为NULL。 if (!T) p = f; return FALSE; / 查找不胜利查找不胜利 else if ( key = T- data.key ) p = T; return TRUE; / 查找胜利查找胜利 else if ( key data.key ) SearchBST (T - lchild, key, T, p ); / 在左子树中查找在左子树中查找 else SearchBST

8、 (T- rchild, key, T, p ); / 在右子树中查找在右子树中查找 / SearchBST :v二叉排序树的插入算法二叉排序树的插入算法9.2 动态查找表动态查找表Status InsertBST(BiTree &T, ElemType e ) / 当二叉排序树当二叉排序树 T 中不存在关键字等于中不存在关键字等于 e.key 的数据元素时，的数据元素时， / 插入插入 e 并前往并前往 TRUE，否那么前往，否那么前往 FALSE if (!SearchBST ( T, e.key, NULL, p ) / 查找不胜利查找不胜利 s = (BiTree) mallo

9、c (sizeof (BiTNode); s - data = e; s - lchild = s - rchild = NULL; if ( !p ) T = s; / 插入插入 s 为新的根结点为新的根结点 else if ( e.key data.key ) p - lchild = s; / 插入插入 s 为左孩子为左孩子 else p - rchild = s; / 插入插入 s 为右孩子为右孩子 return TRUE; else return FALSE; / 树中已有关键字一样的结点，不再插入树中已有关键字一样的结点，不再插入 / Insert BST :v二叉排序树的生成二叉

10、排序树的生成9.2 动态查找表动态查找表例：设查找的关键字序列为 45, 24, 53, 45, 12, 24, 90 可生成二叉排序树如下： 从空树开场，经过一系列的查找操作、插入操作之后，可生成一棵二叉排序树。 4553249012:v二叉排序树的建立二叉排序树的建立9.2 动态查找表动态查找表例：关键字序列 10、18、3、8、12、2、7、3 生成二叉排序树过程。1018381227注：二叉排序树与关键字陈列顺序有关，顺序不同，得到的二叉排序树也不同:v二叉排序树的建立的算法二叉排序树的建立的算法9.2 动态查找表动态查找表反复调用二叉排序树的插入算法即可Bitree Creat (i

11、nt n) /建立含有n个结点的二叉排序树 Bitree T= NULL; for ( int i=1; ix; /输入关键字序列 InsertBST ( T, x); return BST;:v中序遍历二叉排序树中序遍历二叉排序树9.2 动态查找表动态查找表15303778535063902970:v二叉排序树分析二叉排序树分析9.2 动态查找表动态查找表中序遍历二叉排序树可得到一个关键字的有序序列。 一个无序序列可经过构造二叉排序树而变成一个有序序列。构造树的过程就是对无序序列进展排序的过程。 插入的结点均为叶子结点，故无需挪动其他结点。相当于在有序序列上插入记录而无需挪动其他记录。 :v

12、二叉排序树上的删除二叉排序树上的删除9.2 动态查找表动态查找表 对于二叉排序树，删去树上一个结点相当于删去有序序列中的一个记录，在删除某个结点之后照旧要坚持二叉排序树的特性。如何在二叉排序树上删去一个结点呢如何在二叉排序树上删去一个结点呢? :v二叉排序树上的删除二叉排序树上的删除9.2 动态查找表动态查找表分三种情况进展讨论： (1)假设*p结点为叶子结点，即PL和PR均为空树。 由于删去叶子结点不破坏整棵树的构造，那么只需修正其双亲结点的指针。 (2)假设*p结点只需左子树PL或者只需右子树PR。 只需令PL或PR直接成为其双亲结点*f的左子树即可。(3)假设*p结点的左子树和右子树均不

13、空。 :v二叉排序树上的删除二叉排序树上的删除9.2 动态查找表动态查找表2)P只需左子树或右子树： P只需左子树，用P的左孩子替代P； SPPLQSPLQSPPLQSPLQ:v二叉排序树上的删除二叉排序树上的删除9.2 动态查找表动态查找表2)P只需左子树或右子树： P只需右子树，用P的右孩子替代P； SPPRQSPRQSPPRQSPRQ:v二叉排序树上的删除二叉排序树上的删除9.2 动态查找表动态查找表3)P左、右子树均非空 用P的直接前驱(或直接后继)取代PFPCDAQBSCGEPACBQCSPEDGF中序遍历从小到大陈列ACBQCSPEDGF:v二叉排序树上的删除二叉排序树上的删除9.

14、2 动态查找表动态查找表3)P左、右子树均非空 用P的直接前驱(或直接后继)取代PFPCDAQBSCGEPFPCDAQBCGESS:v二叉排序树上的删除二叉排序树上的删除9.2 动态查找表动态查找表3)P左、右子树均非空 用P的直接前驱(或直接后继)取代PFPCDAQBSCGEPFPCDAQBGEESC:v二叉排序树的删除算法二叉排序树的删除算法9.2 动态查找表动态查找表Status DeleteBST(BiTree &T, KeyType key) if(!T) return FALSE; /不存在关键字等于不存在关键字等于key的数据元素的数据元素 else if EQ(key,

15、 T-key) return Delete(T); /查找胜利查找胜利 else if LT(key，T-key) return DeleteBST (T-lchild,key); else return DeleteBST (T-rchild,key); /DelectBST:v二叉排序树的删除算法二叉排序树的删除算法9.2 动态查找表动态查找表Status Delete (BiTree &p) if(!p-rchild) /右子树空那么只需重接它的左子树右子树空那么只需重接它的左子树 q=p; p=p-lchild; free(q); else if (!p-lchild) /左子

16、树空那么只需重接它的右子树左子树空那么只需重接它的右子树 q=p; p=p-rchild; free(q); else q=p; s=p-lchild; while (s-rchild) q=s; s=s-lchild; /转左转左,然后向右到尽头然后向右到尽头 p-data=s-data; if(q!=p) q-rchild=s-lchild; else q-lchild=s-lchild; delete s; Return TRUE; /delete:v二叉排序树的查找分析二叉排序树的查找分析 9.2 动态查找表动态查找表二叉排序树上查找某关键字等于给定值的结点过程，其实就是走了一条从根到

17、该结点的途径。 30802090854035883250查找关键字：35 35比较的关键字次数 此结点所在层次数 最多的比较次数 树的深度 :v二叉排序树的平均查找长度二叉排序树的平均查找长度9.2 动态查找表动态查找表452412375393(45, 24, 53, 12, 37, 93) 114(1 223 3 3)66ASL 534512243793114(1 223 3 3)66ASL 折半查找断定树 二叉排序树 :v二叉排序树的平均查找长度二叉排序树的平均查找长度9.2 动态查找表动态查找表114(1 223 3 3)66ASL (12, 24, 37, 45, 53, 93) 37

18、1245245393452412375393121(1 23456)66ASL 折半查找断定树 二叉排序树 含有含有 n 个结点的二叉排序树的平均查找长度和树的形状有关个结点的二叉排序树的平均查找长度和树的形状有关 :v二叉排序树的查找分析二叉排序树的查找分析 9.2 动态查找表动态查找表最坏情况：插入的 n 个元素从一开场就有序， 变成单支树的形状！ 此时树的深度为 n; ASL = (n + 1) / 2 查找效率与顺序查找情况一样。 最好情况： ASL=log 2(n + 1) 1; 树的深度为：log 2n + 1; 与折半查找中的断定树一样。 形状比较平衡。 452412375393

19、452412375393:v二叉排序树的查找分析二叉排序树的查找分析 9.2 动态查找表动态查找表 设每种树态出现概率一样，查找每个关键字也是等概率的，那么有 n 个关键字的二叉排序树的平均查找长度12(1)logASLnn 由此可见，在随机的情况下，二叉排序树的ASL和logn是等数量级的。 问题：如何提高形状不平衡的二叉排序树的查找效率？ 处理方法：做“平衡化处置，即尽量让二叉树的外形平衡！ :v平衡二叉树平衡二叉树9.2 动态查找表动态查找表 平衡二叉树又称 AVL树，它是具有如下性质的二叉树： 即： |左子树深度右子树深度| 1u 左、右子树是平衡二叉树；u 一切结点的左、右子树深度之

20、差的绝对值 1。 :v例：判别以下二叉树能否例：判别以下二叉树能否 AVL 树？树？ 9.2 动态查找表动态查找表非平衡二叉树 1-100-110平衡二叉树 0012-10:v平衡二叉树平衡二叉树9.2 动态查找表动态查找表 为了方便起见，给每个结点附加一个数字， 数字=该结点左子树与右子树的深度差。这个数字称为结点的平衡因子。这样就可得到AVL树的其它性质任一结点的平衡因子只能取：-1、0 或 1；假设树中恣意一个结点的平衡因子的绝对值大于 1，那么这棵二叉树就失去平衡。 对于一棵有 n 个结点的 AVL 树，其深度和 log n 同数量级， ASL 也和 log n 同数量级。 :v平衡二

21、叉树平衡二叉树9.2 动态查找表动态查找表 假设在一棵AVL树中插入一个新结点，就有能够呵斥失衡，此时必需重新调整树的构造，使之恢复平衡。我们称调整平衡过程为平衡旋转。平衡旋转可以归纳为四类：v LL平衡旋转v RR平衡旋转v LR平衡旋转v RL平衡旋转:v平衡二叉树平衡二叉树9.2 动态查找表动态查找表 假设在一棵AVL树中插入一个新结点，就有能够呵斥失衡，此时必需重新调整树的构造，使之恢复平衡。我们称调整平衡过程为平衡旋转。平衡旋转可以归纳为四类：v LL平衡旋转v RR平衡旋转v LR平衡旋转v RL平衡旋转:v平衡二叉树平衡二叉树9.2 动态查找表动态查找表假设在 A 的左子树的左子树上插入 结点，使 A 的平衡因子从 1 添加 至 2， 需求进展一次顺时针旋转。 (以 B 为旋转轴 1) LL 平衡旋转： CBA A:v平衡二叉树平衡二叉树9.2 动态查找表动态查找表假设在 A 的右子树的右子树上插入 结点，使 A