Binary search Tree(BST)

Binary Search Trees ( BST ) : Binary Search Trees ( BST ) V. Vasantha Senior Lecturer Dept., of IT National Engg., College, Kovilpatti Tamil Nadu, India

A Taxonomy of Trees : 6/10/2010 CS1151 Data Structures VV 2 A Taxonomy of Trees General Trees – any number of children / node Binary Trees – max 2 children / node Heaps – parent < (>) children Binary Search Trees

Binary Search Tree ( BST ) : 6/10/2010 CS1151 Data Structures VV 3 Binary Search Tree ( BST ) Binary search tree Every element has a unique key. The keys in a nonempty left subtree (right subtree) are smaller (larger) than the key in the root of subtree. The left and right subtrees are also binary search trees.

BST – Contd., : 6/10/2010 CS1151 Data Structures VV 4 BST – Contd., It’s binary tree in which for every node X, in the tree, the values of all the keys in its left sub tree are smaller than the key value in X and the values of all the keys in its right sub tree are larger than the key value in X.

BST – Contd., : 6/10/2010 CS1151 Data Structures VV 5 Binary Search Trees (BST) are a type of Binary Trees with a special organization of data. This data organization leads to O(log n) complexity for searches, insertions and deletions in certain types of the BST (balanced trees). O(h) in general BST – Contd.,

BST Example : 6/10/2010 CS1151 Data Structures VV 6 BST Example Binary Search Tree Not a Binary Search Tree

Example – Contd., : 6/10/2010 CS1151 Data Structures VV 7 Example – Contd.,

Operations on BST ADT : 6/10/2010 CS1151 Data Structures VV 8 Operations on BST ADT Create a BST Insert an element Remove an element Find an element Clear (remove all elements) Display all elements in a sorted order

Node Structure : 6/10/2010 CS1151 Data Structures VV 9 Node Structure Struct TreeNode { int Data; Tree Left Tree Right; };

bst.h : 6/10/2010 CS1151 Data Structures VV 10 bst.h # ifndef _BST_H struct TreeNode; typedef struct TreeNode *Pos; typedef struct TreeNode *Tree; Tree MakeEmpty(Tree T); Pos Find(int x, Tree T);

bst.h – Contd., : 6/10/2010 CS1151 Data Structures VV 11 bst.h – Contd., Pos FindMin(Tree T); Pos FindMax(Tree T); Tree Insert(int x, Tree T); Tree Deletion(int x, Tree T); void Inorder(Tree T); void Preorder(Tree T); void Postorder(Tree T); #endif

Slide 12 : 6/10/2010 CS1151 Data Structures VV 12 if the tree is empty return NULL else if the target is lesser than the item in the node return the result of searching the left subtree else if target is greater than the item in the node return the result of searching the right subtree else (* the item in the node equals the target *) return the node address Search in BST - Pseudocode

Search Code : 6/10/2010 CS1151 Data Structures VV 13 Search Code Pos Find(int x, Tree T) { if ( T == NULL ) return NULL; else if ( x < T->Data ) return Find(x, T->Left); else if ( x > T->Data ) return Find(x, T->Right); else return T; }

FindMin Pseudo code : 6/10/2010 CS1151 Data Structures VV 14 FindMin Pseudo code Returns the smallest element in the tree. Start at the root and go left as long as there is left child. The stopping point is the smallest element.

FindMin Code : 6/10/2010 CS1151 Data Structures VV 15 FindMin Code Pos FindMin(Tree T) { if ( T == NULL ) return NULL; else if ( T->Left != NULL ) return FindMIn(T->Left); else return T; }

Insert Algorithm : 6/10/2010 CS1151 Data Structures VV 16 Insert Algorithm If value we want to insert < key of current node, we have to go to the left subtree Otherwise we have to go to the right subtree If the current node is empty (not existing) create a node with the value we are inserting and place it as root.

Slide 17 : 6/10/2010 CS1151 Data Structures VV 17 Case 1: The Tree is Empty Set the root to a new node containing the item Case 2: The Tree is Not Empty Call a recursive method to insert the item Insertion – Contd.,

Insertion Example : 6/10/2010 CS1151 Data Structures VV 18 Insertion Example 9 7 5 4 6 8 10 10 10 > 7 10 > 9

Slide 19 : 6/10/2010 CS1151 Data Structures VV 19 if tree is empty create a root node with the new key else compare key with the top node if key < node key compare key with the left subtree: if the subtree is empty create a leaf node else add key to the left subtree if key > node key compare key with the right subtree: if subtree is empty create a leaf node else add key in right subtree Insertion into BST - Pseudo code

Insert Code : 6/10/2010 CS1151 Data Structures VV 20 Insert Code Tree Insert(int x, Tree T) { if ( T == NULL ) { T = malloc(sizeof( struct TreeNode ) ); if ( T == NULL ) { printf(“ Tree Not Created\n”); return T; } else

Insert Code – Contd., : 6/10/2010 CS1151 Data Structures VV 21 Insert Code – Contd., { T->Data = x; T->Left = T->Right = NULL; } } else if ( x < T->Data ) T->Left = Insert ( x, T->Left ); else if ( x > T->Data ) T->Right = Insert ( x, T->Right); return T; }

Delete Operation : 6/10/2010 CS1151 Data Structures VV 22 Delete Operation How do we delete a node form BST? Similar to the insert function, after deletion of a node, the property of the BST must be maintained.

Deletion – Contd., : 6/10/2010 CS1151 Data Structures VV 23 Deletion – Contd., There are 3 possible cases Node to be deleted has no children ? We just delete the node. Node to be deleted has only one child ? Replace the node with its child and make the parent of the deleted node to be a parent of the child of the deleted node Node to be deleted has two children ???

Slide 24 : 6/10/2010 CS1151 Data Structures VV 24 if the tree is empty return false Attempt to locate the node containing the target using the recursive deletion method if the target is found, so remove its node: Case 1: if the node has 2 empty subtrees replace the link in the parent with null Case 2: if the node has a left and a right subtree - replace the node's value with the max value in the left subtree - delete the max node in the left subtree Deletion in BST - Pseudo code

Slide 25 : 6/10/2010 CS1151 Data Structures VV 25 Case 3: if the node has no left child - link the parent of the node to the right (non-empty) subtree Case 4: if the node has no right child - link the parent of the target to the left (non-empty) subtree Deletion Pseudocode – Contd.,

Slide 26 : 6/10/2010 CS1151 Data Structures VV 26 9 7 5 6 4 8 10 9 7 5 6 8 10 Case 1: removing a node with 2 EMPTY SUBTREES parent cursor Deletion Example Removing 4 replace the link in the parent with null

Slide 27 : 6/10/2010 CS1151 Data Structures VV 27 Case 2: removing a node with 2 SUBTREES 9 7 5 6 8 10 9 6 5 8 10 cursor cursor - replace the node's value with the max value in the left subtree - delete the max node in the left subtree 4 4 Removing 7 Deletion Example – Contd., What other element can be used as replacement?

Binary Search Tree : 6/10/2010 CS1151 Data Structures VV 28 Binary Search Tree Node to be deleted has two children

Alternate Way : 6/10/2010 CS1151 Data Structures VV 29 Alternate Way Node to be deleted has two children Find minimum value of right subtree Replace the value of the node to be deleted by the minimum value. Delete the minimum node.

Binary Search Tree : 6/10/2010 CS1151 Data Structures VV 30 Binary Search Tree

Slide 31 : 6/10/2010 CS1151 Data Structures VV 31 9 7 5 6 8 10 9 7 5 6 8 10 cursor cursor parent parent the node has no left child: link the parent of the node to the right (non-empty) subtree Case 3: removing a node with 1 EMPTY SUBTREE Deletion Example – Contd.,

Slide 32 : 6/10/2010 CS1151 Data Structures VV 32 9 7 5 8 10 9 7 5 8 10 cursor cursor parent parent the node has no right child: link the parent of the node to the left (non-empty) subtree Case 4: removing a node with 1 EMPTY SUBTREE Removing 5 4 4 Deletion Example – Contd.,

Deletion Code : 6/10/2010 CS1151 Data Structures VV 33 Deletion Code On Blackboard

Applications for BST : 6/10/2010 CS1151 Data Structures VV 34 Applications for BST Sorting with binary search trees Input: unsorted array Output: sorted array Algorithm ? Running time ?

Inorder Traversal Pseudo code : 6/10/2010 CS1151 Data Structures VV 35 Inorder Traversal Pseudo code For a non empty BST, Process the left sub tree. Process the root. Process the right sub tree.

Inorder Traversal Code : 6/10/2010 CS1151 Data Structures VV 36 Inorder Traversal Code void Inorder (Tree T) { if ( T != NULL ) { Inorder (T->Left); printf(“%d\t”, T->Data); Inorder (T->Right); } }

Slide 37 : 6/10/2010 CS1151 Data Structures VV 37 Queries ??? Thank U !!!