When a binary search tree is constructed, the keys are added one at a time. As the keys are inserted, a new node Node(key, data) is created for each key and linked to its proper position within the tree.
Suppose we want to build a binary seach tree from the key list 60, 25, 100, 35, 17, 80 by inserting the keys in the order thay are listed.
But how do we insert the new keys? Suppose we want to insert key 30 into the tree we built by hand. What happens if we use the _search() method and search for key 30? The search will eventually lead us to node 35 and we then fall off the tree when attempting to follow its left child link, as illustrated in below. Notice that this is the exact location where the new key needs to be inserted.
We can use a modified version of the search operation to insert new keys into a binary search tree.
class BSTMap : #...
# Adds a new entry to the map or replaces the value of an existing key.
def add( self, key, value ):
# Find the node containing the key, if it exists.
node = self._bstSearch( key )
# If the key is already in the tree, update its value.
if node is not None :
node.value = value
return False
# Otherwise, add a new entry.
else :
self._root = self._bstInsert( self._root, key, value )
self._size += 1
return True
# Helper method that inserts a new item, recursively.
def _insert( self, subtree, key, value ):
if subtree is None :
subtree = _BSTMapNode( key, value )
elif key < subtree.key :
subtree.left = self._bstInsert( subtree.left, key, value )
elif key > subtree.key :
subtree.right = self._bstInsert( subtree.right, key, value )
return subtree
To describe how the recursive method works, suppose we want to insert key value 30 into the tree we built by hand from above and below illustrates the method’s view of the tree in each invocation and shows the changes to the tree as the specific instructions are executed. Remember, given the recursive definition of a binary tree, each node is itself the root of a subtree. As the _insert() recursive method navigates through the tree, the root of the current subtree will be the node of interest.
To insert key value 30, the method must search for its ultimate location by recursively navigating deeper into the tree following either the left or right branch at each node as appropriate. These recursive steps are shown here.
The gray nodes indicate the root of the subtree currently being processed by the current invocation of the method. The dashed lines indicate the direction we must follow to find the correct path through the tree and then the path followed during the unwinding of the recursion.
