balanced tree

balanced tree

(algorithm)An optimisation of a tree which aims to keepequal numbers of items on each subtree of each node so as tominimise the maximum path from the root to any leaf node.As items are inserted and deleted, the tree is restructured tokeep the nodes balanced and the search paths uniform. Such analgorithm is appropriate where the overheads of thereorganisation on update are outweighed by the benefits offaster search.

A B-tree is a kind of balanced tree that can have morethan two subtrees at each node (i.e. one that is notrestricted to being a binary tree).