balanced tree

algorithm An optimisation of a tree which aims to keep

equal numbers of items on each subtree of each node so as to

minimise the maximum path from the root to any leaf node.

As items are inserted and deleted, the tree is restructured to

keep the nodes balanced and the search paths uniform. Such an

algorithm is appropriate where the overheads of the

reorganisation on update are outweighed by the benefits of

faster search.

A B-tree is a kind of balanced tree that can have more

than two subtrees at each node (i.e. one that is not

restricted to being a binary tree).

(2000-01-10)