Page 122 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 6: Binary Search Tree and AVL Trees

A tree shown below in Figure 6.1 is a binary search tree: Notes

Figure 6.1: A Binary Search Tree

50

30 60

25 40 70

35 65

A binary search tree is basically a binary tree, and therefore it can be traversed is inorder, preorder,

and postorder. If we traverse a binary search tree in inorder and print the identifiers contained in

the nodes of the tree, we get a sorted list of identifiers in the ascending order.
A binary search tree is an important search structure. For example, consider the problem of
searching a list. If a list is an ordered then searching becomes faster, if we use a contiguous
list and binary search, but if we need to make changes in the list like inserting new entries and
deleting old entries. Then it is much slower to use a contiguous list because insertion and deletion
in a contiguous list requires moving many of the entries every time. So we may think of using
a linked list because it permits insertions and deletions to be carried out by adjusting only few
pointers, but in a linked list there is no way to move through the list other than one node at a
time hence permitting only sequential access. Binary trees provide an excellent solution to this
problem. By making the entries of an ordered list into the nodes of a binary search tree, we fi nd
that we can search for a key in O(n log n) steps.

Creating a Binary Search Tree

We assume that every node a binary search tree is capable of holding an integer data item and
the links which can be made pointing to the root of the left and the right sub-tree respectively.
Therefore the structure of the node can be defined using the following declaration:

struct tnode
{
int data;
tnode *lchid;
tnode *rchild;
}
To create a binary search tree we use a procedure named insert which creates a new node with
the data value supplied as a parameter to it, and inserts into an already existing tree whose root
pointer is also passed as a parameter. The procedure accomplishes this by checking whether the
tree whose root pointer is passed as a parameter is empty. If it is empty then the newly created
node is inserted as a root node. If it is not empty then it copies the root pointer into a variable
temp1, it then stores value of temp1 in another variable temp2, compares the data value of the
node pointed to by temp1 with the data value supplied as a parameter, if the data value supplied
as a parameter is smaller than the data value of the node pointed to by temp1 then it copies the
left link of the node pointed by temp1 into temp1 (goes to the left), otherwise it copies the right
link of the node pointed by temp1 into temp1(goes to the right). It repeats this process till temp1
becomes nil.

LOVELY PROFESSIONAL UNIVERSITY 117