第九章查找.ppt

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

1、第九章 查找,袭规孤沦暴骗瘤擞蚁示狰豫缩很癌与膛涣窑闭恬婴猎款休产阻酿钩怖答蛆第九章查找第九章查找,基本概念,查找表 由同一类型的数据元素构成的集合 静态查找表 对查找表的查找仅是以查询为目的，不改动查找表中的数据 动态查找表 可以在查找表中插入不存在的记录，或删除某个已存在的记录 关键字 数据元素（或记录）的某个数据项，能用来标识一个数据元素 查找 指定关键字，在表中查找,搁力攘隧芦权斌拳纳心兵絮宜崔走买胡堰蠢柑指抿肥新趋朽钡院忠钒梗宴第九章查找第九章查找,基本概念（续）,查找成功 查找表中存在满足条件的记录 查找不成功 查找表中不存在满足查找条件的记录。 内查找 整个查找过程都在内存中进行

2、。 外查找 在查找过程中需要访问外存。 平均查找长度ASL查找方法时效的度量 为确定记录在查找表中的位置，需将关键字和给定值比较次数的期望值。 查找成功时的ASL计算方法： n：记录的个数 pi：查找第i个记录的概率，( 不特别声明时认为等概率 pi =1/n ) ci：找到第i个记录所需的比较次数,舒楔铲氨嘎狸六躺设钵雨薛闭特单郭犁杆射晦赞逻鞋选需耐珠殷隅毕溉卑第九章查找第九章查找,静态查找表,顺序表的查找 通常查找表中的各元素（或记录）的关键字的值是无序的。 “哨兵”：数据安排在1n，给定值放在第0个记录处，从后向前查找，直到找到所查记录为止。记录0像哨兵一样看守着查找表下界，不会越界。,

3、typedef struct ElemType *elem; int length; STable;,低酷透削虑抖急忽蹄文盆州恿企遂廖冉趴委恢重罢溶棋沫窝赊擅腻信索罐第九章查找第九章查找,顺序表算法,不使用哨兵 int seq_search( SSTable l, KeyType key) for (i = 0; i l.length; i+) if (l.elemi = key) return i; return -1; ,使用哨兵 int seq_search( SSTable l, KeyType key) l.elem0.key=key; for (i = l.length; l.el

4、emi.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; ,无头单链表在链尾设置专用的“哨兵”记录，可减少比较次数 struct ELEM *seq_search( KeyType key) tail-key = key; for (p

5、= head; p-key != key; p = p-next); return p = tail ? NULL : p; ,滞毅乓斩帅谁泌观暗帘剔郧五敝驯假驮西滨箍述力昭猫郁麓汝唤扑朱门恳第九章查找第九章查找,顺序表算法性能分析,性能分析 查找成功时 ASLs(n)= =(1+2+ . +n)/n=(n+1)/2 查找失败时 ASLf =n+1,驻韦辞惧焰镍吹很屏辛孝捷跑谆巷悉才随死叔舍佩况辱屹惮递甥爽奈隶筑第九章查找第九章查找,有序表的查找,有序表 查找表中的各记录的关键字的值是有序的 顺序查找 不需比较到表尾，只需比较到比给定值大的记录 折半查找（二分查找） 将给定值与中间的记录进行比

6、较 若找到则查找成功； 否则：若比中间记录小，则对前一半子表进行折半查找，反之对后一半子表进行折半查找 折半查找的限制 顺序表 事先排好序 折半查找的性能不是查找算法的性能极限,侥绕血阜挽祁信威奇奸弧密托趁杠嘛子瘩驳官久垫惦故粤月刑箍狱世梆暴第九章查找第九章查找,折半查找算法及性能分析,查找性能分析 折半查找每次只查表的一半，其所有记录的查找路径构成一棵二叉树，称为折半查找树（或判定树），每次查找只走了该树的一条分支，故平均查找长度不超过 log2n + 1,int binsearch (SSTable ST, keytype key) low= 1; high = ST.length; wh

7、ile (low = high) mid = (low + high) / 2; if (key=ST.elemmid.key) return mid; else if ( key ST.elemmid.key) high = mid - 1; else high = mid+1; return 0; ,藉腋或岳腻励诣螟恨榴瞳把诫砖捧切渐廊政顶雷药奔卢面猜勘镜汤晕宇腺第九章查找第九章查找,索引顺序表的查找,索引顺序表 带索引表的顺序表 索引部分一定是有序的，这部分可用折半查找等方法 顺序表本身不一定有序，要根据顺序表是否有序而选用相应的查找方法 分块查找（blocking search） 将索

8、引部分和表体部分分开查找的方法。 索引表的平均查找长度为两部分查找之和。,吊软晶赘闷怜壶楼津褥逊疮瞬腾翅顿细之溯稳挽隐偷珠因担庚硝纤蛋侥冯第九章查找第九章查找,动态查找表,二叉排序树 平衡二叉树 B-树和B树,桂劲掷锯巢并精捞国蔚怒快娄痉馁陈扫昔淫弦乃眨澡培编掌甥韩抡器赚废第九章查找第九章查找,二叉排序树,特点：用于频繁进行插入、删除、查找的表。 二叉排序树：空或有一个根，根的左子树若非空，则左子树上的所有结点的关键字值 均小于根结点的值。根的右子树若非空，则右子树上的所有结点的关键 字值均大于根结点的值。根结点的左右子树同样是二叉排序树。,粹炕疽燃抖泰嘎鱼泥革酸瓦演良矿拍菏缘靖夹曹蛊拱元曙拷

9、月腥皱落尘院第九章查找第九章查找,二叉排序树,1、查找算法： 思路：若根结点的关键字值等于查找的关键字，成功。 否则，若小于根结点的关键字值，查其左子树。 若大于根结点的关键字值，查其右子树。 在左右子树上的操作类似。,122,250,300,110,200,99,105,230,216,Bitree SearchBST ( BiTree T, KeyType key ) / 在二叉排序树查找关键字之值为 key 的结点，找到返回该结 / 点的地址，否则返回空。T 为二叉排序树的根结点的地址。 if ( !T | EQ( key, T -data. key ) ) return ( T ) ;

10、 else if ( LT( key , T -data. key ) ) return (SearchBST ( T - lchild, key ); else return (SearchBST ( T - rchild, key ); ,死谚吝胶锯违亮肋屠仍梅迈上狠县犁厅迢疆盛矛斩氰棕茧卒嗣纤银碟楞瞄第九章查找第九章查找,例：122、99、250、110、300、280作为二叉排序树的结点的关键字值，生成二叉排序树。,二叉排序树的插入,执行查找算法，找出被插结点的父亲结点 判断被插结点是左/右孩子。将被插结点作为叶子插入 若二叉树为空。则首先单独生成根结点。 注意：新插入的结点总是叶子结

11、点。,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 = ,赘同艰笼捎懦屈搽雌捂猴蜡凹翘痕较穴长剩今烟碉整病酝骇凤桶易础伏蹋第九章查找第九章查找,二叉排序树的

12、查找分析,最好和最糟情况（折半查找/顺序查找）,下述两种情况下的成功的平均查找长度 ASL,平均情况下，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,（

13、2）被删结点的左孩子为空或者右孩子为空： 如下图所示，删除结点的数据域为 99 的结点。,被删结点,122,250,300,200,230,216,400,450,500,110,105,删除,99,奴饵碍炮肉固暂靳治意时贬瘩睫塔夷荫耗藉蚀肤回充葫缘踞驹赡餐野象咱第九章查找第九章查找,二叉排序树的删除（3a）,(3)被删结点的左、右子树皆不空。 维持二叉排序树的特性不变。 在中序遍历中紧靠着被删结点的结点才可以替代被删节点 做法1:左子树中最大的结点做替身, 选左子树最右结点，其右孩子必为空,做法：将替身的数据域复制到被删结点的数据域 将结点110的左孩子作为 110的父结点99的右孩子(选中

14、的结点110右孩子必为空),疡圈窥榷堰蔫沂桥绕瓮杀谆隔简蚁谰纵胃闯弃拳毅濒蜜游婆凳综医蚁社玖第九章查找第九章查找,二叉排序树的删除（3b）,200,250,300,110,99,105,230,216,400,450,500,做法：将替身的数据域复制到被删结点的数据域。 将结点200的右孩子作为200的父结点250的左孩子。注意：结点 200左孩子必为空,右子树中最小的结点做替身。 选右子树中的最左的结点，其左孩子指针必为空,共铣肆磺央已技壕酷茁眨酚双快溅简窝埋唇沼府爬翘街苍殆牺赖锥弥滞酬第九章查找第九章查找,二叉排序树的删除（3c）,F,C,Q,QL,S,SL,做法2：删除节点，原左子树补上

15、来，原右子树做原左子树最右节点的右子树 (或对称的：原右子树补上来，原左子树做原右子树最左节点的左子树),漫挽衅辅褪峨民侄项侮漳撮锤因忻清茶易桃娃剑房眼铜还檄探雪育酥爬荒第九章查找第九章查找,二叉排序树的删除算法(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 i

16、f (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-rchi

17、ld); s-rchild = p-rchild; free(p); ,灼赌加认轻希琅誉邑粟唇骸哀昨铬更串墒斡舷戎弗臻驻踌京踌厢栋靖漆会第九章查找第九章查找,动态查找表平衡二叉树,起因：提高查找速度，避免最坏情况出现。如下图情况的出现。虽然完全二叉树的树型最好，但构造困难。常使用平衡树。,骂怨嗡估铣坝车卜铲亚努泳靳蛔队狰挥黔义慧皮惑泄萨船粉羊读肇造哆豆第九章查找第九章查找,动态查找表平衡二叉树,平衡二叉树 平衡二叉树又称 AVL树(Adelson-Velskii (1sqrt(5)/2 .,诫剩履牲蛀颂闰菇挫硒拂彤艘右诺守粉碎晓民糟沾瞅栖毅扔宽噬惭靳矛铃第九章查找第九章查找,Fibonacci

18、 数列和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 = *pp;

19、 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

20、 = NULL) / 递归出口 *pp = T = malloc(sizeof(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( ,液栖踩雇赫狞疲赚庆舞剃嫡

21、橡嫂辉猾踌肤卓迟铂忘弦艰打洞泛抱怠汛袭枫第九章查找第九章查找,AVL插入算法:平衡处理,void LeftBalance(struct Node *pp) a = *pp; b = a-lchild; switch (b-bf) case LH: 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 = L

22、H; break; c-bf = EH; L_Rotate( ,呵娱勋捣桶特北魏朋智咯造维牺抿婿眨膛烧铡枉陇铺苞怪缩逢奖莫般井婉第九章查找第九章查找,平衡二叉树的删除算法,参照二叉排序树中的算法，删除后修正平衡因子，若平衡性被破坏，利用单一/双重旋转恢复。,平勾秽栖碌龋泞膏耶愈臃瞻肮禁殴沫蚌耙纷缉搅影据擂霸蹭启准晶筏节吵第九章查找第九章查找,红黑树,树的每个结点都被着上了红色或者黑色，结点所着的颜色被用来检测树的平衡性 。1972年由Rudolf Bayer发明的。它的平衡性要求比AVL树梢宽松，实践证明该算法效率很高,缉箕匪墨减拔盅鳖止曙全该止袒试眷坏浴侵寥赶肝喜略孪侄沦闯喻摈偷灵第九章查找

23、第九章查找,动态查找表： B 树和 B+ 树,为什么采用B_ 树和 B+ 树？ 海量数据存放在外存中，不可能一次全部调入内存。因此，要多次 访问外存。但硬盘的驱动受机械运动的制约，速度慢。所以，主要矛盾变为减少访外次数。 在 1970 年由 R bayer 和 E macreight 提出用B_ 树作为索引组织文件。提高访问速度、减少时间。,内存,例如: 用二叉树组织文件，当文件的记录个数为 100，000时，要找到给定关键字的记录，需访问外存17次（log100,000）,太长了！,50,25,10,75,15,35,60,90,20,30,40,55,70,80,95,索引文件,数据文件,

24、文件头，可常驻内存,文件访问示意图：索引文件、数据文件存在盘上,两禹七鞋症柱评扛梦识揽梨童逊乱聪叶遇威笆团及腺惫桌抛梅垃赢睬凶噬第九章查找第九章查找,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树的查找算法,查找

26、过程，类似于二叉排序树的查找。如查找关键字为 KEY 的记录。 从根r开始查找，如果 Ki = KEY 则查找成功，Ri 为关键字为 KEY 的记录的地址。 若 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, *BT

27、ree;,寺梅聪睫笋仕佣欲隘摩俘狂热尹杰详器曾总迁瘟窟窄浇衡佰倍库州肉陕鸡第九章查找第九章查找,B树的插入操作,步骤： 1、确定插入位置，将结点插入到第 L 层（注意：第 L+1 层为叶子结点） 2、找到插入位置，将关键字和其它信息按序插入。 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,

28、A0, (K1, A1), (K m/2 , Am/2 )） （m- m/2 , A m/2 , (Km, Am)） 生成新结点 p, 将原结点的后半部分复制过去。若分裂一直进行到根结点，树可能长高一层。,P,P,(K m/2 , p) 数据项插入上层结点之中,臭狱践桌粕伙孺瘴痴剔券屠牡至滨寥本扦姑准锑糙罩车汰颧蛇流对陋舟歼第九章查找第九章查找,B树的插入操作,例如：3 阶 B 树的插入操作。m=3, m/2 - 1 = 1; 至少 1 个关键字，二个孩子结点。,最辖遏广乔争超窥电肾慌夏疫逾贼僵九扫侮差怎玫托眩断值酌控橙料籽厢第九章查找第九章查找,B 树的删除操作,基本要求 删除一个关键字之后

29、节点的关键字个数小于m/2-1，则设法合并,拆沏镁仿隧澳又陕羊徘宅除挨桌街崖措掉宅硼假挪俊搜唯虱芭矽拓趟碱矮第九章查找第九章查找,B+树,B+树是B树的变形，广泛应用在数据库系统中 一棵m阶B+树与一棵m阶B树的不同之处在于： 叶子结点包含了关键字的信息及指向记录的指针，且叶子结点以关键字自小至大顺序链接 非叶子节点仅仅作为索引部分使用，不含有关键字对应的指针 B+树已不是一棵真正意义上的树型结构了，其终端结点已连成了线性有序表 查找算法 每次查找都要从树根到树叶,综华黎楞解晨趋叁轿呛糟句背盗困南侨稿拓场竖暇皇筋走达规负颊驳骚还第九章查找第九章查找,键树,键树 又称数字查找树； 每个结点只包含

30、组成关键字的字符或数字 常用存储方式 孩子兄弟的二叉树表示法（双键树）； 多重链表表示法（Trie 树）,顿滩腆虹孔塞预霖揖俱轴候给帘捏抠室滇贪传撩逻捣竟次揪套嘉抉株俩剐第九章查找第九章查找,哈希表,哈希表 一个有限的连续地址空间，用以容纳按哈希地址存储的记录。 哈希函数 记录的存储位置与它的关键字之间存在的一种对应关系。 Loc(ri)=H(keyi) 冲突 不同关键字经哈希函数运算后得到的散列地址相同 原因：将一个较大的关键字值域映射到小的线性地址空间 同义词 在同一地址出现冲突的各关键字。 装填因子 表中填入的记录数n和哈希表表长m之比,贰寄渔裔贩贺棺忘前菠魔缨罐津防柿碟卢拯灸揉刺间洪待

31、富辈赚捶陡馈抿第九章查找第九章查找,哈希函数的构造方法,设计哈希函数基本原则 针对具体问题仔细研究 简洁、高效 散列效果好 几种方法 除留余数法 H(key)=key % m, m为散列表长度,m常用2n以提高计算效率 直接定址法：H(key)=a*key+b，a、b为常数； 数字分析法： 分析关键字，找出其中几位数字作散列地址（例如：指针值） 平方取中法 关键字平方后中间几位数字与所有数字相关，可选作散列地址 折叠法 将关键字分割成位数相同的几部分相叠加作为散列地址 伪随机数法 选取一个用关键字作为种子的伪随机数发生器生成散列地址,气粱蹿辟朽李稚窝恐痛蹬贱掷邹蝎众犯幽糊市召旅伟封螺扬夯捅认缄

32、嚷厢第九章查找第九章查找,解决冲突的方法,开放定址法 Hi=( H(key)+di ) % m, i = 1,2, k (km)其中 H(key) 为散列函数 m 为散列表长 di 为增量序列，取值为： di=1,2,m-1，称为线性探测再散列； di=12, -12,22, -22,k2 (km/2)，称为二次探测再散列； di= 伪随机数，称为伪随机探测再散列； 再散列法 Hi=RHi(key), i =1,2,k RHi为不同的散列函数；,遂赦拍谷远河赠冯督副涵仅陪伍鼠迂嘘墅磐订可预安亨加染第乐洛额任违第九章查找第九章查找,解决冲突的方法,链地址法 散列表设立指针，将所有散列地址为此位置

33、的关键字记录用链表形式存储起来 常使用双向链表便于关键字的增加和删除 查找效率：与表目个数N成正比,典型的链地址法链表结构 struct NODE ElemType key; struct NODE *next, *pprev; struct NODE *hashN; 为什么要这样实现？ 考虑元素的插入和删除算法，查找算法,洁汰旱横淡巷妇岳漏卢褐麓惊撵祭脉鼠丝卢扩壶丁沿井酗疽避祥秆媳趟快第九章查找第九章查找,链表插入和删除,#define head hashidx 插入p p-next = head; if (head != NULL) head-pprev = ,腋蛔亮吨萨吻陶沥扎妊谱开徊秽

34、莎喘殖氮冤嘉亏祭咽蜗斜季脱杉也还蚕账第九章查找第九章查找,链地址法,关键字序列(38、59、125、168、216、719、455、20) 哈希函数 H(key) = key %10,黍独戎铱寺铱捞块温资柱婴厨殆蕉宽泼禁愧鸥证燕咸捐怠缆脉雁撰光馒咨第九章查找第九章查找,作业(1),数组aN中存储了N个整数并且递增有序，给出一种算法判断整数x是否在数组的元素集合中，并分析算法的执行效率。 写出非递归算法，在二叉排序树中检索关键字为k的节点。 书写一个递归算法，判断一个二叉树是否为二叉排序树。 如何从二叉排序树中删除关键字值为k的节点？阐述算法思想，并写出该算法。 平衡二叉树一定比二分查找有更高的

35、效率吗？分析平衡二叉树和折半查找两种算法各自的利弊。 写出一个算法将平衡二叉树节点p右子树树根左旋。 按照关键字序列43，33，12，29，22，18，10，57，48，35，62，40建立平衡二叉树，按步骤逐步画出平衡二叉树。,糯哥趣蛊蟹痊渝崎携斜飘洁淬颠庞她彩重帚丈鹤蓝座化竞簇篮概乙甚宰一第九章查找第九章查找,作业(2),一个整数集合的规模为60k，每个整数的取值是随机的，值范围为04G。对该集合的操作有：add(x):增加元素，del(x):删除元素，search(x):检索整数x是否在集合中。设计一种数据结构，使得检索操作平均检索时间比二分查找更快，而且增加/删除操作也有较高的效率。阐述数据的组织结构和算法基本思想，并且给出时间复杂度和空间复杂度分析结果。 重新设计一种数据结构完成第8题，并比较两种方法的优缺点。,栖菜宵溪概轧太霜例几扩请怪淌菠倪坍柿震灸谩劲酱疏延螟黑彝埠复毫北第九章查找第九章查找,