"""Binary Search Trees Each binary search tree node has a parent, left child, right child, and a key. The tree structure is maintained such that, for any given node x, all the keys on the left subtree rooted by x.left are less than x.key, conversely, all the keys on the right subtree rooted by x.right are greater than or equal to x.key. """ class BinarySearchTreeNode: def __init__(self, key, nil=None): self.key = key self.parent = nil self.left = nil self.right = nil class BinarySearchTree: def __init__(self, root, nil=None): self.root = root def inorder_walk(x, action, nil=None): if x.left != nil: inorder_walk(x.left, action, nil) action(x.key) if x.right != nil: inorder_walk(x.right, action, nil) def recursive_search(x, k, nil=None): if x == nil or k == x.key: return x if k < x.key: return recursive_search(x.left, k, nil) else: return recursive_search(x.right, k, nil) def iterative_search(x, k, nil=None): while x != nil and k != x.key: if k < x.key: x = x.left else: x = x.right return x def minimum(x, nil=None): while x.left != nil: x = x.left return x def maximum(x, nil=None): while x.right != nil: x = x.right return x def successor(x, nil=None): if x.right != nil: return minimum(x.right, nil) y = x.parent while y != nil and x == y.right: x = y y = y.parent return y def insert(T, z, nil=None): y = nil x = T.root while x != nil: y = x if z.key < x.key: x = x.left else: x = x.right z.parent = y if y == nil: T.root = z else: if z.key < y.key: y.left = z else: y.right = z def delete(T, z, nil=None): if z.left == nil or z.right == nil: y = z else: y = successor(z, nil) if y.left != nil: x = y.left else: x = y.right if x != nil: x.parent = y.parent if y.parent == nil: T.root = x else: if y == y.parent.left: y.parent.left = x else: y.parent.right = x if y != z: z.key = y.key return y def print_tree(T, nil=None): def f(key): print key, print "Inorder Tree:", inorder_walk(T.root, f, nil) print ###################################################################### # TEST def test(): data = [12,6,14,17,15,16,10,2,18,19] print "Add data", data, "to tree." T = BinarySearchTree(None) for d in data: insert(T, BinarySearchTreeNode(d)) print_tree(T) print key = 14 print "Search for %d." %key node = iterative_search(T.root, key) print "Found node with key=%d." % node.key suc = successor(node) print "Successor of %d is %d." % (node.key, suc.key) print "Delete node with key=%d." % (node.key) delete(T, node) print_tree(T) print print "Search for maximum." node = maximum(T.root) print "Found node with key=%d." % node.key suc = successor(node) if suc == None: print "No successor of %d was found." % (node.key) else: print "Successor of %d is %d." % (node.key, suc.key) print "Delete node with key=%d." % (node.key) delete(T, node) print_tree(T) print print "Search for minimum." node = minimum(T.root) print "Found node with key=%d." % node.key suc = successor(node) if suc == None: print "No successor of %d was found." % (node.key) else: print "Successor of %d is %d." % (node.key, suc.key) print "Delete node with key=%d." % (node.key) delete(T, node) print_tree(T) if __name__ == '__main__': test()