第九章查找.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:表示新插入结点在危机结点的左子树的右子
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第九 查找
链接地址:https://www.31doc.com/p-2558167.html