Problem Solving with Algorithms & Data Structures part 4/4

Problem Solving with Algorithms and Data Structures 3.0 by Brad Miller, David Ranum

(A Summary of ADT’s, Trees, and Binary Search)

 

Date

2022.08.03

 

Binary Search Trees

 

Now we will be using the binary tree structure for efficient searching.

 

A binary search tree relies on the property that keys that are less than the parent are found in the left subtree, and keys that are greater than the parent are found in the right subtree. We will call this the bst property.

 

Example of Binary Search Tree w/ BST Property

 

To implement the binary search tree, we will use the nodes and references. However, because we must be able to create and work with a binary search tree that is empty, our implementation will use two classes. The first class we will call BinarySearchTree, and the second class we will call TreeNode. The BinarySearchTree class has a reference to the TreeNode that is the root of the binary search tree. In other words, each node in the BinarySearchTree is a TreeNode type. Thus each node inherits the properties of TreeNode. The TreeNode contains helper functions to keep track of the position of parent nodes and classify nodes.

 

 

Now it is time to write the put method that will allow us to build our binary tree. The put method is a method of the BinarySearchTree class. This method will check to see if the tree already has a root. If there is not a root then put will create a new TreeNode and install it as the root of the tree. If a root node is already in place then put calls the private, recursive, helper function _put to search the tree according to the following algorithm.

 

1. Starting at the root of the tree, search the binary tree comparing the new key to the key in the current node. If the new key is less than the current node, search the left subtree. If the new key is greater than the current node, search the right subtree.
2. When there is no left (or right) child to search, we have found the position in the tree where the new node should be installed.
3. To add a node to the tree, create a new TreeNode object and insert the object at the point discovered in the previous step.
4. If the node is a duplicate of the existing one, then replace the new key with the old value.

 

The _put function is written recursively following the steps outlined above. 

 

 

With the put method defined, we can easily overload the [] operator for assignment by having the __setitem__ method call the put method. This allows us to write Python statements like my_zip_tree[‘node’] = payload, just like a Python dictionary.

 

Once the tree is constructed, the next task is to implement the retrieval of a value for a given key. The get method is even easier than the put method because it simply searches the tree recursively until it gets to a non-matching leaf node or finds a matching key. When a matching key is found, the value stored in the payload of the node is returned. 

 

The code for get, _get, and __getitem__ is implemented so the _get method uses the same logic for choosing the left and right child as the _put method. The _get method returns a TreeNode to get, this allows _get to be used as a flexible helper method for other BinarySearchTree methods that may need to take use of other data from the TreeNode besides the payload.

 

 

Now we implement the final method for the binary search tree: deletion of key. The first task is to find the node to delete by searching the tree. If the tree has more than one node we search using the _get method to find the TreeNode that needs to be removed. If the tree only has a single node, that means we are removing the root of the tree, but we still must check to make sure the key of the root matches the key that is to be deleted.

 

 

Once we’ve found the node containing the key we want to delete, there are three cases that we must consider.

 

ex) Deleting node with only one children

 

1. The node to be deleted has no children.
2. The node to be deleted has only one child.
3. The node to be deleted has two children.

 

The first case is straightforward. If the current node has no children all we need to do is delete the node and remove the reference to this node in the parent.

 

Removing node with no children

 

The second case is when a node has a single child. We can simply promote the child to take the place of its parent. There are six cases to consider which are symmetric with respect to either having a left or right child.

 

1. If the current node is a left child then we only need to update the parent reference of the left child to point to the parent of the current node, and then update the left child reference of the parent to point to the current node’s left child.
2. If the current node is a right child then we only need to update the parent reference of the right child to point to the parent of the current node, and then update the right child reference of the parent to point to the current node’s left child.
3. If the current node has no parent, it must be the root. In this case we will just replace the key.payload, left_child, and right_child data by calling the replace_node_data method on the root.

 

Removing node with one child

 

The third case is when a node has two children. In this case, it is inappropriate to simply promote one of the children to take the node’s place. Instead, we search the tree for a node that can replace the node. We want to find a node that will preserve the binary search tree relationships. The node that will do this is the node that has the next-largest key in the tree. We will call this node the successor, and the successor is guaranteed to have no more than one child, so we know how to remove it using the two cases for deletion that we have already implemented. Once the successor has been removed, we simply put it in the tree in place of the node to be deleted. We will be using helper methods find_successor and find_min to find the successor. To remove the successor, we make use of the splice_out.

 

Removing node with both children

 

The code to find the successor uses the same properties of binary search trees that cause an inorder traversal to print out the nodes in the tree from smallest to largest. There are three cases to consider when looking for the successor:

 

1. If the node has a right child, then the successor is the smallest key in the right subtree.
2. If the node has no right child and is the left child of its parent, then the parent is the successor.
3. If the node is the right child of its parent, and itself has no right child, then the successor to this node is the successor of its parent, excluding this node.
4. The first condition is the only one that matters for us when deleting a node from a binary search tree. However, the find_sucessor method has other uses that we will explore in the exercises at the end of this chapter.

 

The find_min method is called to find the minimum key in a subtree. You should convince yourself that the minimum valued key in any binary search tree is the leftmost child of the tree. Therefore the find_min method simply follows the left_child references in each node of the subtree until it reaches a node that does not have a left child.

 

 

At this point you have the complete version of both BinarySearchTree and TreeNode classes.

 

That’s it for General Tree Data Types and Tree Traversals.

 

The End.