# TADM2E 3.8

From Algorithm Wiki

Use a balanced tree structure where the nodes store the rank and the size of the left sub-tree. The rank can be calculated on insertion as follows:
1. Initialize rank to 1.
2. Add the size of the left subtree plus one (for the visited parent) every time the right child of a node is visited.
3. Increment the size of the left subtree every time the left child of a node is visited.
*Insert(x, T)* takes O(log n) as the height of the tree is log n.
*delete(x, T)* takes O(log n) as the ranks and sizes can be recursively updated in O(log n) after the deletion.
*member(x, T)* is a search on BSTand is O(log n)