AVLTree類擴展了BST類來重寫insert和delete方法以在必要時重新平衡樹。下面的程式碼給出了 AVLTree 類別的完整原始碼。
AVLTree 類別擴充了BST。與BST 類別一樣，AVLTree 類別有一個無參數建構函數，用於建構一個空的AVLTree（第5 行），以及一個從元素數組創建初始AVLTree 的構造函數（第8- 10 行） .
BST類別中定義的createNewNode()方法建立一個TreeNode。重寫此方法以傳回 AVLTreeNode（第 13-15 行）。
AVLTree中的insert方法在第18-27行被覆蓋。此方法首先呼叫BST中的insert方法，然後呼叫balancePath(e)（第23行）來確保樹是平衡的。
balancePath方法首先取得從包含元素e的節點到根節點的路徑上的節點（第45行）。對於路徑中的每個節點，更新其高度（第 48 行），檢查其平衡係數（第 51 行），並在必要時執行適當的旋轉（第 51-67 行）。 第 82-178 行定義了四種執行旋轉的方法。每個方法都使用兩個
TreeNode參數（A 和 parentOfA）進行調用，以在節點 A 處執行適當的旋轉。貼文中的附圖說明如何執行每次旋轉。旋轉後，節點A、B和C的高度更新（第98、125、148、175行）。
AVLTree中的delete方法在第183-248行被覆蓋。此方法與BST類別中實作的方法相同，只是在兩種情況下需要在刪除後重新平衡節點（第218、243行）。
以上是AVLTree 類的詳細內容。更多資訊請關注PHP中文網其他相關文章！
