[理工] 資結 AVL Tree
題目 :
Construct an AVL tree by inserting 8,9,10,2,1,5,3,6,4,7,11,and 12
successively. You should note the balance factor of each node and show
all necessary rotation. 【95 中央資管(丙)】
我寫這題寫到平衡時有多個孤立點存在
如圖
https://i.imgur.com/9YQEBMi.png
我聽 洪毅上課 他只說一個孤立點的情形 就是照BST插入
那多個孤立點的時候
是要照 "小到大" 依序 BST 插入 還是照 "題目順序" BST插入?
謝謝~~
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.243.93.245
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1510106727.A.A6C.html
※ 編輯: jerry900287 (111.243.93.245), 11/08/2017 10:06:07
推
11/08 11:21,
8年前
, 1F
11/08 11:21, 1F
推
11/08 11:23,
8年前
, 2F
11/08 11:23, 2F
推
11/08 11:33,
8年前
, 3F
11/08 11:33, 3F
可是這也是多個孤立點的情況不是嗎QQ??
推
11/08 11:57,
8年前
, 4F
11/08 11:57, 4F
→
11/08 11:57,
8年前
, 5F
11/08 11:57, 5F
推
11/08 12:00,
8年前
, 6F
11/08 12:00, 6F
推
11/08 12:05,
8年前
, 7F
11/08 12:05, 7F
我想法是 照題目插入的話是 6 4 7 與 照小到大插入的話是 4 6 7 是不衝突沒錯
可是如果今天題目是 7 4 6 這種順序的話 BST 插入
答案就會不一樣惹
※ 編輯: jerry900287 (111.243.93.245), 11/08/2017 12:09:22
→
11/08 12:06,
8年前
, 8F
11/08 12:06, 8F
※ 編輯: jerry900287 (111.243.93.245), 11/08/2017 12:11:14
※ 編輯: jerry900287 (111.243.93.245), 11/08/2017 12:11:53
※ 編輯: jerry900287 (111.243.93.245), 11/08/2017 12:13:05
歐...我好像有點了解T大的講法了 這樣真的就沒衝突了
頂多只有兩個孤立集合 {4},{6-7} 他會分別插在 那個中間鍵值得左右邊
※ 編輯: jerry900287 (111.243.93.245), 11/08/2017 12:18:05
推
11/08 12:17,
8年前
, 9F
11/08 12:17, 9F
→
11/08 12:17,
8年前
, 10F
11/08 12:17, 10F
OKOK 太感謝你了
※ 編輯: jerry900287 (111.243.93.245), 11/08/2017 12:20:01
※ 編輯: jerry900287 (111.243.93.245), 11/08/2017 12:20:57
→
11/08 12:21,
8年前
, 11F
11/08 12:21, 11F
→
11/08 12:24,
8年前
, 12F
11/08 12:24, 12F
→
11/08 12:24,
8年前
, 13F
11/08 12:24, 13F
可以!!!
我覺得你講的是對的
※ 編輯: jerry900287 (111.243.93.245), 11/08/2017 12:28:29