Explaining Implementing a Binary Search Tree.
Terry Reedy
tjreedy at udel.edu
Sun Jun 15 15:34:22 EDT 2008
"Bart Kastermans" <bkasterm at gmail.com> wrote in message
news:ae91857d-ea63-4204-9fc3-251049adee98 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/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
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/python-list
|
More information about the Python-list
mailing list