moea_joint_essay 113年 [統計資訊] 資料庫及資料探勘、程式設計

第二題

📖 題組：
請依下列條件畫出樹狀圖：（2 題，每題 6 分，共 12 分）

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

小題 (二)

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

逐步畫出插入節點的過程，並隨時檢查 Balance Factor。發生不平衡時(LL, RR, LR, RL)，進行對應旋轉以保持 AVL 樹平衡性質。

🤖

AI 詳解

AI 專屬家教

逐步插入與旋轉過程：

插入 53, 68, 72：導致 53 的 RR 不平衡。對 53 進行左旋。樹變成 68 為根，左 53，右 72。
插入 5, 47：5 接在 53 左側，47 接在 5 右側。導致 53 發生 LR 不平衡。對 53 進行 LR 旋轉 (先對 5 左旋，再對 53 右旋)。結果為 47 升級為 68 的左子節點，47 的左子為 5，右子為 53。

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

利用前序的第一個元素為根節點，對應中序切分左右子樹，遞迴建構出完整二元樹。

🤖

AI 詳解

AI 專屬家教

推導過程：

查看更多「[統計資訊] 資料庫及資料探勘、程式設計」的主題分類考古題