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

Question

I need to present a tree structure in what is basically a list view with support for data virtualization. To do this I need to be able to query for a range of items in the tree based on their index, or position in the visible tree.

Because each node in the tree may contain millions of children, I load children only when a parent node is expanded. On the back-end side I want to cache the loaded children for each expanded node in a file. The front-end then needs to be able to query for the visible range of items as if it was a flat list however.

So for example the tree:

• Root
  • A
    • A1
    • A2
  • B
    • B1
  • C
  • D

Would need to be presented as a list like [A, A1, A2, B, B1, C, D].

Collapsing a node, for example A would instead yield the result [A, B, B1, C, D].

To do this some kind of index is needed to keep track of expanded nodes and where the cached data resides.

To do this one idea was to have some sort of range map, where we map indices (or positions) to data files. So for the tree above we could have something like:

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

Such an index could allow for fast querying of a range, for example to retrieve all items between index 2 and 5.

However, what would be a good data structure to store such an index? Since expanding or collapsing nodes requires changing the intervals of all successors to the node being expanded or collapsed.

Or is there a better way to structure such an index?

Answer 1

A balanced binary search tree can support these operations efficiently. There will be no keys. Instead, each node will be located based on its position(that is, keys are implicit). The value for each node is pointer to an item it corresponds to. We will also need an auxiliary data structure that maps a node from an original tree to a node in out balanced binary search tree(we can use a hash table, for instance). The operations can be done in the following way:

1. Collapsing a node: we should find a node in the search tree that corresponds to the collapsed node in the original tree. Let's assume that it has k children. Then we just need to remove the k next nodes from the search tree and the hash table. The time complexity of this operation is O(k * log n).

2. Expanding a node: almost the same as 1. We can locate this node in the binary search tree using the hash table and then insert k children after it. We also need to add these children to the hash table. It also requires O(k * log n) time.

3. Range query: all we need to do is to traverse the binary search tree visiting only those nodes that are inside the given range. A tree with implicit keys allows us to do it without visiting any nodes that are outside of the range. So the time complexity of this operation is O(size_of_the_range + log n).

I didn't find any articles on binary search trees with implicit keys, but I think this question can be helpful. I'm actually not sure if it is possible to use implicit keys with any binary search tree, but it is definitely possible for a treap.