通过继承实现 AVL 树
AVL tree implementation via inheritance
我被要求实现一个 AVL 树，我做到了 - 现在它适用于我能想到的所有压力测试。现在我看到我们被建议实施它，s.t 它继承自二叉搜索树，二叉搜索树继承自二叉树。我想要它是正确的——我很高兴得到关于哪些不变量（必须出现的字段）应该出现在每个变量（二叉树、搜索和 AVL）中的建议。
谢谢你！
这是我的实现：
我给你一些提示。在编写面向 object 的代码时，我发现自顶向下设计很有用 - 即实现 parent class，然后继承并决定需要什么 added/overriden。
示例：
二叉树：
- 好吧，你显然需要一个节点，有两个 children（你如何实现那是你的事）。节点需要一个数据字段。
- 插入 - 没有限制，您可以在节点后向左、向右插入或替换 parent。您实施哪些以及如何实施取决于您。
- 遍历 - 向左走比向右走，向右走比向左走等等...
- 查找没有限制，所以你将不得不遍历整棵树（最坏的情况）
所有这些都是二叉树的一般属性。您可以想出更多（打印用于调试等...）。我们继承了所有这些并开始于：
二叉搜索树
- 节点并没有真正改变，是吗？
- 那么现在插入根本不是由你决定的！您不插入到插入到整个树的特定节点。你需要寻找你要插入的地方，然后你可以调用碱基插入.
- 遍历不会改变是吗？
- 查找可以大大改进，可能应该完全覆盖。
- 您可以想到对非有序搜索树没有意义的新方法，但我没有想到。有些人可能会考虑向节点添加 compare（例如小于）运算符，重载它以与数据类型或另一个节点进行比较。
最后，你继承它来制作一棵AVL树。尝试并考虑哪些可以按原样继承，哪些需要完全覆盖，以及在调用基 class 之前需要做一些工作。您可以 google/wikipedia 进行常见的树操作（例如，我没有提到删除）。祝你好运。
编辑
正如 davmac 提到的那样，AVL 的节点发生了变化——它需要一个额外的字段！我们继承了两个 children 和数据字段，但现在我们还需要一个平衡因素。这是何时添加字段的示例。
我被要求实现一个 AVL 树，我做到了 - 现在它适用于我能想到的所有压力测试。现在我看到我们被建议实施它，s.t 它继承自二叉搜索树，二叉搜索树继承自二叉树。我想要它是正确的——我很高兴得到关于哪些不变量（必须出现的字段）应该出现在每个变量（二叉树、搜索和 AVL）中的建议。
谢谢你！
这是我的实现：
我给你一些提示。在编写面向 object 的代码时，我发现自顶向下设计很有用 - 即实现 parent class，然后继承并决定需要什么 added/overriden。
示例：
二叉树：
- 好吧，你显然需要一个节点，有两个 children（你如何实现那是你的事）。节点需要一个数据字段。
- 插入 - 没有限制，您可以在节点后向左、向右插入或替换 parent。您实施哪些以及如何实施取决于您。
- 遍历 - 向左走比向右走，向右走比向左走等等...
- 查找没有限制，所以你将不得不遍历整棵树（最坏的情况）
所有这些都是二叉树的一般属性。您可以想出更多（打印用于调试等...）。我们继承了所有这些并开始于：
二叉搜索树
- 节点并没有真正改变，是吗？
- 那么现在插入根本不是由你决定的！您不插入到插入到整个树的特定节点。你需要寻找你要插入的地方，然后你可以调用碱基插入.
- 遍历不会改变是吗？
- 查找可以大大改进，可能应该完全覆盖。
- 您可以想到对非有序搜索树没有意义的新方法，但我没有想到。有些人可能会考虑向节点添加 compare（例如小于）运算符，重载它以与数据类型或另一个节点进行比较。
最后，你继承它来制作一棵AVL树。尝试并考虑哪些可以按原样继承，哪些需要完全覆盖，以及在调用基 class 之前需要做一些工作。您可以 google/wikipedia 进行常见的树操作（例如，我没有提到删除）。祝你好运。
编辑
正如 davmac 提到的那样，AVL 的节点发生了变化——它需要一个额外的字段！我们继承了两个 children 和数据字段，但现在我们还需要一个平衡因素。这是何时添加字段的示例。