CSE-111 Data Structure Module 01: Binary Search Tree (BST) PDF

New Mansoura University Faculty of Computer Science and Engineering CSE-111 Data Structure Module 01: Binary Search Tree (BST) Dr. Omar Elzeki Assistant Professor [email protected] Objectives Learn about binary search trees Learn how...

New Mansoura University Faculty of Computer Science and Engineering CSE-111 Data Structure Module 01: Binary Search Tree (BST) Dr. Omar Elzeki Assistant Professor [email protected] Objectives Learn about binary search trees Learn how to organize data in a binary search tree Explore various binary search tree algorithms Discover how to: Find item in a binary search tree Find Max and Min insert items in a binary search tree Delete items in a binary search tree 12/21/2023 2  Binary Search Tree (BST) Data Structure 8 Structure property (binary tree) Each node has  2 children Result: keeps operations simple 5 11 Order property 2 6 10 12 Result: straight-forward to find any given value 4 7 9 14 A binary search tree is a type of binary tree 13 (but not all binary trees are binary search trees!) 12/21/2023 3  Binary Search Trees (BSTs) Where is the smallest element? Ans: leftmost element Where is the largest element? Ans: rightmost element How to search a binary search tree? (1) Start at the root (2) Compare the value of the item you are searching for with the value stored at the root (3) If the values are equal, then item found; otherwise, if it is a leaf node, then not found Practice: are these BSTs? 5 8 4 8 5 11 1 7 11 2 7 6 10 18 3 4 15 20 21 12/21/2023 6 Tree Search Tree-Search(x, k) 1. if x = NIL or k = key[x] 2. then return x 3. if k < key[x] 4. then return Tree-Search(left[x], k) 56 5. else return Tree-Search(right[x], k) 26 200 Running time: O(h) 18 28 190 213 12 24 27 12/21/2023 7 Iterative Tree Search Iterative-Tree-Search(x, k) 56 1. while x  NIL and k  key[x] 26 200 2. do if k < key[x] 18 28 190 213 3. then x  left[x] 4. else x  right[x] 12 24 27 5. return x The iterative tree search is more efficient on most computers. The recursive tree search is more straightforward. 12/21/2023 8 Other BST “Finding” Operations 12 findMin: Find minimum node 5 15 2 9 20 findMax: Find maximum node 7 10 17 30 12/21/2023 9 Finding Min & Max The binary-search-tree property guarantees that: » The minimum is located at the left-most node. » The maximum is located at the right-most node. Tree-Minimum(x) Tree-Maximum(x) 1. while left[x]  NIL 1. while right[x]  NIL 2. do x  left[x] 2. do x  right[x] 3. return x 3. return x Q: How long do they take? 12/21/2023 10 How do we find( v al u e ) in BTS? 12 5 15 2 9 20 7 10 17 30 12/21/2023 11 find in BST: Recursive Version Data find(Data value, Node root){ if(root == null) 12 return null; if(key < root.value) return find(value, root.left); if(key > root.value) 5 15 return find(value, root.right); return root.value; } 2 9 20 What is the running time? 7 10 17 30 12/21/2023 12 find in BST: Iterative Version 12 Data find(Object value, Node root){ while(root != null && root.value != value) { if (value < root.value) 5 15 root = root.left; else (value > root.value) root = root.right; } 2 9 20 if(root == null) return null; return root.value; 7 10 17 30 } 12/21/2023 13 Function InsertItem Use the binary search tree property to insert the new item at the correct place 12/21/2023 14  Function InsertItem (cont.) Implementing insertion recursively e.g., insert 11 12/21/2023 15  Function InsertItem (cont.) What is the size of the problem? Number of nodes in the tree we are examining What is the base case(s)? The tree is empty What is the general case? Choose the left or right subtree 12/21/2023 16  Function InsertItem (cont.) template void TreeType::InsertItem(ItemType item) { Insert(root, item); } template void Insert(TreeNode*& tree, ItemType item) { if(tree == NULL) { // base case tree = new TreeNode; tree->right = NULL; tree->left = NULL; tree->info = item; } Running Time? else if(item < tree->info) Insert(tree->left, item); O(h) else Insert(tree->right, item); } 12/21/2023 17  Function InsertItem (cont.) Insert 11 12/21/2023 18 Does the order of inserting elements into a tree matter? Yes, certain orders might produce very unbalanced trees! 12/21/2023 19 Does the order of inserting elements into a tree matter? (cont.) 12/21/2023 20  Does the order of inserting elements into a tree matter? (cont’d) Unbalanced trees are not desirable because search time increases! Advanced tree structures, such as AVL, red-black trees, guarantee balanced trees. 12/21/2023 21  Function DeleteItem First, find the item; then, delete it Binary search tree property must be preserved!! We need to consider three different cases: (1) Deleting a leaf (2) Deleting a node with only one child (3) Deleting a node with two children 12/21/2023 22 (1) Deleting a leaf 12/21/2023 23  (2) Deleting a node with only one child 12/21/2023 24  (3) Deleting a node with two children (cont.) Find predecessor (i.e., rightmost node in the left subtree) Replace the data of the node to be deleted with predecessor's data Delete predecessor node 12/21/2023 25 (3) Deleting a node with two children 12/21/2023 26  Function DeleteItem (cont.) What is the size of the problem? Number of nodes in the tree we are examining What is the base case(s)? Key to be deleted was found What is the general case? Choose the left or right subtree 12/21/2023 27  Function DeleteItem (cont.) template void TreeType::DeleteItem(ItemType item) { Delete(root, item); } template void Delete(TreeNode*& tree, ItemType item) { if(item < tree->info) Delete(tree->left, item); else if(item > tree->info) Delete(tree->right, item); else DeleteNode(tree); } 12/21/2023 28  Function DeleteItem (cont.) template void DeleteNode(TreeNode*& tree) { ItemType item; TreeNode* tempPtr; tempPtr = tree; if(tree->left == NULL) { // right child tree = tree->right; 0 children or delete tempPtr; } 1 child else if(tree->right == NULL) { // left child tree = tree->left; delete tempPtr; } 0 children or else { 1 child GetPredecessor(tree->left, item); tree->info = item; Delete(tree->left, item); } 2 children } 12/21/2023 29 Function DeleteItem (cont.) template void GetPredecessor(TreeNode* tree, ItemType& item) { while(tree->right != NULL) tree = tree->right; item = tree->info; } 12/21/2023 30  Function DeleteItem (cont.) template void TreeType::DeleteItem(ItemType item) { Delete(root, item); } template void Delete(TreeNode*& tree, ItemType item) { if(item < tree->info) Delete(tree->left, item); else if(item > tree->info) Delete(tree->right, item); Running Time? else DeleteNode(tree); O(h) } 12/21/2023 31  Thank You 12/21/2023 32