我被要求实现一个 AVL 树，我做到了 - 现在它适用于我能想到的所有压力测试。现在我看到我们被建议实现它，s.t 它继承自二叉搜索树，二叉搜索树继承自二叉树。我想要它是正确的——我很高兴得到关于哪些不变量(必须出现的字段)应该出现在它们中的每一个(二叉树、搜索和 AVL)中的建议。
谢谢你!
这是我的实现:
最佳答案
我会给你一些建议。在编写面向对象的代码时，我发现自上而下的设计很有用 - 即实现父类，然后继承并决定需要添加/覆盖的内容。
例子:
二叉树:
- 好吧，您显然需要一个有两个子节点的节点(如何实现那是您的事)。节点需要一个数据字段。
- 插入 - 没有限制，您可以在节点后向左、向右插入或替换父节点。您实现哪些以及如何实现由您决定。
- 遍历 - 向左走比向右走，向右走比向左走等...
- 查找没有限制，所以你将不得不遍历整棵树(最坏的情况)
所有这些都是二叉树的一般属性。您可以想出更多(打印用于调试等...)。我们继承了所有这些并开始于:
二叉搜索树
- Node 并没有真正改变，对吗？
- 好吧，现在插入根本不是由你决定的!您不插入到插入到整个树的特定节点。你需要找到你要插入的地方，然后你就可以调用base insertion。
- 遍历不会改变，对吗？
- 查找可以得到显着改进，并且可能应该被完全覆盖。
- 您可以想到对非有序搜索树没有意义的新方法，但我还没有想到。有些人可能会考虑向节点添加一个比较(例如小于)运算符，重载它以与数据类型或另一个节点进行比较。
最后，您继承它来创建一个AVL 树。尝试并考虑哪些可以按原样继承，哪些需要完全覆盖，以及在调用基类之前需要做一些工作。您可以在 google/wikipedia 上搜索常见的树操作(例如，我没有提到删除)。祝你好运。
编辑
正如 davmac 所提到的，AVL 的节点发生了变化——它需要一个额外的字段!我们继承了两个 child 和数据字段，但现在我们还需要一个平衡因素。这是何时添加字段的示例。
关于c++ - 通过继承实现 AVL 树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40842031/