这个数据结构怎么称呼？

Question

几个月前，我的同事向我展示了一种数据结构，它基本上是一棵树，但带有一些附加数据，可以使某些操作执行得更快、更高效。我只剩下一张图表，显示了该 DS 的可能架构。

Answer 1

这是一棵用某种前序信息和后序信息进行“增强”的树。除了微不足道的深度之外，我们还可以得出：

给定节点的前序序号为 (LKey + Depth + 1) / 2，其中根的编号为 1，其左子节点为 2，...，最右边的叶子为 13。
类似地，给定节点的后序序列号为 (RKey + Depth + 1) / 2，其中最左边的节点为数字 1，其父节点为 2，...，根节点为 13。
以给定节点为根的树的大小为 (RKey - LKey + 1) / 2，因此例如 id 为 8 的节点以具有 (25-18+1)/2 = 4 个节点的树为根。因此所有叶子节点都有 RKey - LKey = 1。
此结构仅在树静态时才有用，即不添加或删除任何节点，因为这些操作的时间复杂度为 O(𝑛)。但如果这些操作不相关，那么这个结构可以提供有关节点的信息，否则需要您遍历树。

此外，此结构需要每个节点（即值）一些

payload

，否则它不会存储比树的形状更多的内容。在实践中，您可能想要存储一些具有一定商业意义的数据。 请注意，Id 信息只是一个唯一标识符：我们无法仅从这个示例中看到它，但它可能会给出节点添加到树中的顺序，以便保证节点的 id 大于该顺序其父级的，并且根的 ID 为 1。