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 c