[prev] 14 [next]

Rebalancing Trees

An 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 {
   int  data;
   int  nnodes;      // #nodes in my tree
   Tree left, right; // subtrees
} Node;