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

zserewr

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

謝謝。

lxyscls

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

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

AVL不知道了

yulihua49

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

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

windoze

因為這兩種樹的定義就是這樣子啊，rbtree只要求每條路徑上的黑節(jié)點個數(shù)相同，而且不能有兩個連著的紅結(jié)點，所以最長路徑有可能達到最短路徑的兩倍長，AVL的定義就要求是一個嚴格的平衡樹。
rbtree不用每次插入都做調(diào)整，而是攢夠一批一次調(diào)整到位，所以對于頻繁插入刪除的情況下rbtree會稍快一點。單說查找性能rbtree肯定不會比avl更好。
統(tǒng)計意義上rbtree性能更好是因為絕大多數(shù)要用二叉樹的場合插入和刪除操作都比較多，要是沒有太多插入刪除就不用二叉樹了，直接用個排序數(shù)組查找性能秒殺所有二叉樹，雖說復(fù)雜度是一樣的，但數(shù)組顯然比二叉樹更cache friendly，而且省內(nèi)存。