CS61B, 2019
Lecture 16: ADTs and BSTs
● Abstract Data Types
● Binary Search Tree (intro)
● BST Definitions
● BST Operations
● Sets vs. Maps, Summary
datastructur.es
Abstract Data Types
datastructur.es
Interfaces vs. Implementation
In class:
● Developed ALists and SLLists.
● Created an interface List61B.
○ Modified AList and SLList to implement List61B.
○ List61B provided default methods.
In projects:
● Developed ArrayDeque and LinkedListDeque.
● Created an interface Deque.
○ Modified AD and LLD to implement Deque.
AList
SLList
List61B
Deque
Array Deque
LinkedList
Deque
datastructur.es
Interfaces vs. Implementation
With DisjointSets, we saw a much richer set of possible implementations.
ListOfSetsDS QuickFindDS QuickUnionDS
DisjointSets
WeightedQuick
UnionDS
datastructur.es
Abstract Data Types
An Abstract Data Type (ADT) is defined only by its operations, not by its implementation.
Deque
Deque ADT:
● addFirst(Itemx);
● addLast(Itemx);
● booleanisEmpty();
● int size();
● printDeque();
● ItemremoveFirst();
● ItemremoveLast();
● Itemget(intindex);
ArrayDeque and LinkedList Deque are implementations of the Deque ADT.
Array Deque
LinkedList
Deque
datastructur.es
Another example of an ADT: The Stack
The Stack ADT supports the following operations:
● push(int x): Puts x on top of the stack.
● int pop(): Removes and returns the top item from the stack.
piunshe(rtinBatcxk()) getBack()
deleteBack() gpeopt()int i)
2
6
4
datastructur.es
The Stack ADT: yellkey.com/?
The Stack ADT supports the following operations:
● push(int x): Puts x on top of the stack.
● int pop(): Removes and returns the top item from the stack.
Which implementation do you think would result in faster overall performance?
A. Linked List B. Array
piunshe(rtinBatcxk()) getBack()
deleteBack() gpeopt()int i)
4
datastructur.es
The Stack ADT: yellkey.com/?
The Stack ADT supports the following operations:
● push(int x): Puts x on top of the stack.
● int pop(): Removes and returns the top item from the stack
Which implementation do you think would result in faster overall performance?
A. Linked List B. Array
piunshe(rtinBatcxk()) getBack()
deleteBack() gpeopt()int i)
Both are about the same. No resizing for linked lists, so probably a lil faster.
datastructur.es
4
The GrabBag ADT: yellkey.com/?
The GrabBag ADT supports the following operations:
● insert(int x): Inserts x into the grab bag.
● int remove(): Removes a random item from the bag.
● int sample(): Samples a random item from the bag (without removing!)
● int size(): Number of items in the bag.
Which implementation do you think would result in faster overall performance?
A. Linked List B. Array
insert(Biacntk()x) rgetmoBaveck()()
dseamleplteB(a)ck() gseitz(ei(nitnti)i)
datastructur.es
The GrabBag ADT: yellkey.com/?
The GrabBag ADT supports the following operations:
● insert(int x): Inserts x into the grab bag.
● int remove(): Removes a random item from the bag.
● int sample(): Samples a random item from the bag (without removing!)
● int size(): Number of items in the bag.
Which implementation do you think would result in faster overall performance?
A. Linked List
B. Array
insert(Biacntk()x) rgetmoBaveck()()
dseamleplteB(a)ck() gseitz(ei(nitnti)i)
datastructur.es
Abstract Data Types in Java
One thing I particularly like about Java is the syntax differentiation between abstract data types and implementations.
● Note: Interfaces in Java aren’t purely abstract as they can contain some implementation details, e.g. default methods.
Example: List
List
Linked List
ArrayList
datastructur.es
Collections
Among the most important interfaces in the java.util library are those that extend the Collection interface (btw interfaces can extend other interfaces).
● Lists of things.
● Sets of things.
● Mappings between items, e.g. jhug’s grade is 88.4, or Creature c’s north
neighbor is a Plip.
○ Maps also known as associative arrays, associative lists (in Lisp), symbol
tables, dictionaries (in Python).
Collection
List
Set
Map
datastructur.es
Map Example
Maps are very handy tools for all sorts of tasks. Example: Counting words.
Map
“momo”, “no”, “uchi”}; for (String s : text) {
int currentCount = m.getOrDefault(s, 0);
m.put(s, currentCount + 1); }
m = {}
text = [“sumomo”, “mo”, “momo”, “mo”, \
“momo”, “no”, “uchi”] for s in text:
current_count = m.get(s, 0) m[s] = current_count + 1
sumomo
1
mo
2
momo
2
no
1
uchi
1
Python equivalent
datastructur.es
Java Libraries
The built-in java.util package provides a number of useful:
● Interfaces: ADTs (lists, sets, maps, priority queues, etc.) and other stuff.
● Implementations: Concrete classes you can use.
Today, we’ll learn the basic ideas behind the TreeSet and TreeMap.
Collection
List
Set
ArrayList HashSet TreeSet HashMap TreeMap
Map
Linked List
datastructur.es
Binary Search Trees
datastructur.es
Analysis of an OrderedLinkedListSet
In an earlier lecture, we implemented a set based on unordered arrays. For the order linked list set implementation below, name an operation that takes worst case linear time, i.e. Θ(N).
sent
ABCDEFG size contains add iterator
size
7
datastructur.es
Analysis of an OrderedLinkedListSet
In an earlier lecture, we implemented a set based on unordered arrays. For the order linked list set implementation below, name an operation that takes worst case linear time, i.e. Θ(N).
sent
ABCDEFG size contains add iterator
size
7
datastructur.es
Optimization: Extra Links
Fundamental Problem: Slow search, even though it’s in order.
● Add (random) express lanes. Skip List (won’t discuss in 61B)
ABCDEFG
datastructur.es
Optimization: Change the Entry Point
Fundamental Problem: Slow search, even though it’s in order. ● Move pointer to middle.
ABCDEFG
datastructur.es
Optimization: Change the Entry Point, Flip Links
Fundamental Problem: Slow search, even though it’s in order.
● Move pointer to middle and flip left links. Halved search time!
ABCDEFG
datastructur.es
Optimization: Change the Entry Point, Flip Links
Fundamental Problem: Slow search, even though it’s in order.
● How do we do even better?
● Dream big! ABCDEFG
datastructur.es
Optimization: Change Entry Point, Flip Links, Allow Big Jumps
Fundamental Problem: Slow search, even though it’s in order. ● How do we do better?
ABCDEFG
D B
ACEG
F
datastructur.es
BST Definitions
datastructur.es
Tree
A tree consists of:
● A set of nodes.
● A set of edges that connect those nodes.
○ Constraint: There is exactly one path between any two nodes. Green structures below are trees. Pink ones are not.
datastructur.es
Rooted Trees and Rooted Binary Trees
In a rooted tree, we call one node the root.
● Every node N except the root has exactly one parent, defined as the first node on the path from N to the root.
● Unlike (most) real trees, the root is usually depicted at the top of the tree.
● A node with no child is called a leaf.
In a rooted binary tree, every node has either 0, 1, or 2 children (subtrees).
AA
A
BB
For each of these:
● A is the root.
● B is a child of A.
● A is a parent of B.
(and C of B) (and B of C)
B
C
C C C
Not binary!
datastructur.es
Binary Search Trees
A binary search tree is a rooted binary tree with the BST property. BST Property. For every node X in the tree:
● ●
Every key in the left subtree is less than X’s key. Every key in the right subtree is greater than X’s key.
dog
debt
bag
flat
bus
ears
alf
cat
elf
cow
fish
glut axe
Binary Tree, but not a Binary Search Tree
gut
Binary Search Tree
datastructur.es
Binary Search Trees
Ordering must be complete, transitive, and antisymmetric. Given keys p and q: ● Exactly one of p ≺ q and q ≺ p are true.
● p ≺ q and q ≺ r imply p ≺ r.
One consequence of these rules: No duplicate keys allowed!
●
Keeps things simple. Most real world implementations follow this rule.
dog
debt
bag
flat
bus
ears
alf
cat
elf
cow
fish
glut axe
Binary Tree, but not a Binary Search Tree
gut
Binary Search Tree
datastructur.es
BST Operations: Search
datastructur.es
Finding a searchKey in a BST (come back to this for the BST lab)
If searchKey equals T.key, return.
● If searchKey ≺ T.key, search T.left.
● If searchKey ≻ T.key, search T.right.
dog
bag
flat
alf
cat
elf
glut
datastructur.es
Finding a searchKey in a BST
If searchKey equals T.key, return.
● If searchKey ≺ T.key, search T.left.
● If searchKey ≻ T.key, search T.right.
dog
bag
cat
flat
static BST find(BST T, Key sk) { if (T == null)
return null;
if (sk.equals(T.key))
return T;
else if (sk ≺ T.key)
return find(T.left, sk); else
return find(T.right, sk);
}
alf
elf
glut
datastructur.es
BST Search: http://yellkey.com/?
What is the runtime to complete a search on a “bushy” BST in the worst case,
where N is the number of nodes.
A. Θ(log N)
B. Θ(N)
C. Θ(N log N)
D. Θ(N2)
E. Θ(2N)
“bushiness” is an intuitive concept that we haven’t defined.
datastructur.es
BST Search
What is the runtime to complete a search on a “bushy” BST in the worst case, where N is the number of nodes.
A. Θ(log N)
Height of the tree is ~log2(N)
datastructur.es
BSTs
Bushy BSTs are extremely fast.
● At 1 microsecond per operation, can find something from a tree of size 10300000 in one second.
Much (perhaps most?) computation is dedicated towards finding things in response to queries.
● It’s a good thing that we can do such queries almost for free.
datastructur.es
BST Operations: Insert
datastructur.es
Inserting a New Key into a BST
Search for key.
● If found, do nothing.
● If not found:
○ Create new node.
○ Set appropriate link.
Example:
insert “eyes”
dog
bag
flat
alf
cat
elf
glut
datastructur.es
Inserting a New Key into a BST
Search for key.
● If found, do nothing.
● If not found:
○ Create new node.
○ Set appropriate link.
dog
bag
cat
flat
elf
glut
ARMS LENGTH RECURSION!!!! No good.
eyes
A common rookie bad habit to avoid:
if (T.left == null) T.left = new BST(ik);
else if (T.right == null)
T.right = new BST(ik); datastructur.es
alf
static BST insert(BST T, Key ik) { if (T == null)
return new BST(ik); if (ik ≺ T.key)
T.left = insert(T.left, ik); else if (ik ≻ T.key)
T.right = insert(T.right, ik); return T;
}
BST Operations: Delete
datastructur.es
Deleting from a BST
3 Cases:
● Deletion key has no children.
● Deletion key has one child.
● Deletion key has two children.
dog
bag
flat
alf
cat
elf
glut
eyes
datastructur.es
Case 1: Deleting from a BST: Key with no Children
Deletion key has no children (“glut”):
● Just sever the parent’s link.
● What happens to “glut” node?
dog
bag
flat
alf
cat
elf
glut
eyes
datastructur.es
Case 1: Deleting from a BST: Key with no Children
Deletion key has no children (“glut”):
● Just sever the parent’s link.
● What happens to “glut” node?
○ Garbage collected.
dog
bag
flat
alf
cat
elf
glut
eyes
datastructur.es
Case 2: Deleting from a BST: Key with one Child
Example: delete(“flat”):
dog
bag alf
flat
Goal:
● Maintain BST property.
● Flat’s child definitely larger than dog.
cat
elf
○ Safe to just move that child into flat’s spot. Thus: Move flat’s parent’s pointer to flat’s child.
eyes
datastructur.es
Case 2: Deleting from a BST: Key with one Child
Example: delete(“flat”):
dog
Goal:
● Maintain BST property.
● Flat’s child definitely larger than dog.
bag
alf cat
flat
elf
eyes
○ Safe to just move that child into flat’s spot.
Thus: Move flat’s parent’s pointer to flat’s child.
● Flat will be garbage collected (along with its instance variables).
datastructur.es
Hard Challenge
Delete k.
k
ev
bgpy
adf m
rxz
datastructur.es
Hard Challenge
Delete k.
k
ev
bgpy
adf m
rxz
datastructur.es
Case 3: Deleting from a BST: Deletion with two Children (Hibbard)
Example: delete(“dog”)
dog
bag
flat
Goal:
● Find a new root node.
● Must be > than everything in left subtree.
● Must be < than everything right subtree.
Would bag work?
alf
cat
elf
glut
eyes
datastructur.es
Case 3: Deleting from a BST: Deletion with two Children (Hibbard)
Example: delete(“dog”)
dog
Goal:
● Find a new root node.
● Must be > than everything in left subtree.
● Must be < than everything right subtree.
bag
alf cat
flat
elf glut
eyes
Choose either predecessor (“cat”) or successor (“elf”).
● Delete “cat” or “elf”, and stick new copy in the root position: ○ This deletion guaranteed to be either case 1 or 2. Why?
● This strategy is sometimes known as “Hibbard deletion”.
datastructur.es
Hard Challenge (Hopefully Now Easy)
Delete k.
k
ev
bgpy
adf m
rxz
datastructur.es
Hard Challenge (Hopefully Now Easy)
Delete k. Two solutions: Either promote g or m to be in the root. ● Below, solution for g is shown.
k
ev
bgpy
adf m
rxz
datastructur.es
Hard Challenge (Hopefully Now Easy)
Two solutions: Either promote g or m to be in the root. ● Below, solution for g is shown.
g
ev
bfpy
adm
rxz
datastructur.es
Sets vs. Maps, Summary
datastructur.es
Sets vs. Maps
Can think of the BST below as representing a Set: ● {mo, no, sumomo, uchi, momo}
sumomo
mo
momo
no
uchi
sumomo
momo
uchi
mo
no
datastructur.es
Sets vs. Maps
Can think of the BST below as representing a Set: ● {mo, no, sumomo, uchi, momo}
sumomo
momo
uchi
sumomo
mo
momo
no
uchi
mo
no
But what if we wanted to represent a mapping of word counts?
????
sumomo
mo
momo
no
uchi
1
2
2
1
1
datastructur.es
Sets vs. Maps
To represent maps, just have each BST node store key/value pairs.
sumomo
1
mo
2
momo
2
no
1
uchi
1
sumomo
1
momo
2
uchi
1
mo
2
no
2
Note: No efficient way to look up by value.
● Example: Cannot find all the keys with value = 1 without iterating over ALL nodes. This is fine.
datastructur.es
Summary
Abstract data types (ADTs) are defined in terms of operations, not implementation. Several useful ADTs: Disjoint Sets, Map, Set, List.
● Java provides Map, Set, List interfaces, along with several implementations. We’ve seen two ways to implement a Set (or Map): ArraySet and using a BST.
● ArraySet: Θ(N) operations in the worst case.
● BST: Θ(log N) operations in the worst case if tree is balanced.
BST Implementations:
● Search and insert are straightforward (but insert is a little tricky).
● Deletion is more challenging. Typical approach is “Hibbard deletion”.
datastructur.es
BST Implementation Tips
datastructur.es
Tips for BST Lab
● Code from class was “naked recursion”. Your BSTMap will not be.
● For each public method, e.g. put(K key, V value), create a private
recursive method, e.g. put(K key, V value, Node n)
● When inserting, always set left/right pointers, even if nothing is actually
changing.
● Avoid “arms length base cases”. Don’t check if left or right is null!
Avoid “arms length base cases”.
if (T.left == null) T.left = new BST(ik);
else if (T.right == null)
T.right = new BST(ik); datastructur.es
static BST insert(BST T, Key ik) { if (T == null)
return new BST(ik); if (ik ≺ T.label()))
T.left = insert(T.left, ik); else if (ik ≻ T.label())
T.right = insert(T.right, ik);
return T; }
Always set, even if nothing changes!
Citations
Probably photoshopped binary tree: http://cs.au.dk/~danvy/binaries.html
datastructur.es