Java Reference
In-Depth Information
in the case when this node has two children, the depth of the node with smallest
value in its right subtree. Thus, in the worst case, the cost for any one of these
operations is the depth of the deepest node in the tree. This is why it is desirable to
keep BSTs balanced, that is, with least possible height. If a binary tree is balanced,
then the height for a tree of n nodes is approximately log n. However, if the tree
is completely unbalanced, for example in the shape of a linked list, then the height
for a tree with n nodes can be as great as n. Thus, a balanced BST will in the
average case have operations costing (log n), while a badly unbalanced BST can
have operations in the worst case costing (n). Consider the situation where we
construct a BST of n nodes by inserting records one at a time. If we are fortunate
to have them arrive in an order that results in a balanced tree (a “random” order is
likely to be good enough for this purpose), then each insertion will cost on average
(log n), for a total cost of (n log n). However, if the records are inserted in
order of increasing value, then the resulting tree will be a chain of height n. The
cost of insertion in this case will be
P
i=1
i = (n
2
).
Traversing a BST costs (n) regardless of the shape of the tree. Each node is
visited exactly once, and each child pointer is followed exactly once.
Below is an example traversal, named
printhelp
. It performs an inorder
traversal on the BST to print the node values in ascending order.
privatevoidprinthelp(BSTNode<Key,E>rt){
if(rt==null)return;
printhelp(rt.left());
printVisit(rt.element());
printhelp(rt.right());
}
While the BST is simple to implement and efficient when the tree is balanced,
the possibility of its being unbalanced is a serious liability. There are techniques
for organizing a BST to guarantee good performance. Two examples are the AVL
tree and the splay tree of Section 13.2. Other search trees are guaranteed to remain
balanced, such as the 2-3 tree of Section 10.4.
5.5
Heaps and Priority Queues
There are many situations, both in real life and in computing applications, where
we wish to choose the next “most important” from a collection of people, tasks,
or objects. For example, doctors in a hospital emergency room often choose to
see next the “most critical” patient rather than the one who arrived first. When
scheduling programs for execution in a multitasking operating system, at any given
moment there might be several programs (usually called jobs) ready to run. The
next job selected is the one with the highest priority. Priority is indicated by a
particular value associated with the job (and might change while the job remains in
the wait list).
