Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 10] BINARY TREES 243

Searching and Inserting in a Binary Search Tree

A search and insertion algorithm in a binary search treeTappears in Fig. 10-9.

Fig. 10-9

EXAMPLE 10.6 Consider the binary search treeTin Fig. 10-8(a). Suppose ITEM=20 is given, and we want
to find or insert ITEM intoT. Simulating Algorithm 10-1, we obtain the following steps:

(1) Compare ITEM=20 with rootR=38. Since 20<38, proceed to the left child of 38, which is 14.

(2) Compare ITEM=20 with 14. Since 20>14, proceed to the right child of 14, which is 23.

(3) Compare ITEM=20 with 23. Since 20<23, proceed to the left child of 23, which is 18.

(4) Compare ITEM=20 with 18. Since 20>18 and 18 has no right child, insert 20 as the right child of 18.

Figure 10-11(b) shows the new tree with ITEM=20 inserted. The path down the tree during the algorithm has
been ringed.

Deleting in a Binary Search Tree

An algorithm which deletes a given ITEM from a binary search treeT appears in Fig. 10-10. It uses
Algorithm 10.1 in Fig. 10-9 to find the location of ITEM inT.

Remark:Observe that case (iii) in Step 2(c) is more complicated than the first two cases. The inorder successor
S(N)ofNis found as follows. From the nodeN, move right to the right child ofN, and then successively move
left until meeting a nodeMwith no left child. The nodeMis the inorder successorS(N)ofN.

EXAMPLE 10.7Consider the binary treeTin Fig. 10-8(b). Suppose we want to delete ITEM=14 fromT.

First find the nodeNsuch thatN=14. NoteN=14 has two children. Moving right and then left, we find the

inorder successorS(N)=18 ofN. We deleteS(N)=18 by replacing it by its only child 20, then we replace

N=14 byS(N)=18. This yields the tree in Fig. 10-8(c).

Complexityofthe Binary Search Tree Algorithms
LetTbe a binary tree withnnodes and depthd, and letf(n) denote the running time of either of the above
algorithms. Algorithm 10.1 tells us to proceed from the rootRdown through the treeTuntil finding ITEM inT
or inserting ITEM as a terminal node. Algorithm 10.2 tells us to proceed from the rootRdown through the tree
Tto find ITEM and then to continue down the treeTto find the inorder successor of ITEM. In either case, the