Tree search, insertion/deletions

Why Use Binary Trees?

• Slow Insertion in an Ordered Array
• Slow Searching in a Linked List

Trees to the rescue

It would be nice if there were a data structure with the quick insertion and deletion of a linked list, and also the quick searching of an ordered array. Trees provide both these characteristics and are also one of the most interesting data structures.

Binary Search Tree (BST)

BST are a type of Binary Trees with a special organization of data.

Binary search tree is a binary tree that is either empty or in which each node contains a data value that satisfies the following:

a) Every element has a unique key.

b) All data values in the left subtree are smaller than the data value in the root.

c) All the data value in the root is smaller than all values in its right subtree.

d) The left and right subtrees are also binary search trees.

Applications of BST

• BST can be used to sort data either in ascending or descending order.
• BST can be used to search techniques.

PseudoCode to create BST:

1. Define a node

struct Tree {

int data;

struct Tree *left;

struct Tree *right;

};

struct Tree *Root = NULL, *temp, *newnode;

newnode = new Tree;

newnode→data = m;

newnode→left = NULL;

newnode → right = NULL;

2. If Root == NULL

then Root = newnode

Else

set flag = 1

set temp = Root

while flag != 0 Repeat

if newnode→data <= temp→data then

if temp→left == NULL then

temp → left = newnode

set flag = 0

endif

else

temp = temp→left

endelse

endif

Algorithm to insert a node in BST;

1. create a node

2. take input data value and assign the following:

newnode→data = m

newnode→left = NULL

newnode→right = NULL

3. If root node is NULL then

root = new node

else

Compare the new node data with the data in the root node (current node) located by the node pointer

if new nodes are smaller than current node data, then insert a new node in the left side of the current pointer

else insert a new node to the right side of the current node.

4. For next data, repeat step 1 to 3.

else

if temp→right == NULL then

temp→right = new node

set flag = 0

endif

else

temp = temp→right

endelse

endelse

endwhile

endelse

Finding a Node

C Code:

Node* find(int key) //find node with given key

{

//(assumes non-empty tree)

Node* pCurrent = pRoot;

//start at root

while(pCurrent->iData != key) //while no match,

{

if(key < pCurrent->iData) //go left?

pCurrent = pCurrent->pLeftChild;

else //or go right?

pCurrent = pCurrent->pRightChild;

if(pCurrent == NULL) //if no child,

return NULL; //didn’t find it

}

return pCurrent; //found it

} //end find()

Removing a node

Remove operation on binary search tree is more complicated, than add and search. Basically, in can be divided into two stages:

• search for a node to remove;
• if the node is found, run remove algorithm.

Remove from BST algorithm in detail

Now, let's see more detailed description of a remove algorithm. The first stage is identical to an algorithm for lookup except we should track the parent of the current node. The second part is more tricky. There are three cases, which are described below.

1. Node to be removed has no children.

This case is quite simple. Algorithm sets the corresponding link of the parent to NULL and disposes of the node.

Example. Remove -4 from a BST.

2.Node to be removed has one child.

It this case, a node is cut from the tree and algorithm links single child (with its subtree) directly to the parent of the removed node.

Example. Remove 18 from a BST.

3.Node to be removed has two children.

This is the most complex case. To solve it, let us see one useful BST property first. We are going to use the idea, that the same set of values may be represented as different binary-search trees. For example those BSTs:

contain the same values {5, 19, 21, 25}. To transform the first tree into the second one, we can do following:

• choose a minimum element from the right subtree (19 in the example);
• replace 5 by 19;
• hang 5 as a left child.

The same approach can be utilized to remove a node, which has two children:

• find a minimum value in the right subtree;
• replace the value of the node to be removed with found minimum. Now, right subtree contains a duplicate!
• apply remove to the right subtree to remove a duplicate.

Notice, that the node with minimum value has no left child and, therefore, it's removal may result in first or second cases only.

Example. Remove 12 from a BST.

Find minimum element in the right subtree of the node to be removed. In the current example, it is 19.

Replace 12 with 19. Notice, that only values are replaced, not nodes. Now we have two nodes with the same value.

Remove 19 from the left subtree.

PseudoCode for Removal

remove(k):

if ( k not in BST ) {

return;

}

if ( k has no subtrees ) {

unlink k from k's parent;

return;

}

if ( k has 1 tree ) {

make k's parent point to k's subtree;

return;

}

/* k has 2 subtrees */

(1) find the successor of k:

go right once

go left all the way down

(2) Replace k with k's successor;

(3) Make the successor's parent point to the successor's right subtree;

References:

1. http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/BST-delete2.html
2. http://www.algolist.net/Data_structures/Binary_search_tree/Removal
3. G. Brassard and P. Bratley, “Fundamentals of Algorithms”
4. R. L. Kruse, B. P. Leung, C. L. Tondo, “Data Structure and Program designin C”