Week 10 (43)

Rebalancing Trees

An approach to balanced trees:

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

Question: how frequently/when to rebalance?

Tree NewTreeInsert(Tree t, Item it)
{
	t = TreeInsert(t,it);
	// e.g. after every 20 insertions
	if (size(t) % 20 == 0)
		t = rebalance(t);
	return t;
}