Java Reference
In-Depth Information
5
Binary Trees
The list representations of Chapter 4 have a fundamental limitation: Either search
or insert can be made efficient, but not both at the same time. Tree structures
permit both efficient access and update to large collections of data. Binary trees in
particular are widely used and relatively easy to implement. But binary trees are
useful for many things besides searching. Just a few examples of applications that
trees can speed up include prioritizing jobs, describing mathematical expressions
and the syntactic elements of computer programs, or organizing the information
needed to drive data compression algorithms.
This chapter begins by presenting definitions and some key properties of bi-
nary trees. Section 5.2 discusses how to process all nodes of the binary tree in an
organized manner. Section 5.3 presents various methods for implementing binary
trees and their nodes. Sections 5.4 through 5.6 present three examples of binary
trees used in specific applications: the Binary Search Tree (BST) for implementing
dictionaries, heaps for implementing priority queues, and Huffman coding trees for
text compression. The BST, heap, and Huffman coding tree each have distinctive
structural features that affect their implementation and use.
5.1
Denitions and Properties
A binary tree is made up of a finite set of elements called nodes. This set either
is empty or consists of a node called the root together with two binary trees, called
the left and right subtrees, which are disjoint from each other and from the root.
(Disjoint means that they have no nodes in common.) The roots of these subtrees
are children of the root. There is an edge from a node to each of its children, and
a node is said to be the parent of its children.
If n 1 , n 2 , ..., n k is a sequence of nodes in the tree such that n i is the parent of
n i+1 for 1 i < k, then this sequence is called a path from n 1 to n k . The length
of the path is k1. If there is a path from node R to node M, then R is an ancestor
of M, and M is a descendant of R. Thus, all nodes in the tree are descendants of the
145
 
Search WWH ::




Custom Search