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).

This article is provided by FOLDOC - Free Online Dictionary of Computing (foldoc.org)

Mentioned in

References in periodicals archive

In a strictly balanced tree, the value range of balance factor should only be [-1,1], which is the balance criterion of the original AVL tree.

Enabling Efficient Verification of Dynamic Data Possession and Batch Updating in Cloud Storage

Definition 2: The height difference of any one node in the tree or subtree is not greater than 1, so that the tree is a balanced tree.

Research on hierarchical tree structure of multi dimension data index in centralized environment

This results in a balanced tree construction, in which none of the nodes are overburdened.

A multi tree based approach for performance analysis in hierarchical wireless sensor networks

That means the balanced tree topology construction approach significantly improves the network lifetime and causes only very low extra data latency overhead when doing that.

Controlled sink mobility algorithms for wireless sensor networks

A more balanced tree will reduce the expected travel cost, but how can the structure be rebalanced without losing clustering information?

Hierarchical topic detection in large digital news archives: exploring a sample based approach

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.

A woodcutter's lament: the difficulties and dangers of cutting firewood. (The woodlot)

Given an unbalanced tree T, we construct a balanced tree T' from T.

Divide-and-Conquer Approximation Algorithms via Spreading Metrics

I ranges from zero for a perfectly balanced tree to one for a perfectly imbalanced tree [ILLUSTRATION FOR FIGURE 1 OMITTED].

Patterns in phylogenetic tree balance with variable and evolving speciation rates

Balanced tree algorithms rearrange the tree as operations are performed to maintain certain balance conditions and assure good performance.

Skip lists: a probabilistic alternative to balanced trees

Because there is more than one way to make the same balanced tree, the Markov model predicts a relatively high proportion of balanced trees.

Problems with null models in the study of phylogenetic radiation

The global balancing algorithms inspect all of the nodes in a tree in order to reconstruct a balanced tree. The global strategies produce either a perfectly balanced tree [2, 3, 9] or a route balanced tree [4, 11] (i.e., a tree with minimal internal path length).

An insertion algorithm for a minimal internal path length binary search tree