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

Chinaunix

標(biāo)題: 同樣是"插入元素可能導(dǎo)致旋轉(zhuǎn)",為什么RB樹(shù)不是嚴(yán)格平衡,而AVL嚴(yán)格平衡? [打印本頁(yè)]

作者: zserewr 時(shí)間: 2015-12-31 18:53
標(biāo)題: 同樣是"插入元素可能導(dǎo)致旋轉(zhuǎn)",為什么RB樹(shù)不是嚴(yán)格平衡,而AVL嚴(yán)格平衡?
粗看RB樹(shù)的講解，這個(gè)樹(shù)在構(gòu)造/刪除的過(guò)程中，像AVL一樣可能會(huì)涉及旋轉(zhuǎn)。
那么
1. 為什么RB樹(shù)不是嚴(yán)格平衡的? 是因?yàn)樾D(zhuǎn)的方法不同嗎?
2. 旋轉(zhuǎn)方法不同，還是別的什么不同，導(dǎo)致了統(tǒng)計(jì)性能上RB樹(shù)更好呢?

謝謝。

作者: lxyscls 時(shí)間: 2015-12-31 20:27
紅黑樹(shù)的特點(diǎn)
1、所有的分支上的黑節(jié)點(diǎn)個(gè)數(shù)相同（黑高度）
2、紅節(jié)點(diǎn)的父節(jié)點(diǎn)不能為紅節(jié)點(diǎn)

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

AVL不知道了

作者: yulihua49 時(shí)間: 2016-01-02 20:36

lxyscls 發(fā)表于 2015-12-31 20:27
紅黑樹(shù)的特點(diǎn)
1、所有的分支上的黑節(jié)點(diǎn)個(gè)數(shù)相同（黑高度）
2、紅節(jié)點(diǎn)的父節(jié)點(diǎn)不能為紅節(jié)點(diǎn)

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

作者: windoze 時(shí)間: 2016-01-03 14:21
因?yàn)檫@兩種樹(shù)的定義就是這樣子啊，rbtree只要求每條路徑上的黑節(jié)點(diǎn)個(gè)數(shù)相同，而且不能有兩個(gè)連著的紅結(jié)點(diǎn)，所以最長(zhǎng)路徑有可能達(dá)到最短路徑的兩倍長(zhǎng)，AVL的定義就要求是一個(gè)嚴(yán)格的平衡樹(shù)。
rbtree不用每次插入都做調(diào)整，而是攢夠一批一次調(diào)整到位，所以對(duì)于頻繁插入刪除的情況下rbtree會(huì)稍快一點(diǎn)。單說(shuō)查找性能rbtree肯定不會(huì)比avl更好。
統(tǒng)計(jì)意義上rbtree性能更好是因?yàn)榻^大多數(shù)要用二叉樹(shù)的場(chǎng)合插入和刪除操作都比較多，要是沒(méi)有太多插入刪除就不用二叉樹(shù)了，直接用個(gè)排序數(shù)組查找性能秒殺所有二叉樹(shù)，雖說(shuō)復(fù)雜度是一樣的，但數(shù)組顯然比二叉樹(shù)更c(diǎn)ache friendly，而且省內(nèi)存。

歡迎光臨 Chinaunix (http://www.72891.cn/)