Search code examples
algorithmdata-structurestreebinary-search-tree

Is there a balanced BST with each node maintain the subtree size?

Is there a balanced BST structure that also keeps track of subtree size in each node?

In Java, TreeMap is a red-black tree, but doesn't provide subtree size in each node.

Previously, I did write some BST that could keep track subtree size of each node, but it's not balanced.

The questions are:

  • Is it possible to implement such a tree, while keeping efficiency of (O(lg(n)) for basic operations)?
  • If yes, then is there any 3rd-party libraries provide such an impl?
    A Java impl is great, but other languages (e.g c, go) would also be helpful.

BTW:

  • The subtree size should be kept track in each node.
    So that could get the size without traversing the subtree.

Possible appliation:

  • Keep track of rank of items, whose value (that the rank depends on) might change on fly.
Solution

  • The Weight Balanced Tree (also called the Adams Tree, or Bounded Balance tree) keeps the subtree size in each node.

    This also makes it possible to find the Nth element, from the start or end, in log(n) time.

    My implementation in Nim is on github. It has properties:

    • Generic (parameterized) key,value map
    • Insert (add), lookup (get), and delete (del) in O(log(N)) time
    • Key-ordered iterators (inorder and revorder)
    • Lookup by relative position from beginning or end (getNth) in O(log(N)) time
    • Get the position (rank) by key in O(log(N)) time
    • Efficient set operations using tree keys
    • Map extensions to set operations with optional value merge control for duplicates

    There are also implementations in Scheme and Haskell available.