Explaining Implementing a Binary Search Tree.
Terry Reedy
tjreedy at udel.edu
Sun Jun 15 21:34:22 CEST 2008
"Bart Kastermans" <bkasterm at gmail.com> wrote in message
news:ae91857dea6342049fc3251049adee98 at k13g2000hse.googlegroups.com...
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/implementingabinarysearchtree/

 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
There are two possible approaches.
1. Define 1 tree class that is also used for subtrees  what you did.
Complication: self.value of root node can be none, so you constantly
have to check self.value for None even though only possible for root node.
2. Define tree class and node class. This had other complications, but
removes that above and makes str easier. tree.str = '(' str(rootnode) ')'
and node.str= self.value '(' str(self.left) ')' '(' str(self.right) ')'.
If use '' instead of None, no conditionals are needed. (This might apply
partly to your version as well.) Or define class NullTree with a singleton
instance with no attributes and a str method returning '' and an inOrder
method yielding nothing. This would also eliminate the condifionals in the
inOrder method. Not sure what is best. With a good test suite, it is easy
to make sure alternative implementations 'work' before testing for speed.
 def __str__ (self):
string appending is an O(n**2) operations. The usual idiom, applied here,
would be slist = ['('], slist.append(str(self.value)), .... return
''.join(slist). In other words, collect list of pieces and join at end.
 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 """
Nope. Returns an inorder list of values.
For an actual generator, which I recommend, *yield* values.

 values = []
[delete this'
 if self.left != None:
 values += self.left.inOrder ()
for value in self.left.inOrder: yield value
 if self.value != None:
 values.append (self.value)
yield self.value
 if self.right != None:
 values += self.right.inOrder ()
for value in self.right.inOrder: yield value
 return values
[delete this]
The above with result in a stack of generators as deep as the tree. It
would probably be faster to eliminate the recursion with an explicit stack
of trees, but I cannot currently write that off the top of my head. (This
is part of my current writing project.) But again, a test suite eases
exploration of alternatives.
 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)
 
 http://mail.python.org/mailman/listinfo/pythonlist

More information about the Pythonlist
mailing list