Coding4Fun - AVL 樹新手練習區

上回提到我最近在看 Hello 演算法。這陣子進度推進到 AVL 樹，原理不算難，把握「Balance Factor 達到正負 2 就旋轉節點降回正負 1 以內以維持平衡化」的原則，再將旋轉規則簡化成：LL 右旋、LR 左旋再右旋、RR 左旋、RL 右旋再右旋，就算學完了。

圖片來源

話雖如此，但真給我一棵不平衡的 AVL 樹問該怎麼轉，我腦袋會當住三五秒，來回琢磨大半天才拼出一個沒把握的答案。(汗)

最近剛好是研究所考試旺季，前幾天在 Dcard 看到一則帖子：

哈，這不就我？對薛丁格 AVL 樹介會與不會之間的疊加態。

但往下讀到卡友留言，我有中了好幾槍的感覺...

於是，老程序員決心要把資工基本常識弄懂，要求自己拿到不平衡 AVL 樹能三秒腦內旋轉完成，勇敢說出答案。(其實更多是預防老年痴呆啦，Strang 教授應該就是每天算代數才能教書到 88 歲還耳聰目明身體勇健)

總之，仿效上次在網頁畫二元搜索樹的概念，我寫了一個 線上版 AVL 樹遊戲區練習 AVL Tree。

操作介面很簡單，加入節點區可以新增不同數字到 AVL 樹，下方則為已經在樹上的數字節點，點選可移除，可預測及驗證插入位置及移除後的節點狀況當成練習。

當出現不平衡(平衡因子大於 +1 或小於 -1)，插入或移除程序會暫停，顯示旋轉前的狀態，此時可先在心中預判要如何旋轉修正，再按下左旋、右旋鈕對答案：

右上區可以保存預先設計好的題目(按【範例】鈕可以載入幾個我隨手蒐集的範例)，將其載入到步驟區，按左右鈕可以上一步下一步觀察樹的成長及演進，當遇到需要左右旋，網頁一樣會暫停以分解動作讓你復習 AVL 樹左右旋處理：

上圖便是我復刻 Hello 演算法的 AVL 樹左旋範例。

最後，為了方便教學和內卷分享交流，網頁支援使用 URL # 傳送題目，例如以下這題：

大家可以一眼看出平衡後的結果嗎？

我已透過 https://darkthread.github.io/algo-lab/tree/avl-tree.html#EX1:8,10,5,6,3,9,4,12,11,15,13:11 將題目轉成可實際操作的 AVL 樹，點進去對答案吧。

URL 的 # Hash 格式為 : 分隔成三段，第一段為說明、第二段為插入數字順序，第三段為停留在第幾步驟。除了自己手動編輯，網頁也提供了簡單工具方便編輯說明文字[1]、複製 URL [2] 及暫存(保存在 localStorage)。

希望這個小工具 (網址：https://darkthread.github.io/algo-lab/tree/avl-tree.html) 能幫助到正在學習 AVL 樹的同學們，人人都練就看圖一秒說結果的功力。GO! (其實也不用走火入魔到這樣啦 XD)
(操作使用如有不順之處，歡迎留言建議，隨緣修改)

The post introduces an online AVL tree practice tool, allowing users to add/remove nodes and observe tree balancing. The tool supports sharing and loading specific scenarios via URL, enhancing learning and practice efficiency.