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
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.
A weight balanced tree gives close to optimal values for the expected length of successful search calculations. From the above example we getELOSS = depth(node A)*probability(node A) + depth(node C)
This is the expected number of nodes that will be examined before finding the desired node.
Data Structures Related Interview Questions
|RDBMS Interview Questions||DBMS Interview Questions|
|Adv Java Interview Questions||Core Java Interview Questions|
|C Interview Questions||Database Administration Interview Questions|
|CSS Advanced Interview Questions||Maven Interview Questions|
|Computer architecture Interview Questions||Object Oriented Analysis and Design Interview Questions|
|Standard Template Library (STL) Interview Questions||Xml Publisher Interview Questions|
Data Structures Tutorial
Abstract Data Types
All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd
Wisdomjobs.com is one of the best job search sites in India.