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*would also be helpful.`c`

,`go`

)

**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.

- Difference between back tracking and dynamic programming
- How can we optimize this algorithm from O(N ** 2) to better complexity in order to pass performance test?
- How do I predict the required size of a Base32 Decode output?
- Reversing AND Bitwise
- Why does my binary search need an extra comparison? log2(N)+1
- How to build a trie for finding exact phonetic matches, sorted globally by weight, and paginated? (Building off this example)
- What is the Time Complexity and Space Complexity of extending a string according to a rule?
- Skyscraper puzzle algorithm
- Check if all elements in a list are equal
- Bitwise Interval Arithmetic
- fast algorithm for drawing filled circles?
- How to find distance from the latitude and longitude of two locations?
- Determine if two rectangles overlap each other?
- Randomly Splitting a Graph according to Conditions
- Maximize distance while pushing crates
- Free a binary tree without recursion
- How can I estimate number of nodes in given tree structure?
- Explanation of class Definition for Binary Trees in leetcode
- Procedural Generation of 2D Rooms
- Is there an algorithm to find the closest element to X in an unsorted array in Ω(logN)?
- Advanced Java idiom for 2+ classes implementing a generic interface
- Is there any algorithm in c# to singularize - pluralize a word?
- Number of Common sub sequences of two strings
- Trying to solve problem 19 on Euler Project
- is a "non-decreasing" sequence "increasing"?
- Is it possible to get the original value of a number, after several multiplications **with overflow**?
- Algorithm to determine the highest and lowest possible finishing position of a team in a league
- Algorithm to calculate the number of divisors of a given number
- Rolling or sliding window iterator?
- best way to pick a random subset from a collection?