Weight-balanced tree

From Wikipedia, the free encyclopedia
Jump to: navigation, search

A weight-balanced binary tree is a binary tree which is balanced based on knowledge of the probabilities of searching for each individual node. Within each subtree, the node with the highest weight appears at the root. This can result in more efficient searching performance.

Construction of such a tree is similar to that of a Treap, but node weights are chosen randomly in the latter.

Example of weight balanced tree

The diagram[edit]

In the diagram to the right, the letters represent node values and the numbers represent node weights. Values are used to order the tree, as in a general binary search tree. The weight may be thought of as a probability or activity count associated with the node. In the diagram, the root is G because its weight is the greatest in the tree. The left subtree begins with A because, out of all nodes with values that come before G, A has the highest weight. Similarly, N is the highest-weighted node that comes after G.

Timing analysis[edit]

A weight balanced tree gives close to optimal values for the expected length of successful search calculations. From the above example we get

ELOSS = depth(node A)*probability(node A) + depth(node C)*probability(node C) + ...

ELOSS = 2*0.17 + 5*0.03 + 4*0.09 + 3*0.12 + 1*0.20 + 3*0.11 + 3*0.10 + 2*0.18

ELOSS = 2.5

This is the expected number of nodes that will be examined before finding the desired node.

See also[edit]