from
The Free On-line Dictionary of Computing (8 July 2008)
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)