Previous Section
 < Free Open Study > 
Next Section


8.1 Trees

A binary search tree is a structure with two properties: a shape property and a property that relates the keys of the elements in the structure. We look first at the shape property.

Binary tree A structure with a unique starting node (the root), in which each node is capable of having two child nodes, and in which a unique path exists from the root to every other node

Root The top node of a tree structure; a node with no parent

Leaf node A tree node that has no children

Each node in a singly linked list may point to one other node: the one that follows it. Thus a singly linked list is a linear structure; each node in the list (except the last) has a unique successor. In contrast, a binary tree is a structure in which each node is capable of having two successor nodes, called children. Each of the children, being nodes in the binary tree, can also have two child nodes, and these children can also have two children, and so on, giving the tree its branching structure. The "beginning" of the tree is a unique starting node called the root.

Figure 8.1 depicts a binary tree. The root node of this binary tree contains the value A. Each node in the tree may have 0, 1, or 2 children. The node to the left of a node, if it exists, is called its left child. For instance, the left child of the root node contains the value B. The node to the right of a node, if it exists, is its right child. The right child of the root node contains the value C. The root node is the parent of the nodes containing B and C. (Earlier textbooks used the terms left son, right son, and father to describe these relationships.) If a node in the tree has no children, it is called a leaf. For instance, the nodes containing G, H, E, I, and J are leaf nodes.

Click To expand
Figure 8.1: A binary tree

In addition to specifying that a node may have as many as two children, the definition of a binary tree states that a unique path exists from the root to every other node. Thus every node (except the root) has a unique parent. In the structure pictured at the top of the next page, the nodes have the correct number of children, but the unique path rule is violated: Two paths from the root to the node containing D exist. Therefore this structure is not a tree at all, let alone a binary tree.

Click To expand

In Figure 8.1, each of the root node's children is itself the root of a smaller binary tree, or subtree. The root node's left child, containing B, is the root of its left subtree, and the right child, containing C, is the root of its right subtree. In fact, any node in the tree can be considered the root node of a subtree. The subtree whose root node has the value B also includes the nodes with values D, G, H, and E. These nodes are the descendants of the node containing B. The descendants of the node containing C are the nodes with the values F, I, and J. A node is the ancestor of another node if it is the parent of the node, or the parent of some other ancestor of that node. (Yes, this is a recursive definition.) In Figure 8.1, the ancestors of the node with the value G are the nodes containing D, B, and A. Obviously, the root of the tree is the ancestor of every other node in the tree.

The level of a node refers to its distance from the root. If we designate the level of the root as 0 (zero), the nodes containing B and C are Level 1 nodes; the nodes containing D, E, and F are Level 2 nodes; and the nodes containing G, H, I, and J are Level 3 nodes.

Level The distance of a node from the root; the root is level 0

Height The maximum level

The maximum level in a tree determines its height. The maximum number of nodes at any level N is 2N. Often, however, levels do not contain the maximum number of nodes. For instance, in Figure 8.1, Level 2 could contain four nodes, but because the node containing C in Level 1 has only one child, Level 2 contains three nodes. Level 3, which could contain eight nodes, has only four. We could construct many differently shaped binary trees out of the ten nodes in this tree. Figure 8.2 illustrates a few variations. You can readily see that the maximum number of levels in a binary tree with N nodes is N. What is the minimum number of levels? If we fill the tree by giving every node in each level two children until we run out of nodes, the tree has log2N + 1 levels (Figure 8.2a). Demonstrate this fact to yourself by drawing "full" trees with 8 [log2(8) = 3] and 16 [log2(16) = 4] nodes. What if there are 7, 12, or 18 nodes?

Click To expand
Figure 8.2: Binary trees with ten nodes

The height of a tree is the critical factor in determining how efficiently we can search for elements. Consider the maximum-height tree in Figure 8.2(c). If we begin searching at the root node and follow the pointers from one node to the next, accessing the node with the value J (the farthest from the root) is an O(N) operation-no better than searching a linear list! On the other hand, given the minimum-height tree depicted in Figure 8.2(a), to access the node containing J, we have to look at only three other nodes-the ones containing E, A, and G-before we find J. Thus, if the tree is of minimum height, its structure supports O(log2N) access to any element.

The arrangement of the values in the tree pictured in Figure 8.2(a) does not actually lend itself to quick searching. Suppose we want to find the value G. We begin searching at the root of the tree. This node contains E, not G, so we need to keep searching. But which of its children should we examine next, the right or the left? The nodes are not organized in any special order, so we have to check both subtrees. We could search the tree, level by level, until we come across the desired value. That is an O(N) search operation, which is no better than searching a linked list!

To support O(log2N) searching, we add a special property based on the relationship among the keys of the items in the tree. We put all the nodes with values smaller than the value in the root into its left subtree, and all the nodes with values larger than the value in the root into its right subtree. Figure 8.3 shows the nodes from Figure 8.2(a) rearranged to satisfy this property. The root node, which contains E, accesses two subtrees. The left subtree contains all values smaller than E and the right subtree contains all values larger than E.

Click To expand
Figure 8.3: A binary search tree

To search for the value G, we look first in the root node. G is larger than E, so we know that G must be in the root node's right subtree. The right child of the root node contains H. Now what? Do we go to the right or to the left? This subtree is also arranged according to the binary search property: The nodes with smaller values are found to the left and the nodes with larger values are found to the right. The value of this node, H, is greater than G, so we search to its left. The left child of this node contains the value F, which is smaller than G, so we reapply the rule and move to the right. The node to the right contains G; we have found the node we were seeking.

Binary search tree A binary tree in which the key value in any node is greater than the key value in its left child and any of its children (the nodes in the left subtree) and less than the key value in its right child and any of its children (the nodes in the right subtree)

A binary tree with this special property is called a binary search tree. Like any binary tree, it achieves its branching structure by allowing each node to have a maximum of two child nodes. It achieves its easy-to-search structure by maintaining the binary search property: The left child of any node (if one exists) is the root of the subtree that contains only values smaller than the node. The right child of any node (if one exists) is the root of the subtree that contains only values that are larger than the node.

Four comparisons instead of ten doesn't sound like such a big deal, but as the number of elements in the structure increases, the difference becomes more impressive. In the worst case-searching for the last node in a linear linked list-you must look at every node in the list; on the average, you must search half the list. If the list contains 1,000 nodes, you must make 1,000 comparisons to find the last node! If the 1,000 nodes were arranged in a binary search tree of minimum height, you would never make more than 10 (log2(1,000) < 10) comparisons, no matter which node you were seeking!

The definitions that we have given for binary trees can be extended to trees whose nodes can have any number of child nodes. A tree is a structure with a unique starting node (the root), in which each node is capable of having many child nodes, and in which a unique path exists from the root to every other node. In this book we restrict ourselves to binary search trees and heaps. We cover binary search trees in great depth in this chapter and cover heaps in Chapter 9.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)