亚洲av成人无遮挡网站在线观看,少妇性bbb搡bbb爽爽爽,亚洲av日韩精品久久久久久,兔费看少妇性l交大片免费,无码少妇一区二区三区

  免費(fèi)注冊(cè) 查看新帖 |

Chinaunix

  平臺(tái) 論壇 博客 文庫
最近訪問板塊 發(fā)新帖
查看: 4708 | 回復(fù): 3
打印 上一主題 下一主題

[算法] 同樣是"插入元素可能導(dǎo)致旋轉(zhuǎn)",為什么RB樹不是嚴(yán)格平衡,而AVL嚴(yán)格平衡? [復(fù)制鏈接]

論壇徽章:
0
跳轉(zhuǎn)到指定樓層
1 [收藏(0)] [報(bào)告]
發(fā)表于 2015-12-31 18:53 |只看該作者 |倒序?yàn)g覽
粗看RB樹的講解,這個(gè)樹在構(gòu)造/刪除的過程中,像AVL一樣可能會(huì)涉及旋轉(zhuǎn)。
那么
1. 為什么RB樹不是嚴(yán)格平衡的? 是因?yàn)樾D(zhuǎn)的方法不同嗎?
2. 旋轉(zhuǎn)方法不同,還是別的什么不同,導(dǎo)致了統(tǒng)計(jì)性能上RB樹更好呢?

謝謝。

論壇徽章:
14
水瓶座
日期:2014-06-10 09:51:0215-16賽季CBA聯(lián)賽之江蘇
日期:2017-11-27 11:42:3515-16賽季CBA聯(lián)賽之八一
日期:2017-04-12 14:26:2815-16賽季CBA聯(lián)賽之吉林
日期:2016-08-20 10:43:1215-16賽季CBA聯(lián)賽之廣夏
日期:2016-06-23 09:53:58程序設(shè)計(jì)版塊每日發(fā)帖之星
日期:2016-02-11 06:20:00程序設(shè)計(jì)版塊每日發(fā)帖之星
日期:2016-02-09 06:20:0015-16賽季CBA聯(lián)賽之上海
日期:2015-12-25 16:40:3515-16賽季CBA聯(lián)賽之廣夏
日期:2015-12-22 09:39:36程序設(shè)計(jì)版塊每日發(fā)帖之星
日期:2015-08-24 06:20:002015亞冠之德黑蘭石油
日期:2015-08-07 09:57:302015年辭舊歲徽章
日期:2015-03-03 16:54:15
2 [報(bào)告]
發(fā)表于 2015-12-31 20:27 |只看該作者
紅黑樹的特點(diǎn)
1、所有的分支上的黑節(jié)點(diǎn)個(gè)數(shù)相同(黑高度)
2、紅節(jié)點(diǎn)的父節(jié)點(diǎn)不能為紅節(jié)點(diǎn)

也就是說:最長(zhǎng)的分支,是最短分支長(zhǎng)度的兩倍,只能是近似平衡

AVL不知道了

論壇徽章:
15
射手座
日期:2014-11-29 19:22:4915-16賽季CBA聯(lián)賽之青島
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16賽季CBA聯(lián)賽之四川
日期:2017-02-07 21:08:572015年亞冠紀(jì)念徽章
日期:2015-11-06 12:31:58每日論壇發(fā)貼之星
日期:2015-08-04 06:20:00程序設(shè)計(jì)版塊每日發(fā)帖之星
日期:2015-08-04 06:20:00程序設(shè)計(jì)版塊每日發(fā)帖之星
日期:2015-07-12 22:20:002015亞冠之浦和紅鉆
日期:2015-07-08 10:10:132015亞冠之大阪鋼巴
日期:2015-06-29 11:21:122015亞冠之廣州恒大
日期:2015-05-22 21:55:412015年亞洲杯之伊朗
日期:2015-04-10 16:28:25
3 [報(bào)告]
發(fā)表于 2016-01-02 20:36 |只看該作者
lxyscls 發(fā)表于 2015-12-31 20:27
紅黑樹的特點(diǎn)
1、所有的分支上的黑節(jié)點(diǎn)個(gè)數(shù)相同(黑高度)
2、紅節(jié)點(diǎn)的父節(jié)點(diǎn)不能為紅節(jié)點(diǎn)

AVL 就是完全平衡。查找速度比rb快。構(gòu)建和析構(gòu)慢。

論壇徽章:
44
15-16賽季CBA聯(lián)賽之浙江
日期:2021-10-11 02:03:59程序設(shè)計(jì)版塊每日發(fā)帖之星
日期:2016-07-02 06:20:0015-16賽季CBA聯(lián)賽之新疆
日期:2016-04-25 10:55:452016科比退役紀(jì)念章
日期:2016-04-23 00:51:2315-16賽季CBA聯(lián)賽之山東
日期:2016-04-17 12:00:2815-16賽季CBA聯(lián)賽之福建
日期:2016-04-12 15:21:2915-16賽季CBA聯(lián)賽之遼寧
日期:2016-03-24 21:38:2715-16賽季CBA聯(lián)賽之福建
日期:2016-03-18 12:13:4015-16賽季CBA聯(lián)賽之佛山
日期:2016-02-05 00:55:2015-16賽季CBA聯(lián)賽之佛山
日期:2016-02-04 21:11:3615-16賽季CBA聯(lián)賽之天津
日期:2016-11-02 00:33:1215-16賽季CBA聯(lián)賽之浙江
日期:2017-01-13 01:31:49
4 [報(bào)告]
發(fā)表于 2016-01-03 14:21 |只看該作者
因?yàn)檫@兩種樹的定義就是這樣子啊,rbtree只要求每條路徑上的黑節(jié)點(diǎn)個(gè)數(shù)相同,而且不能有兩個(gè)連著的紅結(jié)點(diǎn),所以最長(zhǎng)路徑有可能達(dá)到最短路徑的兩倍長(zhǎng),AVL的定義就要求是一個(gè)嚴(yán)格的平衡樹。
rbtree不用每次插入都做調(diào)整,而是攢夠一批一次調(diào)整到位,所以對(duì)于頻繁插入刪除的情況下rbtree會(huì)稍快一點(diǎn)。單說查找性能rbtree肯定不會(huì)比avl更好。
統(tǒng)計(jì)意義上rbtree性能更好是因?yàn)榻^大多數(shù)要用二叉樹的場(chǎng)合插入和刪除操作都比較多,要是沒有太多插入刪除就不用二叉樹了,直接用個(gè)排序數(shù)組查找性能秒殺所有二叉樹,雖說復(fù)雜度是一樣的,但數(shù)組顯然比二叉樹更c(diǎn)ache friendly,而且省內(nèi)存。

評(píng)分

參與人數(shù) 1信譽(yù)積分 +10 收起 理由
lxyscls + 10 很給力!

查看全部評(píng)分

您需要登錄后才可以回帖 登錄 | 注冊(cè)

本版積分規(guī)則 發(fā)表回復(fù)

  

北京盛拓優(yōu)訊信息技術(shù)有限公司. 版權(quán)所有 京ICP備16024965號(hào)-6 北京市公安局海淀分局網(wǎng)監(jiān)中心備案編號(hào):11010802020122 niuxiaotong@pcpop.com 17352615567
未成年舉報(bào)專區(qū)
中國(guó)互聯(lián)網(wǎng)協(xié)會(huì)會(huì)員  聯(lián)系我們:huangweiwei@itpub.net
感謝所有關(guān)心和支持過ChinaUnix的朋友們 轉(zhuǎn)載本站內(nèi)容請(qǐng)注明原作者名及出處

清除 Cookies - ChinaUnix - Archiver - WAP - TOP