c++ - 在叶子上有重复条目的树

我的数据存储在树的叶子中。叶子是通过对象元组的键来访问的。这棵树可能很大，我想浓缩一下。例如:

        *
       / \
      a   b
     /|\   \
    1 2 5   1
   / /| |\  |\
  x x y x z y z   <-- Leaves
  | | | | | | |
  1 2 7 1 3 1 1   <-- Values at leaves

元组(*, a, 1, x)和(*, a, 5, x)都导致叶子处的1值，因此可以将树压缩为:

        *
       / \
      a   b
     / \   \
    A   2   1
   /|  /|   |\
  x z x y   y z
  | | | |   | |
  1 3 2 7   1 1

其中A代表1或5。当然，由于必须检查集合A中的成员资格，因此查找速度变慢。我正在寻找描述此数据结构和相关过程的资源。

我正在使用c++，以防有人启发共享相关的代码问题。

最佳答案

在不知道您将树用作什么的情况下，很难提出建议，但是我认为，这样的树结构实际上在实践中永远不会有用，因为使用某种排序集或关联映射要比这容易得多。 。

但是，如果您已经具有树结构并希望保持当前的效率，则可以合并分支而不是合并分支，而将所有叶子替换为指向数据的指针。这样，您可以存储每个数据对象一次，并有多个叶子指向同一数据对象。这也是最灵活的解决方案，因为您仍然可以通过简单地更改指针来更改任何叶子的值，而在合并分支的想法中，如果没有持久的数据结构，就无法撤消它。

关于c++ - 在叶子上有重复条目的树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16994055/