算法设计与分析6课件.ppt

上传人(卖家):三亚风情 文档编号:3033686 上传时间:2022-06-24 格式:PPT 页数:40 大小:1.66MB
下载 相关 举报
算法设计与分析6课件.ppt_第1页
第1页 / 共40页
算法设计与分析6课件.ppt_第2页
第2页 / 共40页
算法设计与分析6课件.ppt_第3页
第3页 / 共40页
算法设计与分析6课件.ppt_第4页
第4页 / 共40页
算法设计与分析6课件.ppt_第5页
第5页 / 共40页
点击查看更多>>
资源描述

1、求解求解问题问题更简单方便更简单方便另一种表现另一种表现另一个问题另一个问题( )( )( )( log )( )( log )sortscanT nTnTnO nnO nO nn 21( )(1.).(11nknT nkn ( )( )( )( log( lo)l g)o)g(sortscanT nTnTnO nnnnOOn10520427812101101 00AVL树树10520427820011 00非非AVL树,树,BST102R(3)32132100012301 2 L(1)321000321L(1)312201 321000R(3)12 2031R(3)12 3021 32100

2、0L(1)R(w)21eT1T2T311ewT3T2T100wkT4T3T1eT2121 1 L(e)wkT4T3T1eT21220orwkT4T3T1eT21220wkT4T3T1eT201 0R(w)它是它是BST,效率与,效率与BST一样取决于树高:一样取决于树高: 频繁的旋转、维护树节点平衡,设计上较复杂,尤其是频繁的旋转、维护树节点平衡,设计上较复杂,尤其是 删除操作,妨碍了其应用。但蕴涵的思想使人们发现了删除操作,妨碍了其应用。但蕴涵的思想使人们发现了 BST 的其他变种。的其他变种。22log1.4405log (2)1.3277nnhKK K K1 , K2K1 K2 K1,

3、K2,95, ,99589,5分裂,提升分裂,提升892,3,5,89253,892,53,8924, ,83524793, ,89247,892,59,58,8951k=23456789 1011 12( )/22( )22( )21 21( )1 3( )11Parent kkknLChild kkknRChild kkknLSibling kkknRSibling kkkn k奇数奇数k偶数偶数1075421107541105411. 树高树高 2. H0 为空,或放置最大限位器为空,或放置最大限位器3. 父母优势(兄弟节点没有关系)父母优势(兄弟节点没有关系)2log n22 ,/ 2

4、max1kkkHHHkn 左左子子女女右右子子女女1075421 构造一棵满足父母优势的完全二叉树构造一棵满足父母优势的完全二叉树2956898567298567285679285679685271. 21()/ 21, ()()2()(1 )1(), fordowntodowhile notaHnvkjnnddoififHeapValueExchangeinkiH kheapFALSEheapnjkH jjvH jH kHHjjheaipfelsTRUEHkkjjve 注释:父节点下推过程中注释:父节点下推过程中值不变值不变。把它理解。把它理解为空节点,与较大子节点交换键值,直到空为空节点,

5、与较大子节点交换键值,直到空节点到达它的最后位置,再把抹去的值还给节点到达它的最后位置,再把抹去的值还给它。它。110110( )2()2222222hhkkkkhhkkT nhkhkh 2hhh 12222(2)2(log (1),21log (1)102hnnnnnn 112(1)22niniin 9685279652786952785 652652612297568完全二叉树的数组完全二叉树的数组 Hk= 2,9,7,6,5,8 内部节点内部节点叶节点叶节点结果数组为升序结果数组为升序待解问题待解问题已知求解算法已知求解算法A(,),(,),(,)iijjkki xyj xyk xy1101iiijkjjkkxyAxyxy kijxy(, )(, )mnlcm m ngcd m n max( )min( )f xf xx( )f x*x( *)f x( *)f x 11011nkkknkkkkxf xv xw xWkn max( ), ,.,11110nkknkkkkkxf xWvxkxwn ( ),.m x.,a

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 办公、行业 > 各类PPT课件(模板)
版权提示 | 免责声明

1,本文(算法设计与分析6课件.ppt)为本站会员(三亚风情)主动上传,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。
2,用户下载本文档,所消耗的文币(积分)将全额增加到上传者的账号。
3, 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(发送邮件至3464097650@qq.com或直接QQ联系客服),我们立即给予删除!


侵权处理QQ:3464097650--上传资料QQ:3464097650

【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。


163文库-Www.163Wenku.Com |网站地图|