4.5.1. Binary Search Tree Definition¶

A binary search tree (BST) is a binary tree that conforms to the following condition, known as the binary search tree property. All nodes stored in the left subtree of a node whose key value is \(K\) have key values less than or equal to \(K\). All nodes stored in the right subtree of a node whose key value is \(K\) have key values greater than \(K\). Figure 4.5.1 shows two BSTs for a collection of values. One consequence of the binary search tree property is that if the BST nodes are printed using an inorder traversal, then the resulting enumeration will be in sorted order from lowest to highest.

Here is a class declaration template for the BST:

class Node:
    def __init__(self, key):
        self.key = key
        self.left = self.right = None


class BST:
    def __init__(self):
        self.root = None

    # Inserts a new key to the BST
    def insert(self, key):
    def __inserthelp(self, node, key):

    # Check if a key is in the BST
    def find(self, key):
    def __findhelp(self, node, key):

    # Removes a key from the BST
    def remove(self, key):
    def __removehelp(self, node, key):

    # Finds/removes the greatest key value from the BST
    def __getmax(self, node):
    def __removemax(self, node):

4.5.2. BST Search¶

The first operation that we will look at in detail will find the record that matches a given key. Notice that in the BST class, public member function find calls private member function __findhelp. Method find takes the search key as an explicit parameter and its BST as an implicit parameter, and returns the record that matches the key. However, the find operation is most easily implemented as a recursive function whose parameters are the root of a subtree and the search key. Member __findhelp has the desired form for this recursive subroutine and is implemented as follows.

Settings

Saving...
Server Error
Resubmit

4.5.3. BST Insert¶

Now we look at how to insert a new node into the BST.

Settings

Saving...
Server Error
Resubmit

Note that, except for the last node in the path, __inserthelp will not actually change the child pointer for any of the nodes that are visited. In that sense, many of the assignments seem redundant. However, the cost of these additional assignments is worth paying to keep the insertion process simple. The alternative is to check if a given assignment is necessary, which is probably more expensive than the assignment!

We have to decide what to do when the node that we want to insert has a key value equal to the key of some node already in the tree. If during insert we find a node that duplicates the key value to be inserted, then we have two options. If the application does not allow nodes with equal keys, then this insertion should be treated as an error (or ignored). If duplicate keys are allowed, our convention will be to insert the duplicate in the left subtree. In this implementation, the BST does not allow duplicate keys. In this implementation, the BST does not allow duplicate keys.

The shape of a BST depends on the order in which elements are inserted. A new element is added to the BST as a new leaf node, potentially increasing the depth of the tree. Figure 4.5.1 illustrates two BSTs for a collection of values. It is possible for the BST containing \(n\) nodes to be a chain of nodes with height \(n\). This would happen if, for example, all elements were inserted in sorted order. In general, it is preferable for a BST to be as shallow as possible. This keeps the average cost of a BST operation low.

4.5.4. BST Remove¶

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. This routine will be used later by the general node removal function.

Settings

Saving...
Server Error
Resubmit

The return value of the __deletemax method is the subtree of the current node with the maximum-valued node in the subtree removed. Similar to the __inserthelp method, each node on the path back to the root has its right child node reassigned to the subtree resulting from its call to the __deletemax method.

A useful companion method is __getmax which returns the maximum value in the subtree.

def __getmax(self, node):
    if node.right == None:
        return node.key
    else:
        return self.__getmax(node.right)

Now we are ready for the __removehelp method. Removing a node with given key value \(R\) from the BST requires that we first find \(R\) and then remove it from the tree. So, the first part of the remove operation is a search to find \(R\). Once \(R\) is found, there are several possibilities. If \(R\) has no children, then \(R\)’s parent has its pointer set to NULL. If \(R\) has one child, then \(R\)’s parent has its pointer set to \(R\)’s child (similar to __deletemax). The problem comes if \(R\) has two children. One simple approach, though expensive, is to set \(R\)’s parent to point to one of \(R\)’s subtrees, and then reinsert the remaining subtree’s nodes one at a time. A better alternative is to find a value in one of the subtrees that can replace the value in \(R\).

Thus, the question becomes: Which value can substitute for the one being removed? It cannot be any arbitrary value, because we must preserve the BST property without making major changes to the structure of the tree. Which value is most like the one being removed? The answer is the least key value greater than the one being removed, or else the greatest key value less than (or equal to) the one being removed. If either of these values replace the one being removed, then the BST property is maintained.

Settings

Saving...
Server Error
Resubmit

When duplicate node values do not appear in the tree, it makes no difference whether the replacement is the greatest value from the left subtree or the least value from the right subtree. If duplicates are stored in the left subtree, then we must select the replacement from the left subtree. 1 To see why, call the least value in the right subtree \(L\). If multiple nodes in the right subtree have value \(L\), selecting \(L\) as the replacement value for the root of the subtree will result in a tree with equal values to the right of the node now containing \(L\). Selecting the greatest value from the left subtree does not have a similar problem, because it does not violate the Binary Search Tree Property if equal values appear in the left subtree.

1

Alternatively, if we prefer to store duplicate values in the right subtree, then we must replace a deleted node with the least value from its right subtree.

4.5.5. BST Analysis¶

The cost for __findhelp and __inserthelp is the depth of the node found or inserted. The cost for __removehelp is the depth of the node being removed, or in the case when this node has two children, the depth of the node with smallest value in its right subtree. Thus, in the worst case, the cost for any one of these operations is the depth of the deepest node in the tree. This is why it is desirable to keep BSTs balanced, that is, with least possible height. If a binary tree is balanced, then the height for a tree of \(n\) nodes is approximately \(\log n\). However, if the tree is completely unbalanced, for example in the shape of a linked list, then the height for a tree with \(n\) nodes can be as great as \(n\). Thus, a balanced BST will in the average case have operations costing \(\Theta(\log n)\), while a badly unbalanced BST can have operations in the worst case costing \(\Theta(n)\). Consider the situation where we construct a BST of \(n\) nodes by inserting records one at a time. If we are fortunate to have them arrive in an order that results in a balanced tree (a “random” order is likely to be good enough for this purpose), then each insertion will cost on average \(\Theta(\log n)\), for a total cost of \(\Theta(n \log n)\). However, if the records are inserted in order of increasing value, then the resulting tree will be a chain of height \(n\). The cost of insertion in this case will be \(\sum_{i=1}^{n} i = \Theta(n^2)\).

Traversing a BST costs \(\Theta(n)\) regardless of the shape of the tree. Each node is visited exactly once, and each child pointer is followed exactly once.

While the BST is simple to implement and efficient when the tree is balanced, the possibility of its being unbalanced is a serious liability. There are techniques for organizing a BST to guarantee good performance. Two examples are the AVL tree and the splay tree. There also exist other types of search trees that are guaranteed to remain balanced, such as the 2-3 Tree.