Binary Search Trees

Table of Contents

Adapted from Lenhart and Jannen

1 Reading

Read Algorithms 3.2

2 Video

Here is a video lecture for today's lesson. It's on the longer side, so it's okay if you don't get through the whole thing before Monday's class. The video for Wednesday will be shorter to give you time to catch up.

The video contains sections on

  1. Learning goals (0:09)
  2. Defining a binary search tree (0:53)
  3. Example BSTs (4:28)
  4. Animations of search and insert operations (8:07)
  5. How to handle removing from a BST (12:14)
  6. Animations of removal operations (25:21)
  7. BST implementation (30:52)

The Panopto viewer has table of contents entries for these sections: https://carleton.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=20443fd6-dac0-4d93-87c6-accd0171fcdd

3 Learning Goals

After this lesson you will be able to

  1. Identify when a binary tree meets the definition of a binary search tree
  2. Use a binary search tree to implement the Map ADT
    1. Perform and implement the contains, get, and put operations
    2. Describe the four cases for remove on a binary search tree
  3. Perform and implement firstKey and lastKey operations

4 Defining a Binary Search Tree (BST)

  • Definition: A BST T is either:
    • Empty
    • Has root r with subtrees TL and TR such that
      • All nodes in TL have smaller key than r (or are empty)
      • All nodes in TR have larger key than r (or are empty)
    • TL and TR are also BSTs

4.1 Examples

valid:

bst1.png

valid:

bst2.png

valid:

bst3.png

valid:

bst4.png

valid:

bst5.png

INVALID:

bst6.png

5 BST Operations

5.1 Animations for searching and insertion

https://visualgo.net/en/bst

5.2 Removal

Removing the root is a (not so) special case

  • Let's figure that out first
  • If we can remove the root, we can remove any element in a BST in the same way
    • Every node is the root of a subtree
    • After removing node as root of its own subtree, add subtree back as child of node's parent

bst-remove1.png

bst-remove2.png

bst-remove3.png

5.2.1 Case 4: General Case

  • Consider BST requirements:
    • Left subtree must be <= root
    • Right subtree must be > root
  • Strategy: replace the root with the largest value that is less than or equal to it
    • predecessor(root) : rightmost left descendant
    • Alternatively, could use successor(root): leftmost right descendant
  • This may require reattaching the predecessor's left subtree!

bst-remove4a.png

bst-remove4b.png

5.3 Animations for removal

https://visualgo.net/en/bst

6 Imeplementing a BST

See accomanying BST.java for:

  • BST class
    • inner Node class with key and value
    • implementation of get, contains, and put

7 Practice Problems1

  1. What distinguishes a binary search tree from a binary tree?
  2. Suppose values have only been added into a binary search tree. Where is the first node added to the tree? Where is the last node added to the tree?

  3. Which of the following trees are valid binary search trees?

    (A)

    is-bst1.png

    (B)

    is-bst2.png

    (C)

    is-bst3.png

    (D)

    is-bst4.png

    (E)

    is-bst5.png

  4. For each of the next four problems, draw the binary search tree that would result if the given elements were added to an empty binary search tree in the given order.
    1. Leia, Boba, Darth, R2D2, Han, Luke, Chewy, Jabba
    2. Meg, Stewie, Peter, Joe, Lois, Brian, Quagmire, Cleveland
    3. Kirk, Spock, Scotty, McCoy, Chekov, Uhuru, Sulu, Khaaaan!
    4. Lisa, Bart, Marge, Homer, Maggie, Flanders, Smithers, Milhouse

8 Learning Block

Footnotes:

1

Solutions:

  1. A binary search tree is one that is ordered such that smaller nodes appear to the left and larger nodes appear to the right.
  2. The first node is at the root, the last node is at a leaf.
  3. Valid binary search trees: 2, if duplicates are allowed; 3; and 5.
    1.                       +--------+
                      |  Leia  |
                      +--------+
                  /               \
             /                         \
+--------+                               +--------+
|  Boba  |                               |  R2D2  |
+--------+                               +--------+
         \                                /
          \                              /
     +--------+                    +--------+
     | Darth  |                    |  Luke  |
     +--------+                    +--------+
      /       \
     /         \
 +--------+   +--------+
 | Chewy  |   |  Han   |
 +--------+   +--------+
                    \
                     \
                   +--------+
                   | Jabba  |
                   +--------+

    2.                     +-----+
                    | Meg |
                    +-----+
                  /         \
                /             \
          +-----+             +--------+
          | Joe |             | Stewie |
          +-----+             +--------+
         /      \               /
        /        \             /
+-------+      +------+      +-------+
| Brian |      | Lois |      | Peter |
+-------+      +------+      +-------+
       \                           \
        \                           \
  +-----------+                  +----------+
  | Cleveland |                  | Quagmire |
  +-----------+                  +----------+

    3.                   +------------+
                  |    Kirk    |
                  +------------+
               /                  \
            /                        \
         /                              \
+------------+                      +------------+
|   Chekov   |                      |   Spock    |
+------------+                      +------------+
            \                        /          \
             \                      /            \
              \                    /              \
      +------------+         +------------+   +------------+
      |  Khaaaan!  |         |   Scotty   |   |   Uhuru    |
      +------------+         +------------+   +------------+
                            /                 /
                           /                 /
                          /                 /
                    +------------+   +------------+
                    |   McCoy    |   |    Sulu    |
                    +------------+   +------------+

    4.                   +------------+
                  |    Lisa    |
                  +------------+
               /                  \
            /                        \
         /                              \
+------------+                      +------------+
|    Bart    |                      |   Marge    |
+------------+                      +------------+
              \                    /              \
               \                  /                \
                \                /                  \
         +------------+    +------------+    +------------+
         |    Homer   |    |   Maggie   |    |  Smithers  |
         +------------+    +------------+    +------------+
        /                                      /
       /                                      /
      /                                      /
  +------------+                          +------------+
  |  Flanders  |                          |  Milhouse  |
  +------------+                          +------------+