A weight-balanced binary tree
is a binary tree
where the most probable item is the root item. The left subtree
consists of items less than the root items ranking, not its probability. The right sub tree consists of items greater than the root items ranking.
In the diagram to the right the root node is at the top of the tree because its probability is the greatest in the tree. Each node has a probability or activity count associated with it. The number next to the root node is its probability or activity count for that node. The left sub tree begins with A because A is less than G and A has the highest probability or activity count of the left sub tree nodes. The right sub tree begins with N because it is greater than G and has the highest probability/activity count of all the right sub tree nodes
A weight balanced tree gives close to optimal values for the expected length of successful search calculations. From the above example we get
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.4