Source code online books for professionals by professionals

Listing 6-2.  Insertion into and Search in a Binary Search Tree
class Node:
    lft = None
    rgt = None
    def __init__(self, key, val):
        self.key = key
        self.val = val
 
def insert(node, key, val):
    if node is None: return Node(key, val)      # Empty leaf: add node here
    if node.key == key: node.val = val          # Found key: replace val
    elif key < node.key:                        # Less than the key?
        node.lft = insert(node.lft, key, val)   # Go left
    else:                                       # Otherwise...
        node.rgt = insert(node.rgt, key, val)   # Go right
    return node
 
Figure 6-6.  A (perfectly balanced) binary search tree, with the search path for 11 highlighted

---

Chapter 6 
■
 DiviDe, Combine, anD Conquer
122
def search(node, key):
    if node is None: raise KeyError             # Empty leaf: it's not here
    if node.key == key: return node.val         # Found key: return val
    elif key < node.key:                        # Less than the key?
        return search(node.lft, key)            # Go left
    else:                                       # Otherwise...
        return search(node.rgt, key)            # Go right
 
class Tree:                                     # Simple wrapper
    root = None
    def __setitem__(self, key, val):
        self.root = insert(self.root, key, val)
    def __getitem__(self, key):
        return search(self.root, key)
    def __contains__(self, key):
        try: search(self.root, key)
        except KeyError: return False
        return True 
Note
 
■
  the implementation in Listing 6-2 does not permit the tree to contain duplicate keys. if you insert a new value 
with an existing key, the old value is simply overwritten. this could easily be changed because the tree structure itself 
does not preclude duplicates.