The Algorithm Design Manual Second Edition

3.4.1

Implementing Binary Search Trees

Binary tree nodes have left and right pointer fields, an (optional) parent pointer,

and a data field. These relationships are shown in Figure

3.3;

a type declaration

for the tree structure is given below:

---

78

3 .

D A T A S T R U C T U R E S

left

right

parent

Figure 3.3: Relationships in a binary search tree (left). Finding the minimum (center) and

maximum (right) elements in a binary search tree

typedef struct tree {

item_type item;

/* data item */

struct tree *parent;

/* pointer to parent */

struct tree *left;

/* pointer to left child */

struct tree *right;

/* pointer to right child */

} tree;

The basic operations supported by binary trees are searching, traversal, inser-

tion, and deletion.

Searching in a Tree

at the root. Unless it contains the query key x, proceed either left or right depending

upon whether x occurs before or after the root key. This algorithm works because

both the left and right subtrees of a binary search tree are themselves binary search

trees. This recursive structure yields the recursive search algorithm below:

tree *search_tree(tree *l, item_type x)

{

if (l == NULL) return(NULL);

if (l->item == x) return(l);

if (x < l->item)

return( search_tree(l->left, x) );

else

return( search_tree(l->right, x) );

}

The binary search tree labeling uniquely identifies where each key is located. Start

---

3 . 4

B I N A R Y S E A R C H T R E E S

79

This search algorithm runs in O(h) time, where h denotes the height of the

tree.