c++ - 我应该使用多重继承来实现链表搜索树吗？

Question

我有一个 List 类和一个 AVL Tree 类，我想创建一个本质上是 AVL 树的类，并添加了遍历元素的选项升序:

            _5_
          _/   \_
         3       8
        / \     / \
       2   4   7   9

       2,3,4,5,7,8,9

重点是，我希望能够在 O(log(n)) 时间内插入/删除等，但我也想从 4 开始在 O(1) 时间内到 5。

我应该使用 MI 创建一个新类吗？

class ListTree: private List, public Tree

如果是这样，我应该担心什么？如果不是，为什么不呢？

Answer 1

如果您的新类与您设想的所有基类具有“是”关系，那么多重继承是一个很好的选择。

它是一棵树吗？

I want to create a class that is essentially an AVL tree with the added option of ...

根据此声明，您的 ListTree 绝对是一个 Tree 并且应该继承自它。

是列表吗？

好吧，这取决于您的 List 背后的内容!如果它是一个纯虚类，只定义了一个需要在具体列表类中派生的接口(interface)，那么是:从抽象的角度来看，您的ListTree 是一个列表。

但是如果您的 List 已经是一个具体的类——我在这里假设——那么答案应该是NO。为什么 ？列表是扁平的，而树不是。可以像列表一样遍历树这一事实并不能使它成为列表。

如果您随后选择 MI，您将继承 Tree 和 List 的内部数据。对于插入和删除等每个操作，您必须以一致的方式同步两个结构。例如，如果您只是将插入委托(delegate)给两个基类，那么您的时间复杂度为 O(n) 而不是 O(log(n))。

那怎么办？

如果不知道您如何管理容器元素，就很难给出进一步的建议。

如何将 List 成员添加到您的 ListTree 类(组合而不是继承)，并在您的树中存储对列表节点的引用/指针？

对于遍历，您将使用 O(1) 中的列表。删除/插入，用树在O(log(n))中找到插入或删除的节点，对列表节点进行操作(前提是列表是双链的)，知道平衡是不影响列表中节点的顺序。