第九章查找.ppt

《第九章查找.ppt》由会员分享，可在线阅读，更多相关《第九章查找.ppt（64页珍藏版）》请在三一文库上搜索。

1、第九章 查找,基本概念,查找表 由同一类型的数据元素构成的集合 静态查找表 对查找表的查找仅是以查询为目的，不改动查找表中的数据 动态查找表 可以在查找表中插入不存在的记录，或删除某个已存在的记录 关键字 数据元素（或记录）的某个数据项，能用来标识一个数据元素 查找 指定关键字，在表中查找,基本概念（续）,查找成功 查找表中存在满足条件的记录 查找不成功 查找表中不存在满足查找条件的记录。 内查找 整个查找过程都在内存中进行。 外查找 在查找过程中需要访问外存。 平均查找长度ASL查找方法时效的度量 为确定记录在查找表中的位置，需将关键字和给定值比较次数的期望值。 查找成功时的ASL计算方法：

2、 n：记录的个数 pi：查找第i个记录的概率，( 不特别声明时认为等概率 pi =1/n ) ci：找到第i个记录所需的比较次数,静态查找表,顺序表的查找 通常查找表中的各元素（或记录）的关键字的值是无序的。 “哨兵”：数据安排在1n，给定值放在第0个记录处，从后向前查找，直到找到所查记录为止。记录0像哨兵一样看守着查找表下界，不会越界。,typedef struct ElemType *elem; int length; STable;,顺序表算法,不使用哨兵 int seq_search( SSTable l, KeyType key) for (i = 0; i l.length; i+

3、) if (l.elemi = key) return i; return -1; ,使用哨兵 int seq_search( SSTable l, KeyType key) l.elem0.key=key; for (i = l.length; l.elemi.key != key; i-); return i; ,顺序表算法:采用链表结构,无头单链表 struct ELEM *seq_search( KeyType key) for (p = head; p != NULL; p = p-next) if (p-key = key) return p; return NULL; ,无头单链

4、表在链尾设置专用的“哨兵”记录，可减少比较次数 struct ELEM *seq_search( KeyType key) tail-key = key; for (p = head; p-key != key; p = p-next); return p = tail ? NULL : p; ,顺序表算法性能分析,性能分析 查找成功时 ASLs(n)= =(1+2+ . +n)/n=(n+1)/2 查找失败时 ASLf =n+1,有序表的查找,有序表 查找表中的各记录的关键字的值是有序的 顺序查找 不需比较到表尾，只需比较到比给定值大的记录 折半查找（二分查找） 将给定值与中间的记录进行比较

5、 若找到则查找成功； 否则：若比中间记录小，则对前一半子表进行折半查找，反之对后一半子表进行折半查找 折半查找的限制 顺序表 事先排好序 折半查找的性能不是查找算法的性能极限,折半查找算法及性能分析,查找性能分析 折半查找每次只查表的一半，其所有记录的查找路径构成一棵二叉树，称为折半查找树（或判定树），每次查找只走了该树的一条分支，故平均查找长度不超过 log2n + 1,int binsearch (SSTable ST, keytype key) low= 1; high = ST.length; while (low = high) mid = (low + high) / 2; if

6、(key=ST.elemmid.key) return mid; else if ( key ST.elemmid.key) high = mid - 1; else high = mid+1; return 0; ,索引顺序表的查找,索引顺序表 带索引表的顺序表 索引部分一定是有序的，这部分可用折半查找等方法 顺序表本身不一定有序，要根据顺序表是否有序而选用相应的查找方法 分块查找（blocking search） 将索引部分和表体部分分开查找的方法。 索引表的平均查找长度为两部分查找之和。,动态查找表,二叉排序树 平衡二叉树 B-树和B树,二叉排序树,特点：用于频繁进行插入、删除、查找的表

7、。 二叉排序树：空或有一个根，根的左子树若非空，则左子树上的所有结点的关键字值 均小于根结点的值。根的右子树若非空，则右子树上的所有结点的关键 字值均大于根结点的值。根结点的左右子树同样是二叉排序树。,二叉排序树,1、查找算法： 思路：若根结点的关键字值等于查找的关键字，成功。 否则，若小于根结点的关键字值，查其左子树。 若大于根结点的关键字值，查其右子树。 在左右子树上的操作类似。,122,250,300,110,200,99,105,230,216,Bitree SearchBST ( BiTree T, KeyType key ) / 在二叉排序树查找关键字之值为 key 的结点，找到返

8、回该结 / 点的地址，否则返回空。T 为二叉排序树的根结点的地址。 if ( !T | EQ( key, T -data. key ) ) return ( T ) ; else if ( LT( key , T -data. key ) ) return (SearchBST ( T - lchild, key ); else return (SearchBST ( T - rchild, key ); ,例：122、99、250、110、300、280作为二叉排序树的结点的关键字值，生成二叉排序树。,二叉排序树的插入,执行查找算法，找出被插结点的父亲结点 判断被插结点是左/右孩子。将被插结

9、点作为叶子插入 若二叉树为空。则首先单独生成根结点。 注意：新插入的结点总是叶子结点。,122,250,300,110,280,99,二叉排序树插入算法,struct Node *root, *pptr; /* 全局变量 */ Status SearchBst(struct Node *t, KeyType key) if (t = NULL) return FALSE; else if (key = t-key) return TRUE; else if (key key) pptr = ,二叉排序树的查找分析,最好和最糟情况（折半查找/顺序查找）,下述两种情况下的成功的平均查找长度 ASL

10、,平均情况下，log2n数量级,二叉排序树的删除（1）,（1）叶子结点：直接删除，更改它的父亲结点的相应指针域为空。 如：删除数据域为 15、70 的结点。,15,60,70,30,20,50,60,30,20,50,二叉排序树的删除（2）,122,250,300,110,200,99,105,230,216,400,450,500,（2）被删结点的左孩子为空或者右孩子为空： 如下图所示，删除结点的数据域为 99 的结点。,被删结点,122,250,300,200,230,216,400,450,500,110,105,删除,99,二叉排序树的删除（3a）,(3)被删结点的左、右子树皆不空。

11、维持二叉排序树的特性不变。 在中序遍历中紧靠着被删结点的结点才可以替代被删节点 做法1:左子树中最大的结点做替身, 选左子树最右结点，其右孩子必为空,做法：将替身的数据域复制到被删结点的数据域 将结点110的左孩子作为 110的父结点99的右孩子(选中的结点110右孩子必为空),二叉排序树的删除（3b）,200,250,300,110,99,105,230,216,400,450,500,做法：将替身的数据域复制到被删结点的数据域。 将结点200的右孩子作为200的父结点250的左孩子。注意：结点 200左孩子必为空,右子树中最小的结点做替身。 选右子树中的最左的结点，其左孩子指针必为空,二叉

12、排序树的删除（3c）,F,C,Q,QL,S,SL,做法2：删除节点，原左子树补上来，原右子树做原左子树最右节点的右子树 (或对称的：原右子树补上来，原左子树做原右子树最左节点的左子树),二叉排序树的删除算法(1),全局变量struct NODE *pptr; Status DeleteBST (struct Node *t，KeyType key) if (t = NULL) / 二叉排序树 t 中不存在关键字为 key 的结点 return FALSE; else if (key = t- key) DeleteNode(t); / 存在关键字为 key 的结点，进行删除 else if (

13、key key) pptr = ,二叉排序树的删除算法(2),Status DeleteNode(struct Node *p) / 在二叉排序树中删除地址为 p 的结点，并保持二叉排序树的性质不变。 if (p-rchild = NULL) *pptr = p-lchild ; else if (p-lchild = NULL) *pptr = p-rchild; else *pptr = p-lchild; for (s = p-lchild; s-rchild !=NULL; s = s-rchild); s-rchild = p-rchild; free(p); ,动态查找表平衡二叉树

14、,起因：提高查找速度，避免最坏情况出现。如下图情况的出现。虽然完全二叉树的树型最好，但构造困难。常使用平衡树。,动态查找表平衡二叉树,平衡二叉树 平衡二叉树又称 AVL树(Adelson-Velskii & Landis于 1962年发明)，它具有如下性质： 或者为空树， 或者根结点的左、右子树也均为平衡二叉树，且左、右子树的树高之差的绝对值不超过1。 平衡因子 结点的左子树高度减去右子树高度的值称为该结点的平衡因子。 平衡二叉树也可以这样定义：平衡二叉树是所有结点的平衡因子的绝对值均小于2的二叉树。结点的平衡因子为 1、1、0,注意：完全二叉树必为平衡树，平衡树不一定是完全二叉树。,动态查找

15、表平衡二叉树,平衡二叉树的插入,要求：插入之后仍保持平衡二叉树的性质不变,在平衡树中插入数据域为 2 的结点,平衡二叉树的插入,插入操作解决方案： 1. 新结点插入后，找到平衡因子越轨的结点，调整以此节点为根的子树,调整后，子树高度一定要保持不变（能做到吗？） 2. 不涉及到危机结点的父亲结点 3. 仍保持平衡二叉树的性质不变。,平衡二叉树的插入,右旋转处理,中序序列,平衡二叉树的插入,平衡二叉树的插入LL,左处理（新插入结点出现在危机结点的左子树上进行的调整）的情况分析(设插入前树高h) 1、LL 情况：（LL：表示新插入结点在危机结点的左子树的左子树上）,A,B,+1,h-1,0,+2,+

16、1,h-2,h-2,LL 处理,BL,BR,AR,B,A,0,h-1,0,h-2,h-2,BL,BR,AR,危机结点,处理前：高度为 h + 1 中序序列：,A,B,BL,BR,AR,处理后：高度为 h 中序序列：,A,B,BL,BR,AR,注意：处理后 平衡因子为 0,A,B,右旋转A,平衡二叉树的插入LR(a),2、LR 情况：（LR：表示新插入结点在危机结点的左子树的右子树上） 情况A：,左旋转B然后右旋转A,平衡二叉树的插入LR(b),LR :新插入结点在危机结点的左子树的右子树上 情况B：,左旋转B然后右旋转A,平衡二叉树的插入LR(c),LR：表示新插入结点在危机结点的左子树的右子

17、树上 情况C：,平衡二叉树的插入右处理,右处理（新插入结点出现在右子树上需进行的调整）： 1、RR 情况： （RR：表示新插入结点在危机结点的右子树的右子树上） 处理图形和 LL 镜象相似 2、RL 情况： （RL：表示新插入结点在危机结点的右子树的左子树上） A、处理图形和 LRA 镜象相似 B、处理图形和 LRB 镜象相似 C、处理图形和 LRC 镜象相似,平衡二叉树的插入举例,例：有一组关键字序列JAN、FEB、MAR、APR、MAY、JUN、JUL、AUG、SEP、OCT、NOV、DEC，以此建立 AVL 树。,平衡二叉树的插入举例（续）,平衡二叉树的查找分析,具有 N 个结点的平衡树

18、，高度 h 满足： log2(N+1) h loga(sqrt(5)*(N+1) - 2 其中：a (1sqrt(5)/2 查找的时间复杂度O(logn),平衡二叉树的查找分析（续）,构造一系列结点个数最少的平衡二叉树， T1, T2 , T3 ,Th；这种树的高度分别为 1、2、3、h。,T1 高度 h = 1 结点个 数最少,T2 高度 h = 2 结点个 数最少,T3 高度 h = 3 结点个 数最少,有th = th-2 + th-1 + 1 该数的序列为 1、2、4、7、12、20、33、54、88 . 而 Fibonacci 数列为：0、1、1、2、3、5、8、13、21、34、5

19、5、89 所以： t(h) = f(h+2) - 1；于是转化为求 Fibonacci 数的问题。 由于： f(h) h/ sqrt(5); (1sqrt(5)/2 ,Fibonacci 数列和2n比较,AVL插入算法:数据结构,struct Node ElemType data; int bf; struct Node *lchild, *rchild; ; #define LH +1 /* 左子树高 */ #define EH 0 /* 等高 */ #define RH -1 /* 右子树高 */,AVL插入算法:右旋/左旋,void R_Rotate(struct Node *pp) p

20、 = *pp; lc = p-lchild; p-lchild = lc-rchild; lc-rchild = p; *pp = lc; void L_Rotate(struct Node *pp) p = *pp; rc = p-rchild; p-rchild = rc-lchild; rc-lchild = p; *pp = rc; ,AVL插入算法:简单情况,int InsertAVL(struct Node *pp, ElemType e) /返回值：-1未插入，0高度不变，1增高 T = *pp; if (T = NULL) / 递归出口 *pp = T = malloc(siz

21、eof(struct Node); T-data = e; T-lchild = T-rchild = NULL; T-bf = EH; return 1; else if (e.key = T-Data.key) return -1; else if (e.key Data.key) .,AVL插入算法:左/右子树插入, else if (e.key Data.key) result = InsertAVL( ,AVL插入算法:平衡处理,void LeftBalance(struct Node *pp) a = *pp; b = a-lchild; switch (b-bf) case LH

22、: a-bf = b-bf = EH; R_Rotate(pp); break; case RH: c = b-rchild; switch (c-bf) case LH: a-bf = RH; b-bf = EH; break; case EH: a-bf = b-bf = EH; break; case RH: a-bf = EH; b-bf = LH; break; c-bf = EH; L_Rotate( ,平衡二叉树的删除算法,参照二叉排序树中的算法，删除后修正平衡因子，若平衡性被破坏，利用单一/双重旋转恢复。,红黑树,树的每个结点都被着上了红色或者黑色，结点所着的颜色被用来检测树的

23、平衡性 。1972年由Rudolf Bayer发明的。它的平衡性要求比AVL树梢宽松，实践证明该算法效率很高,动态查找表： B 树和 B+ 树,为什么采用B_ 树和 B+ 树？ 海量数据存放在外存中，不可能一次全部调入内存。因此，要多次 访问外存。但硬盘的驱动受机械运动的制约，速度慢。所以，主要矛盾变为减少访外次数。 在 1970 年由 R bayer 和 E macreight 提出用B_ 树作为索引组织文件。提高访问速度、减少时间。,内存,例如: 用二叉树组织文件，当文件的记录个数为 100，000时，要找到给定关键字的记录，需访问外存17次（log100,000）,太长了！,50,25,

24、10,75,15,35,60,90,20,30,40,55,70,80,95,索引文件,数据文件,文件头，可常驻内存,文件访问示意图：索引文件、数据文件存在盘上,B树,B树是一种平衡的多路查找树，主要应用在文件系统中。 一棵 m 阶的B树，或为空树，或为满足下列特性的 m 叉树： 树中每个结点最多有 m 棵子树； 若根结点不是叶子结点，则最少有两棵子树； 除根之外的所有非终端结点最少有 m/2 棵子树； 所有非终端结点包含(n,A0,K1,A1,K2,Kn,An)信息数据； 其中：n为结点中关键字个数，Ai为指向子树的指针，Ki为关键字。 A0： K1 且 Kn 的结点的地址（指在该 B_ 树

25、中） 注意：K1 K2 . Kn 所有叶子结点在同一层次上，不带信息。,B树,例如：m = 4 阶B树。除根结点和叶子结点之外，每个结点的孩子个数 至少为 m/2 = 2 个；结点的关键字个数至少为 1 。 该B树的深度为 4。 叶子结点都在第 4 层上。,1，99,3，47，58，64,1，39,1，27,1，11,2，43，78,1，18,1，35,第 1 层,第 2 层,第 3 层(L层),第 4 层(L1层),B树的查找算法,查找过程，类似于二叉排序树的查找。如查找关键字为 KEY 的记录。 从根r开始查找，如果 Ki = KEY 则查找成功，Ri 为关键字为 KEY 的记录的地址。

26、若 Ki Kn;在子树 An 中查找 若 找到叶子(r为NULL)，则查找失败。 注意：每次查找将去掉 （s-1）/s 个分支。,B树节点定义 #define m 3 typedef struct BTNode int keynum; struct BTNode *parent; KeyType key1+m; /* 0号未用 *. struct BTNode *ptr1+m; Record *recptr1+m; BTNode, *BTree;,B树的插入操作,步骤： 1、确定插入位置，将结点插入到第 L 层（注意：第 L+1 层为叶子结点） 2、找到插入位置，将关键字和其它信息按序插入。

27、3、若被插入结点的关键字个数 m-1, 则该结点满。必须分裂成两个结点。否则，结束。 如结点原为： （m-1, A0, (K1, A1), (K2, A2), (Km-1, Am-1)） 插入一个关键字之后变为： （m, A0, (K1, A1), (K2, A2), (Km, Am)） 该结点将进行分裂： . (K m/2, p ) . m/2 -1, A0, (K1, A1), (K m/2 , Am/2 )） （m- m/2 , A m/2 , (Km, Am)） 生成新结点 p, 将原结点的后半部分复制过去。若分裂一直进行到根结点，树可能长高一层。,P,P,(K m/2 , p) 数据

28、项插入上层结点之中,B树的插入操作,例如：3 阶 B 树的插入操作。m=3, m/2 - 1 = 1; 至少 1 个关键字，二个孩子结点。,B 树的删除操作,基本要求 删除一个关键字之后节点的关键字个数小于m/2-1，则设法合并,B+树,B+树是B树的变形，广泛应用在数据库系统中 一棵m阶B+树与一棵m阶B树的不同之处在于： 叶子结点包含了关键字的信息及指向记录的指针，且叶子结点以关键字自小至大顺序链接 非叶子节点仅仅作为索引部分使用，不含有关键字对应的指针 B+树已不是一棵真正意义上的树型结构了，其终端结点已连成了线性有序表 查找算法 每次查找都要从树根到树叶,键树,键树 又称数字查找树；

29、每个结点只包含组成关键字的字符或数字 常用存储方式 孩子兄弟的二叉树表示法（双键树）； 多重链表表示法（Trie 树）,哈希表,哈希表 一个有限的连续地址空间，用以容纳按哈希地址存储的记录。 哈希函数 记录的存储位置与它的关键字之间存在的一种对应关系。 Loc(ri)=H(keyi) 冲突 不同关键字经哈希函数运算后得到的散列地址相同 原因：将一个较大的关键字值域映射到小的线性地址空间 同义词 在同一地址出现冲突的各关键字。 装填因子 表中填入的记录数n和哈希表表长m之比,哈希函数的构造方法,设计哈希函数基本原则 针对具体问题仔细研究 简洁、高效 散列效果好 几种方法 除留余数法 H(key)

30、=key % m, m为散列表长度,m常用2n以提高计算效率 直接定址法：H(key)=a*key+b，a、b为常数； 数字分析法： 分析关键字，找出其中几位数字作散列地址（例如：指针值） 平方取中法 关键字平方后中间几位数字与所有数字相关，可选作散列地址 折叠法 将关键字分割成位数相同的几部分相叠加作为散列地址 伪随机数法 选取一个用关键字作为种子的伪随机数发生器生成散列地址,解决冲突的方法,开放定址法 Hi=( H(key)+di ) % m, i = 1,2, k (km)其中 H(key) 为散列函数 m 为散列表长 di 为增量序列，取值为： di=1,2,m-1，称为线性探测再散列

31、； di=12, -12,22, -22,k2 (km/2)，称为二次探测再散列； di= 伪随机数，称为伪随机探测再散列； 再散列法 Hi=RHi(key), i =1,2,k RHi为不同的散列函数；,解决冲突的方法,链地址法 散列表设立指针，将所有散列地址为此位置的关键字记录用链表形式存储起来 常使用双向链表便于关键字的增加和删除 查找效率：与表目个数N成正比,典型的链地址法链表结构 struct NODE ElemType key; struct NODE *next, *pprev; struct NODE *hashN; 为什么要这样实现？ 考虑元素的插入和删除算法，查找算法,链表

32、插入和删除,#define head hashidx 插入p p-next = head; if (head != NULL) head-pprev = ,链地址法,关键字序列(38、59、125、168、216、719、455、20) 哈希函数 H(key) = key %10,作业(1),数组aN中存储了N个整数并且递增有序，给出一种算法判断整数x是否在数组的元素集合中，并分析算法的执行效率。 写出非递归算法，在二叉排序树中检索关键字为k的节点。 书写一个递归算法，判断一个二叉树是否为二叉排序树。 如何从二叉排序树中删除关键字值为k的节点？阐述算法思想，并写出该算法。 平衡二叉树一定比二分

33、查找有更高的效率吗？分析平衡二叉树和折半查找两种算法各自的利弊。 写出一个算法将平衡二叉树节点p右子树树根左旋。 按照关键字序列43，33，12，29，22，18，10，57，48，35，62，40建立平衡二叉树，按步骤逐步画出平衡二叉树。,作业(2),一个整数集合的规模为60k，每个整数的取值是随机的，值范围为04G。对该集合的操作有：add(x):增加元素，del(x):删除元素，search(x):检索整数x是否在集合中。设计一种数据结构，使得检索操作平均检索时间比二分查找更快，而且增加/删除操作也有较高的效率。阐述数据的组织结构和算法基本思想，并且给出时间复杂度和空间复杂度分析结果。 重新设计一种数据结构完成第8题，并比较两种方法的优缺点。,