作者KarmaPolice (Karma Police)
站內Grad-ProbAsk
標題Re: [理工] [algo] AVL Tree的insert
時間Sat Mar 20 19:47:44 2010
※ 引述《fish0112 (魚)》之銘言：
: 99交大資結演算
: 第5題組
: 12.What's the pre-order sequence after inserting"2,1,4,5" into an initially
: empty AVL tree?
: 答案是2,1,4,5
: 13.What's the pre-order sequence after inserting"9,3,6,7" into the above
: AVL tree?
: 答案是 4,2,1,3,6,5,9,7
: 向版上的高手請教這兩題的詳解，感謝m(__.__)m
12.
insert 2 insert 1 insert 4 insert 5
2 2 2 2
/ / \ / \
1 1 4 1 4
\
5
13.
insert 9 RR Rotate insert 3 RL Rotate
2 2 2 4
/ \ / \ / \R / \
1 4 1 5 1 5 => 2 5
\R => / \ L/ \ / \ \
5 4 9 4 9 1 3 9
\R /
9 3
(注意要從下面的優先) (這裡3很容易放錯)
insert 6 RL Rotate insert 7
4 4 4
/ \ / \ / \
2 5 => 2 6 2 6
/ \ \R /\ /\ /\ /\
1 3 9 1 3 5 9 1 3 5 9 done.
/L /
6 7
Preorder: 42136597
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.204.2.14
1F：推 fish0112:感謝 問一下 insert9 459作RR之後，怎麼得到3加在4左下？ 03/20 20:50
2F：→ fish0112:就是...AVL的insert位置到底怎麼定的呢(．＿．?) 03/20 20:51
3F：→ fish0112:知道了，不用回啦:P 感謝原po 03/20 20:56