同樣是"插入元素可能導(dǎo)致旋轉(zhuǎn)",為什么RB樹不是嚴(yán)格平衡,而AVL嚴(yán)格平衡?

zserewr

粗看RB樹的講解，這個(gè)樹在構(gòu)造/刪除的過程中，像AVL一樣可能會(huì)涉及旋轉(zhuǎn)。
那么
1. 為什么RB樹不是嚴(yán)格平衡的? 是因?yàn)樾�轉(zhuǎn)的方法不同嗎?
2. 旋轉(zhuǎn)方法不同，還是別的什么不同，導(dǎo)致了統(tǒng)計(jì)性能上RB樹更好呢?

謝謝。

lxyscls

紅黑樹的特點(diǎn)
1、所有的分支上的黑節(jié)點(diǎn)個(gè)數(shù)相同（黑高度）
2、紅節(jié)點(diǎn)的父節(jié)點(diǎn)不能為紅節(jié)點(diǎn)

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

AVL不知道了

yulihua49

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)慢。

windoze

因?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)存。