c# - 具有规范布局的搜索树

Question

我正在寻找可以按规范形式组织的搜索树。

如果我在这里用错了术语“规范”，请原谅。我的意思是；给定一组要存储在树中的项目，无论进行什么操作使这些项目最终出现在树中，最终的节点结构都是相同的。

我不需要总是提供此功能的结构；如果有“请使其成为规范”功能就足够了。

我目前已经在 C# 中创建了一个基本的 AVL 树实现。

当我向其中添加七个项目 (1-7) 时，通过附加它们，我最终得到以下节点:

              4
           /     \
        2          6
      /   \      /   \
    1      3    5     7

如果我改为首先添加项目 1、2、0、3、4、5、6、0、7，通过附加它们，然后删除这两个零，我最终得到以下结果节点代替:

           3
         /   \
        2     5
       /    /   \
      1    4     7      
                /
               6

枚举这两棵树中的项目会产生相同的预期结果。但是节点结构不同，这是我想避免的。

我知道我可以通过从头开始创建一棵新树来实现“请使其成为规范”功能。但这并不能扩展。

如果要达到规范形式需要付出太多努力，我也很乐意用规范属性换取速度。

---

为什么是“规范”？

我正在追求一个想法，我将使用基于内容的分块算法 (TTTD) 将树分块，然后将这些 block 存储在不可变的 blob 存储中。

使用这种方法，一些子节点将是内联的:存储在与父节点相同的 block 中。其他节点将是外部节点:由基于内容的地址(SHA-1 哈希)引用。

当两个子树具有相同的内容(包括结构)时，它们将具有相同的地址。这个属性很有用，原因有很多；包括:

• 有效地计算两个子树之间的差异。
• 缓存。
• 同步。

Answer 1

您可以使用 trie，它具有 key 位长度的最大更新和搜索时间，或者您可以使用 A. Andersson and Th. Ottmann. "Faster Uniquely Represented Dictionaries" ，其最大更新和搜索时间为\Theta(n^{1/3})。