moea_joint_essay 113年 [資訊] 資訊管理、程式設計

第二題

📖 題組：
四、請依下列條件畫出樹狀圖：（2 題，每題 6 分，共 12 分）

📝 此題為申論題，共 2 小題

小題 (二)

在 1 個空的 AVL 樹，依序插入 53、68、72、5、47、14、36、21，畫出完成後的 AVL樹。

依照插入順序，每插入一個節點就檢查高度平衡因子 (Balance Factor)。如果絕對值超過 1，判斷是不平衡的類型 (LL, LR, RL, RR) 並作相對應的旋轉。

🤖

AI 詳解

AI 專屬家教

插入過程與旋轉演變：

插入 53, 68, 72：樹偏右發生 RR 不平衡，以 68 為中心左旋。得到根節點 68，左 53，右 72。
插入 5, 47：加在 53 左側成為 5 的右子點。導致節點 53 發生 LR 不平衡。對 5 左旋、對 53 右旋。結果 47 成為 68 左子點，47 左 5，右 53。

依據前序(prefix)表示法 JBHCDIGAEF 及中序(infix)表示法 CHBIDJEAGF，畫出唯一的二元樹。

前序的第一個元素是根節點，利用此節點在中序中的位置，可以將中序分為左右子樹，不斷遞迴即可建構出唯一的二元樹。

🤖

AI 詳解

AI 專屬家教

分析過程：

查看更多「[資訊] 資訊管理、程式設計」的主題分類考古題