Trees - Binary Search Tree
We should be pretty familiar with a binary tree. In this lesson we will examine an extension of them termed binary search tree.
A binary search tree Is a binary tree that consists of nodes which each have a value and a left and right pointer. Nodes in the left subtree are less than the current node while nodes in the right subtree are greater.
The application of this is for consistent look up. When an algorithm searchs
for a specific value, it is able to eliminate half the nodes on each
iteration, giving lookup time complexity of Node and tree creation algorithm from the previous
lesson.
Here's an image of what a binary search tree might look like.
To search, the node either exists or it does not. We use a
property of a binary search tree to recurse down either the left or
right child node. The base case is the node doesn't exist, and will
return None if we end up in that situation. Otherwise, if we end up
at a point where node.value == key (which is the last
return statement), then we may return it. To make sure the base or
last case propogates back up, we return at the recursion points.
To insert, the node either is new or already exists. In the latter, there is nothing we need to do. If it's new, then we need to first find the right location to insert at. We may use the same algorithm as in search with a minor alteration. The base case that the node doesn't exist is the exact place we wish to insert it at. Additionally, we need to update its parent's right or left pointer based on the inserted node. Note how when we print the tree after insertion, the new node is correctly printed in sorted order.
Before we write any code for deletion, we will look at various examples. Deletion is much more complicated than either search or insert. This is because we need to actually change references in the tree, depending on the node that is marked for deletion. Pay attention to how the example tree changes slightly to highlight each example.
Our first example is deleting a leaf node. This is fairly straight forward. Find the node in the tree, and delete it.
Our next example is deleting a node that has one child. We should take the child and set it as a reference in the same left or right of the parent node. Note how this preserves a child that itself has a child.
Here's the really complicated part. A node for deletion has two children. Which node should we choose?
Well, we have two options. Find the leaf that is right-most of the left child, or find the leaf that is left-most of the right child. Take this leaf node, termed successor node, and set its value to the node for deletion. Then delete the successor node.
Why does this work? Because the successor node is guaranteed to maintain the property of a binary search tree. In the former case, the successor will be the largest node in the left subtree, and thus a candidate to replace the node for deletion. In the latter case, the successor node will be the smallest node in the right subtree, and thus also a candidate.
For simplicity, our algorithm will use the left-most node of the right child as the successor node.
What happens when the successor node itself has a child? Well, it can't be a left node, otherwise we would have chosen it. So, it must be a right node. There are once again, two situations. The first is when the parent node to the successor is the node for deletion. In this case, we should set the parent's right node to that of the successor's right. Notice how this appears to move the nodes up.
The last situation is when the successor node's parent is not the node for deletion. In this case, we know we are at a terminal left, and may set the successor parent's left node to that of the successor's right. This also appears to move the nodes up.
We're now ready to write code for deletion. We start with a similar recursion step as insert. We then handle multiple situations where the node for deletion has zero, one, or two children.
In this example, the node for deletion Node(60) has two children. Its successor node is Node(70). The reference updates should occur as in the relevant figure above.