Chapter 20
Binary Search Trees
20.1 Binary Search Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
20.2 Inserting Data into a Binary Search Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
20.3 Searching a Binary Search Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
20.4 Printing a Binary Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
20.5 Deleting from a Binary Search Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
20.6 Destroying a Binary Search Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
20.7 main . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
20.8 Makefile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
20.9 Counting the Different Shapes of a Binary Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
The previous chapter explained linked lists. Each Node has precisely one link called next.
Traversing the list to find a given node means starting at the first node—usually called the
head—and visiting each node in turn. In a doubly linked list, each Node has two links (next
and previous). A doubly linked list allows for traversing forward using next and backward
using previous. Even though doubly linked lists are more convenient, they still have the
same limitations of singly linked lists. If the list is long, then finding particular nodes may
require visiting many nodes. If we want to efficiently add and remove data, a linked list is
insufficient.
Section 15.1 provides an example of quickly locating data in an array by skipping large
portions of it. This is a step in the right direction. Note, however, that the array must be
sorted before a binary search can be applied. Furthermore, the array’s size is fixed. Inserting
an element in an array can be expensive, because there may not be enough memory available.
It is necessary to allocate a new array and copying data before freeing the old array. If the
new element is inserted at the beginning, all the elements must be moved. This is inefficient.
Can a dynamic structure support the efficient searching properties of binary searching,
but still preserve the ability to quickly add and remove elements? Binary search trees are
designed to do precisely that. A binary search tree can typically discard half of the data in
a single comparison. This makes search efficient. A binary search tree is one type of binary
tree. A binary search tree is always a binary tree, but a binary tree may not necessarily
be a binary search tree. We will start exploring binary search trees and then generalize to
binary trees.
Like a linked list, a binary search tree is composed of nodes that are linked together.
The tree is a single root node similar to the head node in a linked list. Every node in a
binary tree has two links called left and right. A binary tree is different from a doubly
linked list. In a doubly linked list, if p -> next is q, then q -> previous must be p. It is
possible to reach p from q and it is also possible to reach q from p. Even though each node
has two links, they form a single chain.
The situation is fundamentally different in binary trees. Although each node has two
links, the links point to distinct nodes. This means that if q is p -> left or p -> right,
neither q -> left nor q -> right is p. It is possible to reach q from p but it is impossible
to reach p from q.
317
318 Intermediate C Programming
The following are some terms used for binary trees. If q is p -> left, then q is called
p’s left child. If r is p -> right, then r is p’s right child. We call p the parent of q and r.
We also say that q and r are siblings. If a node has no child, then it is called a leaf node.
All the nodes on the left side of p are called p’s left subtree. All the nodes on the right side
of p are called p’s right subtree. The top node is called the root of the tree, and the root
can reach every node in the tree.
Fig. 20.1 shows an example of a binary tree. The root stores the value 8. The value 4 is
stored in the left child of the root. The nodes storing 1, 4, 5, and 7 are the left subtree of
the root. The nodes storing 9, 10, 11, 12, and 15 are the right subtree of the root.
FIGURE 20.1: An example of a binary search tree.
The distance of a node from the root is the number of links between the root and the
node. For example, the distance between the node 7 and the root is 2. The height of a
binary tree is one plus the longest distance in the tree. The height of the tree above is 4. In
a full binary tree, each node has either two children or no children. The tree in Fig. 20.1 is
not full because some nodes (nodes 7, 9, and 12) have only one child. In a complete binary
tree, each node, except the nodes just above the leaf nodes, has two children. Fig. 20.1 is
complete but not full.
It is possible for a node in a complete binary tree to have only one child, and thus not
be a full binary tree. It is also possible that a full binary tree is incomplete. If a binary tree
is full and complete and its height is n (i.e., the distance between a leaf node and the root
is n − 1), then the tree has precisely 2
n
− 1 nodes and 2
n−1
leaf nodes. In a balanced binary
tree, the difference between the height of the left subtree and the height of the right subtree
is at most one. A binary tree is degenerated if each node has at most one child. In this case,
the binary tree is essentially a linked list.
We can create tree structures in which each object has three or more links. For example,
many computer games take advantage of octrees where each node has eight children. In this
case, octrees are used to partition three-dimensional space, and are thus useful for indexing
the objects in 3D worlds. This book focuses on binary trees because they are useful for a
wide array of problems.
20.1 Binary Search Tree
A binary search tree is a binary tree and satisfies the following conditions:
• Each node has two links and one data attribute. This data attribute can be a primitive
type (int, double, char, etc.) or an object.
• The data attributes store values that must be distinct.
• The data attributes must be totally ordered. If a and b are the values stored in two
different nodes, then either a < b or a > b must be true. Transitivity must be satisfied
Binary Search Trees 319
(if a < b and b < c, then a < c). For example, integers, characters, floating-point
numbers, and strings all support total ordering. Complex numbers are not totally
ordered and cannot be used as the attributes for binary search trees.
• For every node p in a tree, if p has a left child node q, then q -> value must be
smaller than p -> value. Similarly, if p has a right child node r, then r -> value
must be greater than p -> value.
Fig. 20.1 is an example of a binary search tree. Below is the header file for a binary
search tree. It shows the structure definition for a tree node, and gives function declarations
for binary search trees.
// tree . h1
#i f n d e f TREE_H2
#d ef in e TREE_H3
#in clude < stdio .h >4
typedef s t ru ct treenode5
{6
st ruc t treenode * left ;7
st ruc t treenode * right ;8
int value ;9
} TreeNode ;10
// insert a value v to a binary search tree startin g11
// with root , return the new root12
TreeNode * Tree _ insert ( Tree N ode * root , i n t v ) ;13
// search a value in a binary search tree startin g14
// with root , return the node whose value is v ,15
// or NULL if no such node exists16
TreeNode * Tree _ search ( Tree N ode * root , i n t v ) ;17
// delete the node whose value is v in a binary search18
// tree starting with root , return the root of the19
// rema ining tree , or NULL if the tree is empty20
TreeNode * Tree _ delete ( Tree N ode * root , i n t v ) ;21
// print the values stored in the binary search tree22
void Tree_pri n t ( T r eeNode * root );23
// delete every node24
void Tree_d estroy ( T r e eNode * root );25
#e ndif26
A binary search tree has similar functionality to a linked list. For example, both struc-
tures support insert, search, and delete. The differences are the internal organization and
the efficiency of these operations. Note that a linked list can be considered a special case of
a binary tree where every node uses only one link, and the other link is always NULL.
20.2 Inserting Data into a Binary Search Tree
As in the chapter on linked lists, we will present the three views of a binary search tree.
Fig. 20.2 illustrates an empty binary tree (in three ways). Remember that the starting point
of a binary tree is called root instead of head. Fig. 20.3 creates the first tree TreeNode. It
is better to create a function Tree insert than write these three statements over and over
again. (Remember, DRY code means Don’t Repeat Yourself.)
320 Intermediate C Programming
Node * root = NULL;
symbol
address
value
root 200 NULL
root
(a) (b)
(c)
FIGURE 20.2: An empty tree has one pointer called root and its value is NULL; root is
a pointer and it is not a tree node.
Node * root = NULL;
root = malloc(size(Node));
root -> left = NULL;
root -> right = NULL;
root -> value = 917;
symbol
address
value
address
value
root 200 60000 60002 917
60001 NULL
60000 NULL
Call Stack Heap Memory
(a)
(c)
root
(b)
917
FIGURE 20.3: A binary tree with only one tree node. Both left and right are NULL.
This node is called the root because it has no parent. It is also a leaf node because it has
no children.
Node * root = NULL;
root = List_insert(root, 917);
root = List_insert(root, -504);
symbol
address
value address value
root 200 60000 75002 -504
75001 NULL
75000 NULL
60002 917
60001 NULL
60000 75000
Call Stack Heap Memory
(a)
(c)
root
(b)
917
-504
FIGURE 20.4: A binary tree with two nodes. The node with value 917 remains the root.
It is no longer a leaf node because it has one child. The node with value −504 is a leaf node
because it has no children.
Binary Search Trees 321
Node * root = NULL;
root = List_insert(root, 917);
root = List_insert(root, -504);
root = List_insert(root, 1226);
symbol
address
value
address
value
root 200 60000 86002 1226
86001
NULL
86000
NULL
75002 -504
75001
NULL
75000
NULL
60002 917
60001 86000
60000 75000
Call Stack Heap Memory
(a)
(c)
(b)
root
917
-504
1226
FIGURE 20.5: A binary tree with three nodes.
Node * root = NULL;
root = List_insert(root, 917);
root = List_insert(root, -504);
root = List_insert(root, 1226);
root = List_insert(root, 73);
root = List_insert(root, 1085);
(a)
(d)
(b)
root
917
-504
1226
73
1085
root
917
-504
73
1226
1085
FIGURE 20.6: A binary tree with five tree nodes. A new view (d) simplifies the repre-
sentation of the tree.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.