Data Structures and Agorithm: DS 10 Binary Search Tree.pptx

Data Structures and Agorithm: DS 10 Binary Search Tree.pptx

1. International Islamic University H-10, Islamabad, Pakistan Data Structure Lecture No. 10, 11, 12, 13 Binary Search Tree Engr . Rashid Farid Chishti http://youtube.com/rfchishti http://sites.google.com/site/chishti Video Lecture No. 10 Video Lecture No. 11 Video Lecture No. 12 Video Lecture No. 13

2. A binary tree is a finite set of elements, that is either empty or is partitioned into three disjoint subsets. The first subset contains a single element called the root of the tree. The other two subsets are themselves binary trees called the left and right subtrees . Each element of a binary tree is called a node of the tree . Binary Tree A B D H C E F G I Left subtree r oot Right subtree

3. Structures that are not trees . Not a Tree A B D H C E F G I A B D H C E F G I A B D H C E F G I

4. Binary Tree: Terminology A B D H C E F G I parent Left descendant Right descendant Leaf nodes Leaf nodes

5. If every non-leaf node in a binary tree has non-empty left and right subtrees, the tree is termed a strictly binary tree . Level of a Binary Tree Node R oot has level 0, Level of any other node is one more than the level its parent (father). The depth of a binary tree is the maximum level of any leaf in the tree. Strictly Binary Tree A B D H C E F G I J K Level 0 Level 1 Level 2 Level 3 r oot

6. A complete binary tree of depth d is the strictly binary all of whose leaves are at level d . At level k , there are 2 k leaf nodes . Total number of nodes in the tree of depth d: 2 + 2 1 + 2 2 + ………. + 2 d = ∑ 2 i = 2 d+1 – 1 In a complete binary tree there are 2 d leaf nodes and (2 d - 1) non-leaf (inner) nodes. Complete Binary Tree A B Level 0: 2 nodes H D I E J K C L F M G N O Level 1: 2 1 nodes Level 2: 2 2 nodes Level 3: 2 3 nodes i =0 d

7. If the tree is built out of ‘n’ nodes then n = 2 d +1 – 1 n + 1 = 2 d +1 log 2 ( n + 1) = log 2 ( 2) d +1 because log 2 ( 2 ) = 1 or log 2 (n+1) = d +1 or d = log 2 (n+1) – 1 I.e., the depth of the complete binary tree built using ‘n’ nodes will be log 2 (n+1) – 1. For example, for n=1,000,000, log 2 (1000001) is less than 20; the tree would be 20 levels deep. The significance of this shallowness will become evident later. Complete Binary Tree

8. Binary Search Tree Construction Root 14 15 4 9 7 18 3 5 16 20 17

9. Searching Number 16 Searching in Binary Search Tree Root 14 15 4 9 7 18 3 5 16 20 17

10. Return the address of the smallest element in the tree Start at the root Go left as long as there is a left child Tree_Node * Find_Min ( Tree_Node *node) { if (node == NULL) return NULL; if (node- >left == NULL) return node; return Find_Min (node- >left); } Searching in Binary Search Tree: Find_Min () Root 14 15 4 9 7 18 3 5 16 20 17

11. Return the address of the largest element in the tree Start at the root Go right as long as there is a right child Tree_Node * Find_Max ( Tree_Node *node ) { if (node == NULL) return NULL; if (node- >right == NULL) return node; return Find_Max (node- >right); } Searching in Binary Search Tree: Find_Max () Root 14 15 4 9 7 18 3 5 16 20 17

12. Pre Order Traversal Show the Current Tree Node Traverse the left subtree in Pre Order Traverse the right subtree in Pre Order Result: 14 4 3 9 7 5 15 18 16 17 20 Traversing a Binary Search Tree Root 14 15 4 9 7 18 3 5 16 20 17

13. In Order Traversal Traverse the left subtree in In Order . Show the Current Tree Node Traverse the right subtree in In Order . can be used as a sorting algorithm . Result : 3 4 5 7 9 14 15 16 17 18 20 Traversing a Binary Search Tree Root 14 15 4 9 7 18 3 5 16 20 17

14. Post Order Traversal Traverse the left subtree in Post Order . Traverse the right subtree in Post Order . Show the Current Tree Node Result : 3 5 7 9 4 17 16 20 18 15 14 Traversing a Binary Search Tree Root 14 15 4 9 7 18 3 5 16 20 17

15. Level Order Traversal It uses a queue when traversing Start from root node Show the Current Tree Node If left child is present, Add it in queue If right child is present, Add it in queue While Queue is not empty go to step 2 As a result, it traverses the tree, level by level Result : 14 4 15 3 9 18 7 16 20 5 17 Traversing a Binary Search Tree Root 14 15 4 9 7 18 3 5 16 20 17

16. It is common with many data structures, the hardest operation is deletion. Once we have found the node to be deleted, we need to consider several possibilities. If the node is a leaf , it can be deleted immediately. Deleting a Leaf Node in BST Root 14 15 4 9 18 3 Root 14 15 4 9 18 Video Lecture

17. Deleting a Leaf Node in BST Root 14 15 4 9 18 3 Root 14 15 4 9 3

18. If the node has one child, the node can be deleted after replacing this node with its child node. Deleting a node with one child in BST Root 14 15 4 3 8 6 7 9 Root 14 15 4 3 8 6 7 9 Bypass link Root 14 15 4 3 8 6 7 Bypass link node to be deleted

19. Deleting a node with one child in BST Root 14 15 4 3 8 6 7 5 Root 14 15 4 3 8 6 5 7 Bypass link Root 14 15 4 3 8 6 7 Bypass link node to be deleted

20. When the node to be deleted has both left and right subtrees. Deleting a node with two children Replace the data of this node with the smallest data of the right subtree And then recursively delete that smallest node . Root 10 11 5 6 1 Root 8 9 Root 10 11 3 1 Root 8 9 5 6 node to be deleted Smallest node in right sub tree copy 7 7

21. Deleting a node in BST Root 6 8 2 5 1 4 Root copy 3 Root 6 8 3 5 1 3 4 Root Root 6 8 3 5 1 4 Root Smallest node in right sub tree node to be deleted Delete this node

22. #include < iostream > using namespace std ; typedef int Type; struct Tree_Node { Tree_Node * left ; Type data ; Tree_Node * right ; }; typedef Tree_Node * QType ; struct Node{ QType data ; Node *next ; }; 22 Example 1: Implementing of Binary Search Tree class Queue{ private : Node *front, *rear ; public : Queue( ) ; bool Is_Empty (){ return front == NULL; } void Put ( QType Data ) ; QType Get( ) ; ~ Queue( ) ; }; Queue :: Queue( ){ front = rear = NULL ; } 1 2

23. void Queue :: Put ( QType Data ){ Node * newNode ; newNode = new Node ; if ( newNode == NULL ) cout << "\ nQueue is full" ; newNode -> data = Data ; newNode -> next = NULL ; if ( front == NULL ){ rear = front = newNode ; return ; } rear -> next = newNode ; rear = rear -> next ; } 23 Example 1: Implementing of Binary Search Tree QType Queue :: Get( ){ if ( front == NULL ){ cout << "Queue is empty" ; exit(-1); } Node *current; QType Data ; Data = front -> data ; current = front ; front = front -> next ; delete current ; return Data ; } Queue :: ~Queue( ){ if ( front == NULL ) return ; Node *current ; while ( front != NULL ){ current = front ; front = front -> next ; delete current ; } } 3 4

24. class Binary_Tree { private : Tree_Node * root; void Insert ( Tree_Node * , Type _data ); Tree_Node * Remove ( Tree_Node * , Type _data ); void Pre_Order ( Tree_Node * ); void In_Order ( Tree_Node * ); void Post_Order ( Tree_Node * ); void Level_Order ( Tree_Node * node); bool Search (Type key , Tree_Node * ); Tree_Node * Find_Min ( Tree_Node *); Tree_Node * Find_Max ( Tree_Node *); public : Binary_Tree (); void Insert (Type _data); void Remove (Type _data); void Pre_Order ( ); void In_Order ( ); 24 Example 1: Implementing of Binary Search Tree void Post_Order ( ); void Level_Order ( ); bool Search (Type _data); void Find_Min ( ); void Find_Max ( ); }; Binary_Tree :: Binary_Tree (){ root = NULL; } void Binary_Tree :: Insert(Type _data){ Insert(root, _data); } void Binary_Tree :: Insert( Tree_Node *node, Type _data) { // if tree is empty if (root == NULL){ root = new Tree_Node ; root->data = _data; root->left = NULL; root->right = NULL; } 5 6

25. else if (_data >= node->data ) { // if right subtree is present if (node- >right != NULL) Insert(node- >right, _data); // create new node else { node- >right = new Tree_Node ; node- >right->data = _data; node- >right->left = NULL; node- >right->right = NULL; } } else { // if left subtree is present if (node- >left != NULL) Insert(node- >left, _data); // create new node else { node- >left = new Tree_Node ; node- >left->data = _data ; 25 Example 1: Implementing of Binary Search Tree node- >left->left = NULL; node->left->right = NULL; } } } void Binary_Tree :: Remove(Type _data){ Remove(root , _data); } Tree_Node * Binary_Tree :: Remove( Tree_Node *node, Type x){ if ( node == NULL ) return NULL; // Item not found; do nothing if ( x < node->data ) node- >left = Remove(node-> left,x ); else if ( x > node->data ) node- >right = Remove(node->right, x ); 7 8

26. else { // if Node has no child if (node->left==NULL && node- >right==NULL){ delete node; return NULL; } // if Node has one right child else if ( node->left == NULL && node- >right != NULL){ Tree_Node * oldNode = node; node = node ->right; delete oldNode ; return node; } // if Node has one left child else if ( node->right == NULL && node- >left != NULL){ Tree_Node * oldNode = node; node = node ->left ; 26 Example 1: Implementing of Binary Search Tree delete oldNode ; return node; } else { // if node has two children // Replace the data of this node // with the smallest data of // the right subtree node->data = Find_Min( node->right )->data; // recursively delete smallest node node->right = Remove( node->right, node->data); } } return node; } void Binary_Tree :: Pre_Order ( ){ Pre_Order (root ); } 9 10

27. bool Binary_Tree :: Search(Type _data){ return Search(_ data,root ); } bool Binary_Tree :: Search(Type key , Tree_Node * node){ bool found = false ; // node is not present if (node == NULL) return false ; // if node with same data is found if ( key == node->data) return true ; else if ( key > node->data ) found = Search( key, node->right ); else found = Search( key, node->left); return found; } 27 Example 1: Implementing of Binary Search Tree void Binary_Tree :: Pre_Order ( Tree_Node *node){ if (node != NULL){ cout << node->data << " " ; Pre_Order (node- >left); Pre_Order (node- >right); } } void Binary_Tree :: In_Order ( ){ In_Order (root ); } void Binary_Tree :: In_Order ( Tree_Node *node){ if (node != NULL){ In_Order (node- >left); cout << node->data << " " ; In_Order (node- >right); } } 11 12

28. void Binary_Tree :: Post_Order ( ){ Post_Order (root ); } void Binary_Tree :: Post_Order ( Tree_Node *node){ if (node != NULL){ Post_Order (node- >left); Post_Order (node- >right); cout << node->data << " " ; } } void Binary_Tree :: Level_Order ( Tree_Node * node){ Queue Q; if ( node == NULL ) return ; Q.Put (node); while ( ! Q.Is_Empty () ){ node = Q.Get (); cout << node->data << " " ; 28 Example 1: Implementing of Binary Search Tree if (node- >left != NULL ) Q.Put ( node->left); if (node->right != NULL ) Q.Put ( node->right); } cout << endl ; } void Binary_Tree :: Level_Order (){ Level_Order (root ); } void Binary_Tree :: Find_Min ( ){ Tree_Node * node = Find_Min (root); if (node != NULL) cout << "Minimum Number in the tree is: " << node->data << endl ; } Tree_Node * Binary_Tree :: Find_Min ( Tree_Node *n ){ if (n == NULL) return NULL ; 13 14

29. if (n- >left == NULL) return n; return Find_Min (n->left); } void Binary_Tree :: Find_Max ( ){ Tree_Node * n = Find_Max (root); if ( n != NULL) cout << "Maximum Number in the tree is: " << n->data << endl ; } Tree_Node * Binary_Tree :: Find_Max ( Tree_Node *node){ if (node == NULL) return NULL; if (node- >right == NULL) return node; return Find_Max (node->right); } 29 Example 1: Implementing of Binary Search Tree int main(){ Binary_Tree tree; int s; int Numbers [] = { 14,15,4,9,7,18,3,5,16,20,17}; // int Numbers [] = {10,3,11,6,1,8,5,9,7}; int size = sizeof (Numbers) / sizeof ( int ); for ( int i = 0 ; i<size ; i++){ tree.Insert (Numbers[ i ]); } cout << " -: Pre_Order Traversal :-" << endl ; tree.Pre_Order (); cout << "\n\n -: In_Order Traversal :-" << endl ; tree.In_Order (); cout << "\ n\n -: Post_Order Traversal :-\n" ; tree.Post_Order (); 15 16

30. cout << "\n\n -: Level_Order Traversal :-\n" ; tree.Level_Order (); cout << endl ; tree.Find_Max (); tree.Find_Min (); cout << "Enter a Number to Search: " ; cin >> s; if ( tree.Search (s)) cout << "found " << s << endl ; else cout << s << " is not present " << endl ; cout << "Enter a Number to Remove: " ; cin >> s; tree.Remove (s ); cout << " -: Pre_Order Traversal :-\n" ; tree.Pre_Order (); 30 Example 1: Implementing of Binary Search Tree cout << endl ; system ( "PAUSE " ); return 0; } 17 18

31. A binary search tree can be used in sorting algorithm implementation. The process involves inserting all the elements which are to be sorted and then performing inorder traversal . It is used to implement searching Algorithm . It can be used to implement dictionary . It can be used to Implement routing table in router . It is used to implement multilevel indexing in DATABASE. It is used in implementation of Huffman Coding Algorithm for data compression. Binary trees are a good way to express arithmetic expressions . The leaves are operands and the other nodes are operators. Applications of Binary Search Tree

32. Binary trees can also be used for classification purposes. A decision tree is a supervised machine learning algorithm . The binary tree data structure is used here to emulate the decision-making process . A decision tree usually begins with a root node. The internal nodes are conditions or dataset features. Branches are decision rules while the leave nodes are the outcomes of the decision . For example, suppose we want to classify apples. The decision tree for this problem will be as follows : Applications of Binary Search Tree