This Week

• 1
  Binary search as a shape
• 2
  The BST property
• 3
  insert, contains, traversals
• 4
  Shape decides everything KEY
• 5
  remove: the three cases
• 6
  The STL set and map
• 7
  Choosing a container

Seven Guesses

I'm thinking of a number between 1 and 128. You get seven guesses.

• Guessing at random: under a 6% chance
• Trying 1, 2, 3, … up to 128 guesses
• Guessing the middle each time: always wins, in 7

What If the Structure Did the Halving?

A sorted array gives fast search but slow insertion. A linked list gives fast insertion but no halving.

Tree Vocabulary

The BST Property

Two Classes Again

class Node {
  Item  myItem;
  Node *myLeft;
  Node *myRight;
};
      

class BST {
 public:
  void insert(Item it);
  bool contains(Item it);
 private:
  Node *myRoot;
  unsigned mySize;
};
      

insert

void Node::insert(Item it) {
    if (it < myItem) {
        if (myLeft == nullptr) { myLeft = new Node(it); }
        else                   { myLeft->insert(it); }
    } else {
        if (myRight == nullptr) { myRight = new Node(it); }
        else                    { myRight->insert(it); }
    }
}
  

• A. 21, 36, 42, 57, 63, 84, 91
• B. 57, 36, 84, 21, 42, 63, 91
• C. 91, 84, 63, 57, 42, 36, 21
• D. 36, 21, 42, 57, 84, 63, 91

find / contains

bool Node::contains(Item it) const {
    if (it == myItem) { return true; }
    if (it < myItem) {
        return myLeft  != nullptr && myLeft->contains(it);
    }
    return myRight != nullptr && myRight->contains(it);
}
  

Shape Decides Everything

Traversals

• A. Pre-order, delete the root first
• B. In-order, delete in sorted order
• C. Post-order, delete both children before the node
• D. Any of them

Height

int Node::height() const {
    int leftH  = (myLeft  == nullptr) ? -1 : myLeft->height();
    int rightH = (myRight == nullptr) ? -1 : myRight->height();
    return 1 + max(leftH, rightH);
}
  

• An empty tree has height −1; a single node, 0
• Computing it costs O(n): you have to visit everything
• A full tree of height h holds 2^(h+1) − 1 nodes

remove: Three Cases

• A leaf: unlink it from its parent and delete. Easy.
• One child: hand the child up to the parent. Also easy.
• Two children: you can't just remove it; something must take its place.

• A. 36, the left child
• B. 84, the right child
• C. 42, the largest value in the left subtree
• D. 21, the smallest value in the tree

Where BSTs Stand

You Built These by Hand

Dynamic array, linked list, stack, queue, binary search tree, self-balancing tree. The STL ships all of them.

set: Unique, Sorted, Fast

#include <set>

set<string> enrolled;

enrolled.insert("ada");
enrolled.insert("grace");
enrolled.insert("ada");        // ignored: already there

cout << enrolled.size();       // 2
cout << enrolled.count("ada"); // 1  (0 or 1, never more)
  

What's Underneath

Iterating

for (const string &name : enrolled) {      // sorted order
    cout << name << endl;
}

set<string>::iterator it = enrolled.find("ada");
if (it != enrolled.end()) {
    cout << *it << " is enrolled" << endl;
}
  

set<int> s;
s.insert(7);
s.insert(3);
s.insert(7);
s.insert(9);
cout << s.size();
    

• A. 3
• B. 4
• C. 2
• D. It won't compile

map: Keys to Values

#include <map>

map<string, int> scores;

scores["ada"]   = 95;
scores["grace"] = 98;

cout << scores["ada"];        // 95
cout << scores.size();        // 2
  

Walking a map

for (const auto &entry : scores) {
    cout << entry.first << ": " << entry.second << endl;
}

// ada: 95
// grace: 98        ← always in key order
  

map<string, int> scores;
scores["ada"] = 95;

if (scores["bob"] > 90) {     // just a lookup?
    cout << "bob did well";
}
cout << scores.size();
    

• A. 1
• B. 2
• C. 0
• D. It throws an exception

The [] Trap

m["missing"]     // creates it!
      

m.count("missing")
m.find("missing") != m.end()
      

A Word Counter

map<string, int> counts;
string word;

while (fin >> word) {
    ++counts[word];        // creates it at 0, then increments
}

for (const auto &entry : counts) {
    cout << entry.first << " " << entry.second << endl;
}
  

Ordered or Unordered?

Choosing a Container

• Index by position, mostly appending → vector
• Constant insert/remove at the ends → deque, stack, queue
• Membership, no duplicates, sorted → set
• Key to value, sorted keys → map
• Membership or lookup as fast as possible, order irrelevant → unordered_*