Justiny: Created page with "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..."

2018-07-22T00:21:45Z

Created page with "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..."

New page

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)

TADM2E 3.8 - Revision history

Justiny: Created page with "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..."