Explaining Implementing a Binary Search Tree.
Bart Kastermans
bkasterm at gmail.com
Sun Jun 15 16:03:04 CEST 2008
I wrote a binary search tree in python, explaining as I was doing it
how and why I did it. I am very interested in receiving comments on
the code, process, and anything else that will improve my coding or
writing.
I wrote this all up in my blog at:
http://kasterma.wordpress.com/2008/06/15/implementing-a-binary-search-tree/
The code of the class has been copied below, but the description of
the process (mostly an attempt at approaching test driving development
for as far as I understand the term) has not been copied.
Any and all comments are appreciated.
Best,
Bart
*********** python code ************************
import re
class BSTree:
def __init__ (self, value = None):
self.value = value
self.left = None
self.right = None
def __str__ (self):
string = "("
if not self.value == None:
string += str (self.value)
if not (self.left == None and self.right == None):
if self.left != None:
string += str (self.left)
else:
string += "()"
if self.right != None:
string += str (self.right)
else:
string += "()"
string += ")"
return string
def FromString (self, string):
""" parses the string and builds the corresponding tree.
If the parsing fails we print an error message and make no
guarantees about the state of the tree.
"""
def readNumber (string, index):
""" reads the number starting at index.
Returns the number (as a string) that starts at index and
the index that is just after the number. It expects the
index to point to the first numberal.
"""
isdigit = re.compile ("\d")
number = ""
while isdigit.match (string [index]):
number += string[index]
index += 1
return number, index
def FromString_Help (string, index):
""" The function that actually does the parsing of the
string.
Variable index indicates where in the string we start
working,
it should be pointing to an open paren, and in returning
point
to just after the corresponding closing paren.
"""
if not string [index] == "(":
print "FromString_Help: ERROR: no opening paren",
print string, index
tree = BSTree ()
tree.value, index = readNumber (string, index + 1)
if string [index] == "(":
tree.left, index = FromString_Help (string, index)
tree.right, index = FromString_Help (string, index)
if not string[index] == ")":
print "FromString_Help: ERROR: no closing paren"
print string, index
if tree.value == '' and tree.left == None and tree.right
== None:
return None, index + 1
else:
tree.value = int (tree.value)
return tree, index + 1
index = 0
tree, index = FromString_Help (string, index)
if tree == None:
print "FromString: ERROR: empty tree passed"
return
self.value = tree.value
self.left = tree.left
self.right = tree.right
def inOrder (self):
""" gives a generator that runs through the tree inOrder """
values = []
if self.left != None:
values += self.left.inOrder ()
if self.value != None:
values.append (self.value)
if self.right != None:
values += self.right.inOrder ()
return values
def Insert (self, value):
""" add value to the tree in BSTree fashion.
We add the value so that the values of the tree will be in
order. We do not duplicate values in the tree.
"""
if self.value == None: # first value added to this tree
self.value = value
if self.value < value:
if self.right == None:
self.right = BSTree (value)
else:
self.right.Insert (value)
if self.value > value:
if self.left == None:
self.left = BSTree (value)
else:
self.left.Insert (value)
def Delete (self, value, parent = None, RL = None):
""" remove value from the tree in BSTree fashion.
Note: we might end up with an empty tree.
"""
if self.value == value:
if self.left == None and self.right == None:
if parent != None:
if RL == "right":
parent.right = None
else:
parent.left = None
else:
self.value = None # created an empty tree, note
only
# happens at the root.
return
if self.left == None:
self.value = self.right.value
self.left = self.right.left
self.right = self.right.right
elif self.left.right == None:
self.value = self.left.value
self.left = self.left.left
else:
moveup = self.left
while moveup.right != None:
# note that by the elif above at least one step is
taken
# we are here looking for the node to move up to
the root
moveup_parent = moveup
moveup = moveup.right
moveup_parent.right = moveup.left
self.value = moveup.value
return
if self.value < value:
self.right.Delete (value, self, "right")
if self.value > value:
self.left.Delete (value, self, "left")
def Search (self, value):
if self.value == value:
return "yes"
if self.value < value:
if self.right == None:
return "no"
else:
return self.right.Search (value)
if self.value > value:
if self.left == None:
return "no"
else:
return self.left.Search (value)
More information about the Python-list
mailing list