Data Structures with Generic Types in Python/

...

/

BinarySearchTree: An Unbalanced Binary Search Tree

BinarySearchTree: An Unbalanced Binary Search Tree

Discover how to search, add or remove an element in the BinarySearchTree.

We'll cover the following...

A BinarySearchTree is a special kind of binary tree in which each node, u, also stores a data value, u.x, from some total order. The data values in a binary search tree obey the binary search tree property: For a node, u, every data value stored in the subtree rooted at u.left is less than u.x and every data value stored in the subtree rooted at u.right is greater than u.x. An example of a BinarySearchTree is shown below.

Press + to interact
A binary search tree
A binary search tree

Searching

The binary search tree property is extremely useful because it allows us to quickly locate a value, x, in a binary search tree. To do this we start searching for x at the root, r. When examining a node, u, there are three cases:

  1. If x < u.x, then the search proceeds to u.left;
  2. If x > u.x, then the search proceeds to u.right;
  3. If x = u.x, then we have found the node u containing x.

The search terminates when Case 3 occurs or when u = None. In the former case, we found x. In the latter case, we conclude that x is not in the binary search tree.

Press + to interact
class BinarySearchTree(BinaryTree,BaseSet):
    """Base classs for all our binary search trees"""
    
    class Node(BinaryTree.Node):
        def __init__(self, x):
            super(BinarySearchTree.Node, self).__init__()
            self.x = x
    def __init__(self, iterable=[], nil=None):
        super(BinarySearchTree, self).__init__()
        self._initialize()
        self.nil = nil
        self.add_all(iterable)
    def find_eq(self, x):
        w = self.r
        while w != self.nil:
            if x < w.x:
                w = w.left
            elif x > w.x:
                w = w.right
            else:
                return w.x
        return None

Visual demonstration of the search operation

Two examples of searches in a binary search tree are shown in the illustration below.

As the second example shows, even if we don’t find x in the tree, we still gain some valuable information. If we look at the last node, u, at which Case 1 occurred, we see that u.x is the smallest value in the tree that is greater than x. Similarly, the last node at which Case 2 occurred contains the largest value in the tree that is less than x. Therefore, by keeping track of the last node, z, at which Case 1 occurs, a BinarySearchTree can implement the find(x) operation that returns the smallest value stored in the tree that is greater than or equal to x:

Press + to interact
class BinarySearchTree(BinaryTree,BaseSet):
    """Base classs for all our binary search trees"""
    
    class Node(BinaryTree.Node):
        def __init__(self, x):
            super(BinarySearchTree.Node, self).__init__()
            self.x = x
            
    def __init__(self, iterable=[], nil=None):
        super(BinarySearchTree, self).__init__()
        self._initialize()
        self.nil = nil
        self.add_all(iterable)
    def find(self, x):
        w = self.r
        z = self.nil
        while w != self.nil:
            if x < w.x:
                z = w
                w = w.left
            elif x > w.x:
                w = w.right
            else:
                return w.x
        if z == self.nil: return None 
        return z.x

Addition

To add a new value, x, to a BinarySearchTree, we first search for x. If we find it, then there is no need to insert it. Otherwise, we store ...