允许将树视图作为平面列表进行范围查询的索引结构

Question

我需要在基本上是支持数据虚拟化的列表视图中呈现树结构。为此，我需要能够根据项目的索引或在可见树中的位置查询树中的一系列项目。

因为树中的每个节点可能包含数百万个子节点，所以我只在父节点展开时才加载子节点。在后端，我想为文件中的每个扩展节点缓存加载的子节点。然后，前端需要能够查询项目的可见范围，就好像它是一个平面列表一样。

例如树：

需要以 [A, A1, A2, B, B1, C, D] 的列表形式呈现。

折叠一个节点，例如 A 将产生结果 [A, B, B1, C, D]。

为此，需要某种索引来跟踪扩展节点和缓存数据所在的位置。

要做到这一点，一个想法是拥有某种范围图，我们在其中将索引（或位置）映射到数据文件。所以对于上面的树，我们可以有类似的东西：

[0, 0] => (Root, 0)
[1, 2] => (A, 0)
[3, 3] => (Root, 1)
[4, 4] => (B, 0)
[5, 6] => (Root, 2)

这样的索引可以允许快速查询范围，例如检索索引 2 和 5 之间的所有项目。

但是，存储这种索引的良好数据结构是什么？由于展开或折叠节点需要更改正在展开或折叠的节点的所有后继节点的间隔。

或者有更好的方法来构建这样的索引吗？

Answer 1

平衡二叉搜索树可以有效地支持这些操作。不会有钥匙。相反，每个节点将根据其位置进行定位（即，键是隐式的）。每个节点的值是指向它对应的项目的指针。我们还需要一个辅助数据结构，将一个节点从原始树映射到平衡二叉搜索树中的一个节点（例如，我们可以使用散列 table）。可以通过以下方式进行操作：

折叠节点：我们应该在搜索树中找到与原始树中折叠节点对应的节点。假设它有 k children。然后我们只需要从搜索树和哈希 table 中删除 k 个下一个节点。这个操作的时间复杂度是O(k * log n).
扩展一个节点：和1差不多，我们可以通过hashtable在二叉搜索树中定位这个节点，然后插入kchildren 在它之后。我们还需要将这些 children 添加到散列 table 中。它还需要 O(k * log n) 时间。
范围查询：我们需要做的就是遍历二叉搜索树，只访问给定范围内的那些节点。具有隐式键的树允许我们在不访问范围之外的任何节点的情况下执行此操作。所以这个操作的时间复杂度是O(size_of_the_range + log n)。

我没有找到任何关于使用隐式键的二叉搜索树的文章，但我认为 this question 会有所帮助。我实际上不确定是否可以对任何二叉搜索树使用隐式键，但绝对有可能进行 treap。

An index structure to allow range queries of a tree view as a flat list