Explaining Implementing a Binary Search Tree.

[Bart Kastermans]

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)