Programming Abstractions
CS106B
Cynthia Bailey
Head TA: Tommy DeBenedetti
pollev.com/stanfordcs
Topics:
2
pollev.com/stanfordcs
Binary Search in a Linked List?
EXPLORING A GOOD IDEA, FINDING WAY TO MAKE IT WORK
Recall our beautiful algorithm: binary search!
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
2 | 7 | 8 | 13 | 25 | 29 | 33 | 51 | 89 | 90 | 95 |
Q. Can we do binary search on a linked list?
Let’s brainstorm a wild idea and then see if we can make it work
“What if…?” �The inspiration for Binary Search Trees
data | next |
56 | |
data | next |
24 | |
data | next |
32 | |
_median:
_size:
7
data | next |
40 | |
data | next |
48 | |
data | next |
8 | |
data | next |
16 | |
“What if…?” �The inspiration for Binary Search Trees
data | next |
56 | |
data | next |
24 | |
| | |
| 32 | |
_median:
_size:
7
data | next |
40 | |
data | next |
48 | |
data | next |
8 | |
data | next |
16 | |
An Idealized Binary Search Tree
_root:
_size:
29
Binary Search Trees
IMPLEMENTING THE MAP INTERFACE WITH BINARY SEARCH TREES
The centrality of search for Map interface
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
2 | 7 | 8 | 13 | 25 | 29 | 33 | 51 | 89 | 90 | 95 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
2 | 7 | 8 | 13 | 25 | 29 | 33 | 51 | 89 | 90 | 95 |
"A" | “B+" | "A-" | “B" | “C+" | "A+" | "A-" | "A" | “B-" | "A" | "A" |
The centrality of search for Map interface
_root:
_size:
29
"A"
"B+"
"A-"
"A+"
"B"
Implementing Map interface with a Binary Search Tree (BST)
TreeMap
THIS IS BASICALLY THE SAME AS STANFORD MAP.
HERE IN CLASS WE’LL CALL IT TREEMAP JUST TO BE EXPLICIT ABOUT ITS IMPLEMENTATION.
tree-map.h
template <typename Key, typename Value>
class TreeMap {
public:
TreeMap();
~TreeMap();
bool isEmpty() const;
int size() const;
bool containsKey(const Key& key) const;
void put(const Key& key, const Value& value);
Value get(const Key& key) const;
Value& operator[](const Key& key);
//...(continued on next slide)
tree-map.h
// class TreeMap continued...
private:
struct node {
Key key;
Value value;
node* left;
node* right;
};
int _size;
node* _root;
};
key:
value:
left:
right:
_root:
_size:
TreeMap
node
key:
value:
left:
right:
node
key:
value:
left:
right:
node
BST put()
Pretty simple!
_root:
_size:
29
Question about our BST put() algorithm:
FAQ. What do we do if the key is equal to the node’s key?
Stanford Map example:
Map<int, string> mymap;
mymap.put(5, "five");
mymap.put(5, "cinco"); // what should happen?
cout << mymap.get(5) << endl; // what should print?
Pretty simple!
BST put() algorithm:
BST put()
Insert: 22, 9, 34, 18, 3
Your Turn: How many of these result in the same tree structure as above?
22, 34, 9, 18, 3
22, 18, 9, 3, 34
22, 9, 3, 18, 34
If key > node’s key
Go right! (if doesn’t exist—place here)
If key < node’s key
Go left! (if doesn’t exist—place here)
If key is equal, update value here.
pollev.com/stanfordcs
BST Big-O Performance
WHAT CAN WE EXPECT FROM A BST-BASED MAP?
Your Turn: What is the worst case cost for doing containsKey() in a BST?
pollev.com/stanfordcs
What is the worst case cost for doing containsKey() in a BST if the BST is balanced?
O(logN)—awesome!
BSTs are great when balanced
BSTs are bad when unbalanced
Your Turn: how many worst-case BSTs are there?
One way to create a bad BST is to insert the elements in decreasing order: 34, 22, 9, 3
That’s not the only way…
How many distinctly structured BSTs are there that exhibit the worst case height (worst case is where height equals number of nodes) for a tree with the 4 nodes listed above?
Bonus question: general formula for any BST of size n?
Extra bonus question (CS109): what is this as a fraction of all trees (i.e., probability of worst-case tree).
pollev.com/stanfordcs
BST and Heap quick recap/cheat sheet
IT CAN BE EASY TO GET CONFUSED BETWEEN BST AND HEAP—HERE’S A QUICK GUIDE!
BST and Heap Facts (cheat sheet)
Heap (Priority Queue)
BST (Map)
25