CODEWITHSUNDEEP
data-structuresbinary-search-treecomputational-geometry
aas
aas

Reputation: 187

Dynamically building a balanced BST with values "in the leaves"?

In their book Computational Geometry (2008), de Berg, et al., describe the data structure underlying their range search algorithm as a balanced BST where "leaves of T store the points of P and the internal nodes of T store splitting values to guide the search."

The Wikipedia page on range trees (link), which cites de Berg, says: "A 1-dimensional range tree on a set of n points is a binary search tree" such that "each node which is not a leaf stores the largest value of its left subtree."

Examples online construct such trees statically, by first sorting the set of points and then recursively pairing up nodes.

Does there exist an algorithm to build a BST of this nature dynamically (i.e., with the ability to insert additional values into the tree)? Where is it described?

Upvotes: 0

Views: 153

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59368

It's possible to adapt just about any tree balancing procedure to work with these two examples, just by treating the leaves separately -- make a balanced tree of the internal nodes, and then take care to keep the leaves in order. Each operation, including balancing, will require you to recalculate the "summary statistics" on at most O(log N) nodes. Those are all the nodes that were updated and their ancestors.

This can be a little complicated, though, and doesn't work for the multi-dimensional range tree, because every level is treated differently from the ones above and below, and that makes tree rotations (which most balancing operations require) invalid.

For these kinds of trees, therefore, where different levels are handled differently, it is usually best to just avoid tree rotations by using a low-order B+tree variant like a 2-3 tree. In a tree like this, nodes can be split and merged, but they never have to change height -- you can implement them so that leaves are always leaves and internal nodes are always internal. The height of the tree is only ever changed by adding or removing the root.

Of course, if you use a tree that can have more than 2 children per node, then your search algorithms will need to change, but the changes are typically trivial.

Upvotes: 1

Related Questions