balanced tree


Also found in: Wikipedia.

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).
References in periodicals archive ?
A more balanced tree will reduce the expected travel cost, but how can the structure be rebalanced without losing clustering information?
These clusters are used to form a better balanced tree with a branching factor of three, suiting the HTD evaluation metric preferring tertiary or quadruple trees [6].
The second figure shows the result of building a more balanced tree with these small branches.
A more balanced tree will be searched more thoroughly, i.
If the tree is not a leaner, it may be possible to use the felling cuts to bring it down where you want it--but don't bet the farm on it; if you cut wood long enough, eventually an apparently straight, well balanced tree will surprise you.
Next, we give a method that allows obtaining a partially balanced tree in weight P of FO formula [phi].
Then, for every subtree T' de T, if it leads the first case, it is trivially considered partially balanced tree.
Let us note that if we arrive to the tree root by the first situation, we obtain a similar result to a totally balanced tree.
Chapter 9 on balanced trees has expanded coverage of B-trees and a new section on Java 6 SkipList.