http://algorist.com/algowiki/index.php?title=TADM2E_3.8&feed=atom&action=historyTADM2E 3.8 - Revision history2019-07-21T12:42:00ZRevision history for this page on the wikiMediaWiki 1.23.3http://algorist.com/algowiki/index.php?title=TADM2E_3.8&diff=560&oldid=prevJustiny: 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<p>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..."</p>
<p><b>New page</b></p><div>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: <br />
1. Initialize rank to 1.<br />
2. Add the size of the left subtree plus one (for the visited parent) every time the right child of a node is visited.<br />
3. Increment the size of the left subtree every time the left child of a node is visited.<br />
''Insert(x, T)'' takes O(log n) as the height of the tree is log n.<br />
''delete(x, T)'' takes O(log n) as the ranks and sizes can be recursively updated in O(log n) after the deletion.<br />
''member(x, T)'' is a search on BSTand is O(log n)</div>Justiny