Week9: Binary Search Tree Data Structure

   

       In this week's lecture and lab, we concentrated on the binary search tree data structure. A binary search tree is a binary tree whose data in left subtree is less than that in the root, which in turn is less than that in right subtree. Also there is no duplicate node in the binary tree. With these properties, searching becomes more efficient.
    To find a data in a binary search tree, we compare the data with the root value. If the data is greater than the root value, we will search the right subtree recursively and if the data is less than the root value, we will search the left subtree recursively with appropriate base cases.
  

 

    Insertion is similar, we compare the data with the root value. If the root is None, then we create a new binary search tree node. If the data is greater than the root, than search the right subtree and if the data is less than the root, search the left subtree. Eventually, we will reach a external node to add a new node to the binary search tree. 

 

 

    Deletion is a little bit complicated. There are roughly three cases: deleting a leaf, deleting a node with no left child, deleting a node with no right child.

    Algorithm for _delete:
       1. If this node is None, return that
       2. If data is less than node.data, delete it from left child and return this node
       3. If data is more than node.data, delete it from right child and return this node
       4. If node with data has fewer than two children, and you know one is None, return the other one
       5. If node with data has two non-None children, replace data with that of its largest child in

           the left subtree, and delete that child, and return this node

 

 

    In this week's lab, we wrote a function count_less in binary search tree using several different ways. Recursion is a good way to deal with binary search tree, and looping is also a good way.

    In Wikipeia, there is more information about binary search tree that I can get approach.

Reference: http://en.wikipedia.org/wiki/Binary_search_tree