設計 AVL 樹的類

由於 AVL 樹是二元搜尋樹，因此 AVLTree 被設計為 BST 的子類。 AVL樹是二元樹，因此可以定義AVLTree類來擴展BST類，如下圖所示。 BST 和 TreeNode 類別在部分中定義。

為了平衡樹，你需要知道每個節點的高度。為了方便起見，將每個節點的高度儲存在 AVLTreeNode 中，並將 AVLTreeNode 定義為 BST.TreeNode 的子類別。請注意，TreeNode 在 BST 中定義為靜態內部類別。 AVLTreeNode 將被定義為 AVLTree 中的靜態內部類別。 TreeNode 包含資料欄位 element、left 和 right，它們由 AVLTreeNode 繼承。因此，AVLTreeNode包含四個資料字段，如下圖所示。

在 BST 類別中，createNewNode() 方法建立一個 TreeNode 物件。在 AVLTree 類別中重寫此方法以建立 AVLTreeNode。注意，BST類別中的createNewNode()方法的回傳類型是TreeNode，但 類別中的> 方法是AVLTreeNode。這很好，因為 AVLTreeNode 是 TreeNode 的子類別。 在AVLTree

中搜尋元素與在常規二元樹中搜尋相同，因此

BST 類別中定義的search 方法也適用於AVLTree。 重寫 insert

和

delete 方法來插入和刪除元素，並在必要時執行重新平衡操作以確保樹平衡。

以上是設計 AVL 樹的類的詳細內容。更多資訊請關注PHP中文網其他相關文章！