Section 10.4 Binary Search Trees
A binary search tree (BST) is a binary tree that satisfies the binary search tree property. According to this property, all nodes in the left subtree of a node with a key value K have key values less than or equal to K, and all nodes in the right subtree have key values greater than K. An important consequence of this property is that when the BST nodes are printed using an inorder traversal, the resulting enumeration will be in sorted order, from the lowest key value to the highest.
The first operation we will examine is the search operation, which finds the record that matches a given key. In the BST class, the public member function find calls the private member function findhelp. The find method takes the search key as an explicit parameter and the BST as an implicit parameter, and it returns the record that matches the key. However, the search operation is best implemented as a recursive function that takes the root of a subtree and the search key as parameters.
Removing a node from a BST is a bit trickier than inserting a node, but it is not complicated if all of the possible cases are considered individually. Before tackling the general node removal process, we will first see how to remove from a given subtree the node with the largest key value.
You have attempted of activities on this page.
