Weight-balanced tree

Weight-balanced tree

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.

The Diagram

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

Timing Analysis

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

See also

* Binary tree
* AVL tree
* B-tree
* Binary space partitioning
* Red-black tree

References

* Jean-Paul Tremblay and Grant A. Cheston. "Data Structures and Software Development in an object-oriented domain", Eiffel Edition. Prentice Hall, 2001. ISBN 0-13-787946-6.


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Scapegoat tree — In computer science, a scapegoat tree is a self balancing binary search tree, invented by Igal Galperin and Ronald L. Rivest. It provides worst case O(log n ) lookup time, and O(log n ) amortized insertion and deletion time.Unlike other self… …   Wikipedia

  • Australian Green Tree Frog — Conservation status Least Concern ( …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

  • Список терминов — Список терминов, относящихся к алгоритмам и структурам данных   Это сл …   Википедия

  • English saddle — English saddles are used to ride horses in English riding disciplines throughout the world. The discipline is not limited to England or English speaking countries. This style of saddle used in all of the Olympic and FEI equestrian disciplines,… …   Wikipedia

  • Stanley Kubrick — Infobox Actor name = Stanley Kubrick imagesize = 300px caption = Self Portrait of Kubrick with a Leica III camera, when he worked for Look (from the book Drama and Shadows ). birthdate = July 26, 1928 location = New York City, New York, U.S.… …   Wikipedia

  • Whom the Gods Would Destroy — is a novel written by Richard P. Powell. It was published in 1970 by Charles Scribner s Sons, NY. The title is currently out of print.The story is narrated through the point of view of a young boy named Helios who grows up during the Trojan… …   Wikipedia

  • arts, East Asian — Introduction       music and visual and performing arts of China, Korea, and Japan. The literatures of these countries are covered in the articles Chinese literature, Korean literature, and Japanese literature.       Some studies of East Asia… …   Universalium

  • literature — /lit euhr euh cheuhr, choor , li treuh /, n. 1. writings in which expression and form, in connection with ideas of permanent and universal interest, are characteristic or essential features, as poetry, novels, history, biography, and essays. 2.… …   Universalium

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”