• Binary Search Trees
    • In our discussion of sorting, we saw that if a list is sorted, and you can access any item in a constant time, you can use binary search, rather than linear search, and the complexity of determining whether an item occurs in a list goes down from O(n) to O(log(n)).  However, if you cannot access any item in a constant time, then you cannot use binary search.  Fortunately, binary search trees (BSTs) solve this problem.

      Read the basics of binary search trees at

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

      and/or watch all or some of the following videos

      https://www.youtube.com/watch?v=pYT9F8_LFTM&hd=1

      https://www.youtube.com/watch?v=rVU_jXyHXqw&hd=1

      https://www.youtube.com/watch?v=pmsVitdSaVU&hd=1

       

    • One of the potential problems with BSTs is that they may become unbalanced.  A BST is unbalanced if the depth of the left subtree is more than 1 larger than the depth of the right subtree.  A BST becomes unbalanced when the items that are inserted into the BST arrive more or less sorted.

      In order to solve this problem, computer scientists have developed a number of ways of keeping BSTs balanced.

      An as exercise, try to find one such way (hint: most of the solutions lead to the BST being self-balancing), and post your solution in the drop box.

    • Another useful application of trees in computing is in the analysis of in particular 2-person games (e.g., tic-tac-toe, chess, checkers, and so on). 

      Here is some written material on And-Or Trees

      http://en.wikipedia.org/wiki/And-or_tree

      And here are some videos

      https://www.youtube.com/watch?v=hEEzZ-XwZi4&hd=1

      https://www.youtube.com/watch?v=Unh51VnD-hA&hd=1

      https://www.youtube.com/watch?v=STjW3eH0Cik&hd=1

      The audio of the last video is not great.

       

    • One of the properties that makes certain games more interesting than others is the complexity of the game.  One of the ways to measure complexity is to look at the branching factor of the game tree. The greater the branching factor the more game states one would need to consider.

      Your exercise for this module is two-fold.

      First, figure out how many states one would have to consider for a two-person game like chess after 3 moves by white and 3 moves by black.

      Second, you will soon determine that the number of states you would have to consider becomes impossibly large, and good chess playing programs therefore have to rely on heuristics.  You second task is the find out what is meant by the term "heuristics".

      Use the drop box to post your answers.