Week 4: Search Tree Data Structures and Algorithms (67)

Rebalancing Trees

Another approach to balanced trees:

insert into leaves as for simple BST
periodically, rebalance the tree

Question: how frequently/when/how to rebalance?

NewTreeInsert(tree,item):
|  Input  tree, item
|  Output tree with item randomly inserted
|
|  t=insertAtLeaf(tree,item)
|  if #nodes(t) mod k = 0 then
|     t=rebalance(t)
|  end if
|  return t

E.g. rebalance after every 20 insertions ⇒ choose k=20

Note: To do this efficiently we would need to change tree data structure and basic operations:

typedef struct Node {
   Item data;
   int  nnodes;      // #nodes in my tree
   Tree left, right; // subtrees
} Node;