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

Question

我将数据存储在树的叶子中。使用作为对象元组的键访问叶子。这棵树可能很大，我想浓缩它。例如：

        *
       / \
      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代表 a1或5。当然，由于必须检查 set 中的成员身份，查找速度会减慢A。我正在寻找描述此数据结构和相关过程的来源。

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

Answer 1

在不知道您使用树的目的的情况下，很难提出建议，但我相信这样的树结构在实践中永远不会真正有用，因为使用某种排序集或关联映射比这容易得多.

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