Re: [理工] [algo] AVL Tree的insert
看板Grad-ProbAsk作者KarmaPolice (Karma Police)時間16年前 (2010/03/20 19:47)推噓1(1推 0噓 2→)留言3則, 1人參與討論串2/2 (看更多)
※ 引述《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
推
03/20 20:50, , 1F
03/20 20:50, 1F
→
03/20 20:51, , 2F
03/20 20:51, 2F
→
03/20 20:56, , 3F
03/20 20:56, 3F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：