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

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

Answer 1

不知道你用树做什么，很难提出建议，但我相信这样的树结构在实践中永远不会真正有用，因为使用某种排序集或关联要容易得多 map 比这个。

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