CS 70

Binary Search Trees (Lookup)

A binary search tree (or BST) is

  • A binary tree, such that
    • For any node, the key in that node is
      • Greater than all keys in the left subtree under that node, and
      • Less than all keys in the right subtree under that node.

Here's one:

BST Lookup

BSTs are built for search. Here's a quick example of finding a key in a BST:

  • LHS Cow speaking

    Now you try!

Give the sequence of nodes visited while searching for the key 35.

As we follow this procedure down the tree, we see the following nodes:

  • Horse speaking

    Hay, this process looks familiar to me…

  • LHS Cow speaking

    Oh, yeah?

  • Horse speaking

    This is like binary search! We start in the “middle” and check which direction we need to go. Then we go to the middle of that half and so on!

  • LHS Cow speaking

    Yes, exactly!

  • RHS Cow speaking

    The name “binary search tree” is very literally descriptive!

  • LHS Cow speaking

    On the one hoof, it is a binary tree that we use for search.

  • RHS Cow speaking

    On the other, it is a tree that lets us (basically) do binary search!

Uses of Binary Search Trees

Binary search trees are used for containers that need to offer efficient INSERT and LOOKUP.

Recall that there are two very common interfaces providing INSERT and LOOKUP,

  • Map: Associates keys to values. Think Python dictionaries.
    • A BST can support this interface by using the key for lookup, but inside the tree node storing both the key and its associated value.
  • Set: Stores a collection of items with no duplicates.
    • A BST can support this interface by treating the items as keys. It can efficiently check membership and avoid inserting duplicates.

So, if you ever find yourself wondering, “What is a BST for, anyway?”, just think of all the ways you've ever used a dictionary or set (and all the ways you could use one in the future) and you'll know what they are for!

  • Duck speaking

    Wait. Did we just demystify a mysterious mystery? Is a Python dictionary a BST?

  • Python speaking

    Actually… no. The encoding for Python dictionaries uses a different structure.

  • LHS Cow speaking

    We'll study that one too, a bit later in the semester! We'll try to remember to let you know when we get there.

  • RHS Cow speaking

    However, C++ has std::map and std::set, both of which are typically implemented using particular kinds of BSTs.

  • Bjarne speaking

    The C++ standard never actually mandates the use of BSTs, but all the complexity guarantees basically ensure that a BST-based implementation is the only option.

(When logged in, completion status appears here.)