通過繼承實現AVL樹

Question

我被要求實現一個AVL樹，我做到了 - 現在它適用於我所能想到的所有壓力測試。現在我看到我們被建議實現它，s.t繼承了從二叉樹繼承的二叉搜索樹。我想說得很對 - 我很樂意得到關於哪些不變量（必須出現的字段）應該出現在每個變量（二叉樹，搜索和AVL）中的建議。 謝謝！ 這裏是我的實施：

Answer 1

我給你一些提示。在編寫面向對象的代碼時，我發現設計自頂向下是有用的 - 即實現父類，然後繼承並決定需要添加/重寫的內容。

例子：

二叉樹：

1. 那麼，你顯然需要一個節點，有兩個孩子（你如何實現這是你的事）。節點需要一個數據字段。
2. 插入 - 沒有限制，您可以在節點向左，向右或替換父節點之後插入。你實現了哪些，以及如何取決於你。
3. 穿越 - 向左走比右，右不是從左等...
4. 查找有沒有限制，所以你將不得不遍歷整個樹（最壞情況）

所有這些都是一般性質一棵二叉樹。你可以想出更多（打印調試用途等）。我們繼承了所有這些，並與啓動：

二叉搜索樹

1. 節點並沒有真正改變，不是嗎？
2. 那麼現在插入不是由你決定！您不會插入到插入到整個樹中的特定節點。你需要尋找你想插入的地方，然後你可以調用基地插入。
3. 遍歷不會改變嗎？
4. 查找可以大大改善，可能應該完全覆蓋。
5. 您可以考慮對非排序搜索樹無意義的新方法，儘管我沒有想到任何提示。有些人可能會考慮將一個比較（小於例如）運算符添加到節點，將其重載以與數據類型或其他節點進行比較。

最後，你繼承這個做一個AVL樹。嘗試並考慮可以繼承的東西，需要完全覆蓋的東西以及調用基類之前需要做些什麼的東西。你可以通過谷歌/維基百科進行常見的樹操作（例如，我沒有提到刪除）。祝你好運。

編輯

AS davmac提到，一個AVL的節點改變 - 它需要一個額外的領域！我們有兩個我們繼承的孩子和數據領域，但現在我們還需要一個平衡因素。這是添加字段的示例。