VJC Chapter 18 Binary Search Tree

VJC/H2Computing/9569 1 Chapter 18 Binary Search Tree Contents 1 Binary Search Trees 2 OOP implementation of a binary search tree 2.1 Node object 2.2 Insertion operation 2.3 Search operation 2.4 Deletion operation [no coding required] 2.5 Update operation [no coding required] 3 Array implementation of a binary tree 4 Time Complexity of Binary search tree for Search Operation 5 Tree traversal 5.1 Pre-order traversal 5.2 In-order traversal 5.3 Post-order traversal Syllabus Learning Outcomes 1.3 Data Structures Understand concept and write algorithms for stack, queue (linear and circular), linear linked list and binary tree (including binary search tree). 1.3.6 Create, update (edit, insert, delete) and search operations for a binary tree (including binary search tree). Exclude: edit and deletion of nodes from binary search tree 1.3.7 Understand pre-order, in-order and post-order tree traversals; and application of in-order tree traversal for a binary tree. 2.3 Implementing Algorithms and Data Structures Use programming language elements and constructs to implement sort and search algorithms such as insertion sort, bubble sort, quicksort, merge sort, linear search, binary search and hash table search, as well as data structures such as stacks, queues, line ar linked lists and binary search trees. 2.3.2 Implement search programs. – Linear search – Binary search – Hash table search 2.3.3 Write programs to implement operations for stacks, queues (linear and circular), linear linked lists and binary search trees. Exclude: doubly-linked list and circular linked list

VJC/H2Computing/9569 2 1 Binary Search Trees In the real world, we draw tree structures to represent hierarchies. For example, we can draw a family tree showing ancestors and their children. A binary tree is different from a family tree. It is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. This structure allows for efficient searching, insertion, and deletion operations. A binary search tree is a specific type of binary tree with an additional property: for each node, the values of all nodes in its left subtree are less than or equal to the node's value, and the values of all nodes in its right subtree are greater than the node's value. This ordering property makes binary search trees particularly useful for searching and retrieval operations. Let’s look at a conceptual diagram of a binary search tree. A binary search tree is a non-linear data structure represented using nodes connected by edges. A tree’s topmost node is called a root node. Each node (apart from the root) in a tree that has at least one sub-node of its own is called a parent node. All nodes have one parent except the root node, which has no parent. Each node can have zero, one, or two children, typically named as the left child and right child. A node with no child, typically the bottom-most node is also called a leaf node. For each node, the values of its left descendent nodes are less than that of the current node, which in turn is less than the right descendent nodes (if any). A binary search tree (BST) is built on the idea of the binary search algorithm which allows for fast lookup, insertion, and removal of nodes. Data stored in the whole tree can be printed out in sequence. F C S B E R Parent/child node Leaf nodes Left subtree Right subtree Root node

VJC/H2Computing/9569 3 2 OOP implementation of a binary search tree 2.1 Node object A binary search tree implementation is typically by object -oriented programming, where a node will have the following attributes: ● data ● pointer to left child ● pointer to right child 2.2 Insertion operation The rules to follow to create a binary search tree that can be easily and quickly searched for a given data: ● Place the first data in the root node. ● Take each subsequent data in turn. ● Start at the root node each time. If the data is less than data in the root node, branch to the left, and if it is greater than the data in the root node, branch to the right. ● Apply the rule at each node encountered. This automatically sorts the data as they are being added. Pseudocode for insertion: IF root is NONE THEN root ← Node(data) ELSE parent ← root WHILE data not inserted DO IF data < parent’s data // branch left THEN IF left branch is empty THEN parent’s left pointer ← Node(data) ELSE parent ← left node ENDIF ELSE // branch right, we assume no duplicate data IF right branch is empty THEN parent’s right pointer ← Node(data) ELSE parent ← right node ENDIF ENDIF ENDWHILE ENDIF Data Left Right Node

VJC/H2Computing/9569 4 Insertion walkthrough: Example 1 Values to be added Binary Search Tree 1. 15 2. 12 3. 5 4. 50 5. 42 6. 13 7. 14 Example 2 Values to be added Binary Search Tree 1. 5 2. 12 3. 13 4. 15 5. 42 6. 50 7. 14 15 12 50 5 13 14 42 5 12 14 15 13 42 50

VJC/H2Computing/9569 5 2.3 Search operation The search operation in a binary search tree is similar to the binary search algorithm. In binary search, we will be given a sorted array and we have to search for an element so we start with finding the middle element in the array and compare it with the element to be searched. If the element to be searched is equal to the middle element then we will stop and simply return that element. But if the element to be searched is smaller than the middle element we will discard the right subarray as the elements a re in sorted form so we can easily say that the element will be present in the left subarray and if the element is found to be greater than the middle element we will search in right subarray discarding the left subarray. So in this way, we will keep on reducing the array size in half till we get our target element(element to be searched) or we are left with only one element. The same procedure is applicable in the case of binary search tree. In this case, we will be given a tree and a target value that needs to be searched. We will start comparing that element with the root node's value. If the element to be searched is equal to the root node's value, we will simply stop and return that element as it is successfully searched. But if the element is smaller than the root node's value, we will discard the right subtree of the root node as after learning the properties of the binary search tree we can say that the element needs to be searched in the left subtree as all the node values in left subtree will be smaller than the root node value. If the element is greater than the root node's value, we will discard the left subtree of the root node because all the nodes in the right subtree have values greater than the root node value so we will search for the element in the right subtree. This way, we will keep on reducing the size of the binary search tree till we find the element that needs to be searched or we are left with one node only. We can see that the procedure is the same as what we have done in the binary search algorithm, and this is the reason for the name Binary Search Tree. The search operation can be implemented using the following algorithm: current_node ← root REPEAT IF data < current_node.data THEN current_node ← current_node.left ELSE current_node ← current_node.right ENDIF UNTIL current_node.data EQUALS data OR Current_node has no corresponding child node

VJC/H2Computing/9569 6 2.4 Deletion operation [no coding required] Deletion of a node from the binary search tree is dependent