From 6.006 Wiki
Binary Search Tree Implementation
# Recitation 06- WF3
#
# An implementation of a binary search tree using
# Python objects.
#
# Users should instantiate and make method calls to the
# BST object instead of BSTnode. The reason is because
# BSTnode objects may shift positions or even values during
# a tree operation, but the BST will be stable.
#
# Keys inserted into the BST are assumed to be unique
# and must be objects that are comparable.
#
class BST(object):
"""
A binary search tree. For the most part, this class is just
a wrapper for BSTnode.
"""
def __init__(self):
"""
Constructs an empty BST.
"""
self.root = None
def insert(self, t):
"""
Inserts the key t into the BST.
"""
if self.root is None:
self.root = BSTnode(None, t)
else:
self.root.insert(t)
def find(self, t):
"""
Returns the BSTnode with the value t.
"""
if self.root is None:
return None
else:
return self.root.find(t)
def next_larger(self, t):
"""
Returns the next largest node or None if self is largest.
"""
node = self.find(t)
if node is None:
return None
return node.next_larger()
def delete(self, t):
"""
Deletes the <b>value</b> of key t from the BST.
"""
node = self.find(t)
# handle delete root case here
# note: it is tricky to handle this case in
# BSTnode.delete() because if the node has no
# children, we need to set self.root to None
if self.root == node:
if node.right is None:
self.root = node.left
node.left.parent = None
elif node.left is None:
self.root = node.right
node.right.parent = None
else:
next = node.next_larger()
node.key = next.key
next.delete()
elif node is not None:
node.delete()
def to_orderedlist(self):
"""
Returns a list of keys in the BST in sorted order
"""
return self.root.to_orderedlist()
class BSTnode(object):
"""
A node in a binary search tree
"""
def __init__(self, parent, t):
self.key = t
self.parent = parent
self.left = None
self.right = None
def find(self, t):
if t == self.key:
return self
elif t < self.key:
if self.left is None:
return None
return self.left.find(t)
else:
if self.right is None:
return None
return self.right.find(t)
def insert(self, t):
if t < self.key:
if self.left is None:
self.left = BSTnode(self, t)
else:
self.left.insert(t)
else:
if self.right is None:
self.right = BSTnode(self, t)
else:
self.right.insert(t)
def get_min(self):
if self.left is None:
return self
else:
return self.left.get_min()
def next_larger(self):
# Case 1: has a right subtree
if self.right is not None:
return self.right.get_min()
# Case 2: no right subtree and no parent
elif self.parent is None:
return None
# Case 3: no right subtree but has parent
p = self.parent
node = self
# traverse up the tree until node is the left-child
while p is not None and p.right==node:
node = node.parent
p = node.parent
return node.parent
def delete(self):
# case 1: leaf node
if self.left is None and self.right is None:
if self.parent.left == self:
self.parent.left = None
else:
self.parent.right = None
# case 2a: 1 right child
elif self.left is None:
if self.parent.left == self:
self.parent.left = self.right
else:
self.parent.right = self.right
self.right.parent = self.parent
# case 2b: 1 left child
elif self.right is None:
if self.parent.left == self:
self.parent.left = self.left
else:
self.parent.right = self.left
self.left.parent = self.parent
# case 3: 2 children
else:
next = self.next_larger()
self.key = next.key
next.delete()
def to_orderedlist(self):
L = []
if self.left is not None:
L.extend(self.left.to_orderedlist())
L.append(self.key)
if self.right is not None:
L.extend(self.right.to_orderedlist())
return L
def __repr__(self):
try:
p = self.parent.key
except:
p = None
try:
l = self.left.key
except:
l = None
try:
r = self.right.key
except:
r = None
return "{Key: %s ; Parent: %s ; Left: %s ; Right: %s}" \
% (self.key,p,l,r)
###################
L = [10, 5, 8, 7, 4, 11, 1, 3, 2, 9, 6, 12]
T = BST()
for item in L:
T.insert(item)