~~Assignment Implement a skip list as a genericized SkipListSet
Programming Project
COP3503 Computer Science II – Summer 2023
Assignment
Implement a skip list as a genericized SkipListSet collection in Java. Your class must implement SortedSet
(and hence Set, Collection and Iterable).
A program that has your class available will be able to instantiate a SkipListSet for any Comparable class, and treat
it like any other sorted collection (as long as it uses classes with a natural order).
Structure
You’ll create three things: a set class, an iterator class, and an item-wrapper (node) class. You’ll almost certainly want to
make the iterator and item-wrapper classes internal private classes of the set class. I’ll call the iterator and itemwrapper classes SkipListSetIterator and SkipListSetItem, but you can call them anything you like.
SortedSet is a Java interface. That means it specifies a set of methods that you must implement to make it work. Your
SkipListSet will implement it.
What this means is you’re not calling methods from SortedSet yourself – you’re writing them, so that a program that
wants to use your SkipListSet can work with it the same way it would any other SortedSet, like TreeSet.
Likewise, Iterator is another Java interface. Your SkipListSetIterator will implement the methods that it
requires.
Long ago in Java programming, iterators were important constructs to use directly, but enhanced-for syntax eliminates
nearly all need to use them explicitly. Once you create your SkipListSetIterator, and implement your
SortedSet’s iterator() method, you can immediately use Java enhanced-for syntax on your SkipListSet.
SortedSet
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
add
addAll
clear
comparator
contains
containsAll
equals
first
hashCode
headSet
isEmpty
iterator
last
remove
removeAll
retainAll
size
subSet
tailSet
toArray
SkipListSet
Implemented By
implements SortedSet
iterator()
method
SkipListSetIterator
Iterator
•
•
•
Implemented By
implements Iterator
Returns
…Item
•Links
•Payload
•Iterates over items
•Returns payloads, not item wrappers
Payload Item Objects
implement Comparable (otherwise, can be anything)
Inserted via SortedSet interface into SkipListSet
Encased in SkipListSetItems
hasNext
Next
Remove
Implementing a Skip List
A skip list is a special linked list. To start with that means your item-wrapper class needs a link to the right like an
ordinary linked list (and you will almost certainly want a link to the left as well).
Working with links in Java is, overall, relatively easy.
•
•
•
All non-primitive parameters in Java are passed by reference as default, so you don’t need to worry about
pointers at all.
Java is a mostly garbage collected language, so to delete list items, all you have to do is “lose” them – nullify all
your references to them, and they’ll go away.
This means that to clear your list, all you need to do is nullify your head and tail pointers, set any internal size
indicators back to zero or default, and let the garbage collector handle the rest.
A skip list is a two-dimensional linked list, so your items will need links vertically as well as horizontally. You can do this
two ways:
•
A true two-dimensional linked list structure, with links upward (and likely downward) from item wrappers either
to other item wrappers or to an abbreviated “node hat” class that has only pointers and no payload. This is
probably more efficient.
An ArrayList of pointers to the right (and possibly to the left) inside each wrapper item. This is probably
easier to implement.
o (A primitive array would actually be ideal, but primitive arrays don’t deal well with generics.)
•
No matter how you deal with the vertical dimension, you will need ways to:
•
Find and traverse to the location of where an item is or could/should be in your skip list.
o This should leverage the verticality of the skip list to be 𝒪(log 𝑛).
o All of the methods for addition, removal and containment check will probably reference this.
o This will be distinct from your SkipListSetIterator class. More on this below.
Add and delete items, and restore the left/right pointers across the whole verticality of the list.
Shrink and grow items without breaking everything.
Re-balance the list.
•
•
•
Remember that an instantiation of your item-wrapper class wraps an item, it is not an item itself. This has three
important implications:
•
•
•
When you’re comparing items for traversal or containment checks, you want to compare the wrapped payload
items, not the objects of your item wrapper class. Make sure you pass compareTo() through to the wrapped
payload items.
Your traversal function will be separate from your SkipListSetIterator. The traversal function works with
the item wrappers that you need to deal with internally, while the iterator returns the payload items that the
user of the skip list wants.
If the user ever sees an item wrapper – that is, if an object of your SkipListSetItem class ever gets out of
your list – something has gone wrong.
Working with Generics
https://docs.oracle.com/javase/tutorial/java/generics/index.html has extensive documentation about generics. Reading
this document will help with a lot of questions on generics, and will show you several patterns you can try for individual
functions.
My own implementation uses the following patterns to declare the set and its iterator, which you may free to copy:
public class SkipListSet implements SortedSet
private class SkipListSetIterator implements Iterator
You may suppress unchecked cast warnings for contains(), remove() and the typed version of toArray() – these
methods all insist on accepting Objects, and the amount of work you’d need to do with the Reflection APIs to avoid
warnings isn’t worth it.
It should be possible to get the compiler happy with all the other methods. If a method is being particularly stubborn
about generating warnings, feel free to ask the Teaching Assistants, or me, about it.
Algorithmic Specifics
•
•
•
•
You can require that list items implement Comparable.
o This means that you can compare your list items against each other by simply using their internal
compareTo() methods.
Randomize the height of the list items rather than using logarithm boundaries. 50% chance of being height 2,
25% chance of being height 3, etc.
Implement a reBalance() method to re-randomize the height of all list items. Don’t call this automatically.
Figure out when and how to grow and shrink the maximum height of list items. (Hint: Powers of 2, and set a
minimum so you don’t have silly thrashing on small lists.) Expect this to be a pain in the neck and don’t leave it
for the last minute.
Implementation Checklist
You’ll need to write:
•
•
•
A SkipListSet class implementing SortedSet, Set, Iterable and Collection, described below.
A SkipListSetIterator internal class implementing Iterator, described further below.
A SkipListSetItem internal class implemented however you wish
Constructors
•
•
•
Your SkipListSet class will need a constructor accepting no arguments, which returns an empty skip list; and
a constructor accepting a Collection as an argument, which returns a new SkipListSet containing all the
elements from the Collection.
You don’t need the other two recommended constructors from the Java collections documentation, since you
may require your list items to implement Comparable.
The constructors for your iterator and item classes can work however you want, since they’re internal.
Methods from SortedSet:
•
•
•
•
first and last
headSet, subSet, and tailSet, but these can simply throw UnsupportedOperationException() and do
nothing else
comparator, but it can return null
You don’t have to implement spliterator, since it has a default implementation
Methods from Set:
•
•
add, addAll, clear, contains, containsAll, equals, hashCode, isEmpty, iterator, remove,
removeAll, retainAll, size, toArray (both versions)
You don’t have to implement spliterator, since it has a default implementation
Methods from Iterable:
•
You don’t need to do anything here – you’re already implementing iterator for Set, and forEach and
spliterator both have default implementations
Methods from Collection:
•
You don’t need to do anything here – you’re already implementing iterator for Set, and
parallelStream, removeIf, spliterator and stream all have default implementations
Your SkipListSetIterator will need to implement, from Iterator:
•
•
•
hasNext, next, remove
You do have to implement remove even though it has a default implementation, because its default
implementation just throws an exception
You do not have to implement forEachRemaining, because its default implementation works
Testing, Structure and Boundaries
Your SkipListSet class shouldn’t have a main() function. Instead, create another class for testing that does have
a main, instantiates a SkipListSet and throws items at it – or work with my test harness class, and modify it however
you see fit. I’ll provide test cases later in the semester.
Your collection doesn’t have to be thread-safe. It does have to work at scale – the test harness will throw a few million
entries at it.
Restrictions
You may use the basic Java collections internally, but you may not use ConcurrentSkipListSet or any other existing
Java skip list.
Code Conventions
In general, follow the Google Java Style Guide, with two relaxed restrictions:
•
•
I don’t care how many spaces you indent by as long as it’s something reasonable.
You don’t have to use JavaDoc for methods, as long as your method comments clearly describe what the
method does, what it returns, and what each parameter is for.
Submitting
Submit your code to Webcourses as a single .java file.
Recursion and Merge
Sort
COP3503 COMPUTER SCIENCE II
DR. MATTHEW B. GERBER
PORTIONS FROM SEAN SZUMLANSKI, MICHAEL MCALPIN,
WIKIPEDIA, WOLFRAM MATHWORLD
Recursion
◦ Recursion is one of the most powerful problem-solving patterns
◦ It maps directly to induction
Patterns of Recursion
int simpleRecurse(int n) {
if(n == 0) {
return base();
} else {
return step(simpleRecurse(n-1));
}
}
Patterns of Recursion
int power(int p, int n) {
if(n == 0) {
return 1;
} else {
return p * power(p, n-1);
}
}
Recursion
◦ Recursion is one of the most powerful problem-solving patterns
◦ It maps directly to induction
◦ Recursion provides a straightforward pattern for applying the base and composite cases of problems
◦ It’s not limited to simple mathematical functions
Patterns of Recursion
type dataRecurse(type[] stuff) {
int l = stuff.lastElementIndex();
if(l == 0) {
return base(stuff[0]);
} else {
type rec = dataRecurse(stuff[0..l-1]);
return compose(rec, stuff[l]);
}
}
Patterns of Recursion
float productOfValues(float[] values) {
int l = values.lastElementIndex();
if(l == 0) {
return values[0];
} else {
float prevProd = productOfValues(values[0..l-1]);
return prevProd * values[l];
}
}
Recursion
◦ Recursion is one of the most powerful problem-solving patterns
◦ It maps directly to induction
◦ Recursion provides a straightforward pattern for applying the base and composite cases of problems
◦ It’s not limited to simple mathematical functions
◦ Recursion is often not the most efficient way to implement things, even those that could be
implemented by recursion…
Iterative Alternatives
int power(int p, int n) {
int ret = 1;
for(i = 1..p) {
ret = ret * n;
}
return ret;
}
Patterns of Recursion
float productOfValues(float[] values) {
int ret = values[0];
for(i = 1..values.lastElementIndex) {
ret = ret * values[i];
}
return ret;
}
Recursion
◦ Recursion is one of the most powerful problem-solving patterns
◦ It maps directly to induction
◦ Recursion provides a straightforward pattern for applying the base and composite cases of problems
◦ It’s not limited to simple mathematical functions
◦ Recursion is often not the most efficient way to implement things, even those that could be
implemented by recursion…
◦ But it’s sometimes more elegant and/or understandable
◦ It’s not unusual to write a recursive algorithm, then work through an iterative implementation
◦ Especially if what you’re doing is particularly mathy
Recursion
◦ Recursion is one of the most powerful problem-solving patterns
◦ It maps directly to induction
◦ Recursion provides a straightforward pattern for applying the base and composite cases of problems
◦ It’s not limited to simple mathematical functions
◦ Recursion is often not the most efficient way to implement things, even those that could be
implemented by recursion…
◦ But it’s sometimes more elegant and/or understandable
◦ It’s not unusual to write a recursive algorithm, then work through an iterative implementation
◦ Especially if what you’re doing is particularly mathy
◦ And sometimes, it is quite efficient in and of itself
Patterns of Recursion
type binaryRecurse(type[] stuff) {
int c = stuff.count();
if(c == 1) {
return base(stuff[0]);
} else {
int last = c – 1;
int splitLeft = floor(c/2) – 1;
int splitRight = splitLeft + 1;
return compose(binaryRecurse(stuff[0..splitLeft]),
binaryRecurse(stuff[splitRight..last]));
}
}
Merge Sort Sort
record[] mergeSort(record[] list) {
int c = list.count();
if(c == 1) {
return list[0];
} else {
int last = c – 1;
int splitLeft = floor(c/2) – 1;
int splitRight = splitLeft + 1;
return merge(mergeSort(list[0..splitLeft]),
mergeSort(list[splitRight..last]));
}
}
Merge Sort
record[] merge(record[] left, record[] right) {
int total = left.count() + right.count();
record[] merged = new record[total];
int m = 0, l = 0, r = 0;
while(m < total) {
if(l == left.count()) {
merged[m] = right[r];
r = r + 1;
} else if(r == right.count() or left[l].key < right[r].key) {
merged[m] = left[l];
l = l + 1;
} else {
merged[m] = right[r];
r = r + 1;
}
m = m + 1;
}
}
Analyzing Merge Sort
◦ Merge is 𝒪(𝑛).
Analyzing Merge Sort
◦ Merge is 𝒪(𝑛).
◦ In fact, merge is Θ 𝑛 .
Analyzing Merge Sort
◦ Merge is 𝒪(𝑛).
◦ In fact, merge is Θ 𝑛 .
◦ Now: How many times are we going to merge the whole list?
Analyzing Merge Sort
◦ Merge is 𝒪(𝑛).
◦ In fact, merge is Θ 𝑛 .
◦ Now: How many times are we going to merge the whole list?
◦ log 𝑛 times. Always log 𝑛 times. Exactly log 𝑛 times.
Analyzing Merge Sort
◦ Merge is 𝒪(𝑛).
◦ In fact, merge is Θ 𝑛 .
◦ Now: How many times are we going to merge the whole list?
◦ log 𝑛 times. Always log 𝑛 times. Exactly log 𝑛 times.
◦ So merge sort takes Θ(𝑛 log 𝑛).
Analyzing Merge Sort
◦ Merge is 𝒪(𝑛).
◦ In fact, merge is Θ 𝑛 .
◦ Now: How many times are we going to merge the whole list?
◦ log 𝑛 times. Always log 𝑛 times. Exactly log 𝑛 times.
◦ So merge sort takes Θ(𝑛 log 𝑛).
◦ It’s a wonderfully predictable algorithm.
Analyzing Merge Sort
◦ Merge is 𝒪(𝑛).
◦ In fact, merge is Θ 𝑛 .
◦ Now: How many times are we going to merge the whole list?
◦ log 𝑛 times. Always log 𝑛 times. Exactly log 𝑛 times.
◦ So merge sort takes Θ(𝑛 log 𝑛).
◦ It’s a wonderfully predictable algorithm.
◦ It’s a horribly optimized algorithm.
Merge Sort Merge
record[] merge(record[] left, record[] right) {
int total = left.count() + right.count();
record[] merged = new record[total];
int m = 0, l = 0, r = 0;
while(m < total) {
if(l == left.count()) {
merged[m] = right[r];
r = r + 1;
} else if(r == right.count() or left[l].key < right[r].key) {
merged[m] = left[l];
l = l + 1;
} else {
merged[m] = right[r];
r = r + 1;
}
m = m + 1;
}
}
Merge Sort Merge
record[] merge(record[] left, record[] right) {
int total = left.count() + right.count();
record[] merged = new record[total];
int m = 0, l = 0, r = 0;
while(m < total) {
if(l == left.count()) {
merged[m] = right[r];
r = r + 1;
This is 𝒪 𝑛 …
but it’s a really
messy 𝒪 𝑛
} else if(r == right.count() or left[l].key < right[r].key) {
merged[m] = left[l];
l = l + 1;
} else {
merged[m] = right[r];
r = r + 1;
}
m = m + 1;
}
}
Merge Sort Sort
record[] mergeSort(record[] list) {
int c = list.count();
if(c == 1) {
return list[0];
} else {
int last = c – 1;
int splitLeft = floor(c/2) - 1;
int splitRight = splitLeft + 1;
return merge(mergeSort(list[0..splitLeft]),
mergeSort(list[splitRight..last]));
}
}
Merge Sort Sort
record[] mergeSort(record[] list) {
int c = list.count();
if(c == 1) {
return list[0];
} else {
int last = c – 1;
int splitLeft = floor(c/2) - 1;
int splitRight = splitLeft + 1;
return merge(mergeSort(list[0..splitLeft]),
mergeSort(list[splitRight..last]));
}
}
…and this involves
a lot of bookkeeping
Analyzing Merge Sort
◦ Merge is 𝒪(𝑛).
◦ In fact, merge is Θ 𝑛 .
◦ Now: How many times are we going to merge the whole list?
◦ log 𝑛 times. Always log 𝑛 times. Exactly log 𝑛 times.
◦ So merge sort takes Θ(𝑛 log 𝑛).
◦ It’s a wonderfully predictable algorithm.
◦ It’s a horribly optimized algorithm.
◦ Merge sort has a ton of overhead.
◦ The iterative version is a bit better…
◦ …and implementing it is like juggling knives.
Analyzing Merge Sort
◦ Merge is 𝒪(𝑛).
◦ In fact, merge is Θ 𝑛 .
◦ Now: How many times are we going to merge the whole list?
◦ log 𝑛 times. Always log 𝑛 times. Exactly log 𝑛 times.
◦ So merge sort takes Θ(𝑛 log 𝑛).
◦ It’s a wonderfully predictable algorithm.
◦ It’s a horribly optimized algorithm.
◦ Merge sort has a ton of overhead.
◦ The iterative version is a bit better…
◦ …and implementing it is like juggling knives.
◦ But we can reduce this overhead!
Merge Sort Sort
record[] mergeSort(record[] list) {
int c = list.count();
if(c == 1) {
return list[0];
} else {
int last = c – 1;
int splitLeft = floor(c/2) - 1;
int splitRight = splitLeft + 1;
return merge(mergeSort(list[0..splitLeft]),
mergeSort(list[splitRight..last]));
}
}
Better Merge Sort Sort
record[] mergeSort(record[] list) {
int c = list.count();
if(c < SORT_SHIFT) {
return smallerSort(list);
} else {
int last = c – 1;
int splitLeft = floor(c/2) - 1;
int splitRight = splitLeft + 1;
return merge(mergeSort(list[0..splitLeft]),
mergeSort(list[splitRight..last]));
}
}
Analyzing Merge Sort
◦ Merge is 𝒪(𝑛).
◦ In fact, merge is Θ 𝑛 .
◦ Now: How many times are we going to merge the whole list?
◦ log 𝑛 times. Always log 𝑛 times. Exactly log 𝑛 times.
◦ So merge sort takes Θ(𝑛 log 𝑛).
◦ It’s a wonderfully predictable algorithm.
◦ It’s a horribly optimized algorithm.
◦ Merge sort has a ton of overhead.
◦ The iterative version is a bit better…
◦ …and implementing it is like juggling knives.
◦ But we can reduce this overhead!
◦ We use a simpler sort when we drop below an array of certain size.
◦ This greatly reduces the overhead at the small-array level…
Analyzing Merge Sort
◦ Merge is 𝒪(𝑛).
◦ In fact, merge is Θ 𝑛 .
◦ Now: How many times are we going to merge the whole list?
◦ log 𝑛 times. Always log 𝑛 times. Exactly log 𝑛 times.
◦ So merge sort takes Θ(𝑛 log 𝑛).
◦ It’s a wonderfully predictable algorithm.
◦ It’s a horribly optimized algorithm.
◦ Merge sort has a ton of overhead.
◦ The iterative version is a bit better…
◦ …and implementing it is like juggling knives.
◦ But we can reduce this overhead!
◦ We use a simpler sort when we drop below an array of certain size.
◦ This greatly reduces the overhead at the small-array level…
◦ And doesn’t increase our asymptotic run time. Do you see why?
Radix and Bucket Sorts
COP3503 COMPUTER SCIENCE II
DR. MATTHEW B. GERBER
PORTIONS FROM SEAN SZUMLANSKI, MICHAEL MCALPIN,
WIKIPEDIA, WOLFRAM MATHWORLD
Sorting Limitations
◦ We can’t do better for sorting than 𝒪(𝑛 log 𝑛)…
Sorting Limitations
◦ We can’t do better for sorting than 𝒪(𝑛 log 𝑛)…
◦ …in the general case
Sorting Limitations
◦ We can’t do better for sorting than 𝒪(𝑛 log 𝑛)…
◦ …in the general case
◦ More specifically, we can’t do better than that in the case where we have to rely on
comparisons
Sorting Limitations
◦ We can’t do better for sorting than 𝒪(𝑛 log 𝑛)…
◦ …in the general case
◦ More specifically, we can’t do better than that in the case where we have to rely on
comparisons
◦ (Which is the general case of sorting)
Sorting Limitations
◦ We can’t do better for sorting than 𝒪(𝑛 log 𝑛)…
◦ …in the general case
◦ More specifically, we can’t do better than that in the case where we have to rely on
comparisons
◦ (Which is the general case of sorting)
◦ But what if we don’t have to rely on comparisons – at least, not fully?
Sorting Limitations
◦ We can’t do better for sorting than 𝒪(𝑛 log 𝑛)…
◦ …in the general case
◦ More specifically, we can’t do better than that in the case where we have to rely on
comparisons
◦ (Which is the general case of sorting)
◦ But what if we don’t have to rely on comparisons – at least, not fully?
◦ There are cases where we already know things about our input
Sorting Limitations
◦ We can’t do better for sorting than 𝒪(𝑛 log 𝑛)…
◦ …in the general case
◦ More specifically, we can’t do better than that in the case where we have to rely on
comparisons
◦ (Which is the general case of sorting)
◦ But what if we don’t have to rely on comparisons – at least, not fully?
◦ There are cases where we already know things about our input
◦ Like, say, “our input is in decimal digits”
Sorting Limitations
◦ We can’t do better for sorting than 𝒪(𝑛 log 𝑛)…
◦ …in the general case
◦ More specifically, we can’t do better than that in the case where we have to rely on
comparisons
◦ (Which is the general case of sorting)
◦ But what if we don’t have to rely on comparisons – at least, not fully?
◦ There are cases where we already know things about our input
◦ Like, say, “our input is in decimal digits”
◦ Can we do better than that then?
Counting Sort
Counting Sort
◦ This kind of sort works well when you have a
really small possible number of values
◦ Like, say, “0 through 9”
Counting Sort
◦ This kind of sort works well when you have a
really small possible number of values
◦ Like, say, “0 through 9”
◦ Go through the list and count how many of each
value you have
0
1
2
3
4
5
6
7
8
9
5
8
2
5
8
0
2
1
7
3
Counting Sort
◦ This kind of sort works well when you have a
really small possible number of values
◦ Like, say, “0 through 9”
◦ Go through the list and count how many of each
value you have
◦ Now go through the value set and turn it into a
running total
0
1
2
3
4
5
6
7
8
9
5
8
2
5
8
0
2
1
7
3
Counting Sort
◦ This kind of sort works well when you have a
really small possible number of values
◦ Like, say, “0 through 9”
◦ Go through the list and count how many of each
value you have
◦ Now go through the value set and turn it into a
running total
0
1
2
3
4
5
6
7
8
9
5
13
2
5
8
0
2
1
7
3
Counting Sort
◦ This kind of sort works well when you have a
really small possible number of values
◦ Like, say, “0 through 9”
◦ Go through the list and count how many of each
value you have
◦ Now go through the value set and turn it into a
running total
0
1
2
3
4
5
6
7
8
9
5
13
15
5
8
0
2
1
7
3
Counting Sort
◦ This kind of sort works well when you have a
really small possible number of values
◦ Like, say, “0 through 9”
◦ Go through the list and count how many of each
value you have
◦ Now go through the value set and turn it into a
running total
0
1
2
3
4
5
6
7
8
9
5
13
15
20
8
0
2
1
7
3
Counting Sort
◦ This kind of sort works well when you have a
really small possible number of values
◦ Like, say, “0 through 9”
◦ Go through the list and count how many of each
value you have
◦ Now go through the value set and turn it into a
running total
0
1
2
3
4
5
6
7
8
9
5
13
15
20
28
0
2
1
7
3
Counting Sort
◦ This kind of sort works well when you have a
really small possible number of values
◦ Like, say, “0 through 9”
◦ Go through the list and count how many of each
value you have
◦ Now go through the value set and turn it into a
running total
0
1
2
3
4
5
6
7
8
9
5
13
15
20
28
28
2
1
7
3
Counting Sort
◦ This kind of sort works well when you have a
really small possible number of values
◦ Like, say, “0 through 9”
◦ Go through the list and count how many of each
value you have
◦ Now go through the value set and turn it into a
running total
0
1
2
3
4
5
6
7
8
9
5
13
15
20
28
28
30
1
7
3
Counting Sort
◦ This kind of sort works well when you have a
really small possible number of values
◦ Like, say, “0 through 9”
◦ Go through the list and count how many of each
value you have
◦ Now go through the value set and turn it into a
running total
0
1
2
3
4
5
6
7
8
9
5
13
15
20
28
28
30
31
7
3
Counting Sort
◦ This kind of sort works well when you have a
really small possible number of values
◦ Like, say, “0 through 9”
◦ Go through the list and count how many of each
value you have
◦ Now go through the list and turn it into a
running total
0
1
2
3
4
5
6
7
8
9
5
13
15
20
28
28
30
31
38
3
Counting Sort
◦ This kind of sort works well when you have a
really small possible number of values
◦ Like, say, “0 through 9”
◦ Go through the list and count how many of each
value you have
◦ Now go through the value set and turn it into a
running total
0
1
2
3
4
5
6
7
8
9
5
13
15
20
28
28
30
31
38
41
Counting Sort
◦ This kind of sort works well when you have a
really small possible number of values
◦ Like, say, “0 through 9”
◦ Go through the list and count how many of each
value you have
◦ Now go through the value set and turn it into a
running total
◦ Now go through the list…
0
1
2
3
4
5
6
7
8
9
5
13
15
20
28
28
30
31
38
41
Counting Sort
◦ This kind of sort works well when you have a
really small possible number of values
◦ Like, say, “0 through 9”
◦ Go through the list and count how many of each
value you have
◦ Now go through the value set and turn it into a
running total
◦ Now go through the list…
◦ …and for each item, its value in the value set
tells you where it goes in the new list
0
1
2
3
4
5
6
7
8
9
5
13
15
20
28
28
30
31
38
41
Counting Sort
◦ This kind of sort works well when you have a
really small possible number of values
◦ Like, say, “0 through 9”
◦ Go through the list and count how many of each
value you have
◦ Now go through the value set and turn it into a
running total
◦ Now go through the list…
◦ …and for each item, its value in the value set
tells you where it goes in the new list
◦ Decrement the value-set value so that the next
item also goes the right place
0
1
2
3
4
5
6
7
8
9
5
13
15
20
28
28
30
31
38
41
Counting Sort
◦ This kind of sort works well when you have a
really small possible number of values
◦ Like, say, “0 through 9”
◦ Go through the list and count how many of each
value you have
◦ Now go through the value set and turn it into a
running total
◦ Now go through the list…
◦ …and for each item, its value in the value set
tells you where it goes in the new list
◦ Decrement the value-set value so that the next
item also goes the right place
◦ Walk the list back-to-front, and equal items stay
in the same order
0
1
2
3
4
5
6
7
8
9
5
13
15
20
28
28
30
31
38
41
Counting Sort
◦ This kind of sort works well when you have a
really small possible number of values
◦ Like, say, “0 through 9”
◦ Go through the list and count how many of each
value you have
◦ Now go through the value set and turn it into a
running total
◦ Now go through the list…
◦ …and for each item, its value in the value set
tells you where it goes in the new list
◦ Decrement the value-set value so that the next
item also goes the right place
◦ Walk the list back-to-front, and equal items stay
in the same order
0
1
2
3
4
5
6
7
8
9
5
13
15
20
28
28
30
31
38
41
◦ Θ(𝑘 + 𝑛) where 𝑘 is the number of possible
values
Counting Sort
◦ This kind of sort works well when you have a
really small possible number of values
◦ Like, say, “0 through 9”
◦ Go through the list and count how many of each
value you have
◦ Now go through the value set and turn it into a
running total
◦ Now go through the list…
◦ …and for each item, its value in the value set
tells you where it goes in the new list
◦ Decrement the value-set value so that the next
item also goes the right place
◦ Walk the list back-to-front, and equal items stay
in the same order
0
1
2
3
4
5
6
7
8
9
5
13
15
20
28
28
30
31
38
41
◦ Θ(𝑘 + 𝑛) where 𝑘 is the number of possible
values
◦ Generally we use this where 𝑘 = 𝒪(𝑛), so it
collapses to Θ(𝑛)
Radix Sort
Radix Sort
◦ Counting-sort the list by the least significant digit.
Radix Sort
◦ Counting-sort the list by the least significant digit.
◦ Counting-sort the list by the second-least-significant digit.
Radix Sort
◦ Counting-sort the list by the least significant digit.
◦ Counting-sort the list by the second-least-significant digit.
◦ …
◦ Counting-sort the list by the most significant digit.
Radix Sort
◦ Counting-sort the list by the least significant digit.
◦ Counting-sort the list by the second-least-significant digit.
◦ …
◦ Counting-sort the list by the most significant digit.
◦ That’s it.
Radix Sort
◦ Counting-sort the list by the least significant digit.
◦ Counting-sort the list by the second-least-significant digit.
◦ …
◦ Counting-sort the list by the most significant digit.
◦ That’s it.
◦ No, really. That’s it.
Radix Sort, A Bit More Formally
◦ Let 𝑑 be the number of significant digits in our list.
◦ For 𝑖 = 1 to 𝑑:
◦ Counting-sort the list by the 𝑖th least-significant digit.
Radix Sort, A Bit More Formally
◦ Let 𝑑 be the number of significant digits in our list.
◦ For 𝑖 = 1 to 𝑑:
◦ Counting-sort the list by the 𝑖th least-significant digit.
◦ Note that we rely on counting sort’s stability property – i.e., that it doesn’t change the order of anything
it doesn’t have to.
Radix Sort, A Bit More Formally
◦ Let 𝑑 be the number of significant digits in our list.
◦ For 𝑖 = 1 to 𝑑:
◦ Counting-sort the list by the 𝑖th least-significant digit.
◦ Note that we rely on counting sort’s stability property – i.e., that it doesn’t change the order of anything
it doesn’t have to.
◦ Since counting sort is Θ(𝑛 + 𝑘), this is Θ 𝑑 𝑛 + 𝑘 .
Radix Sort, A Bit More Formally
◦ Let 𝑑 be the number of significant digits in our list.
◦ For 𝑖 = 1 to 𝑑:
◦ Counting-sort the list by the 𝑖th least-significant digit.
◦ Note that we rely on counting sort’s stability property – i.e., that it doesn’t change the order of anything
it doesn’t have to.
◦ Since counting sort is Θ(𝑛 + 𝑘), this is Θ 𝑑 𝑛 + 𝑘 .
◦ If our counting sort collapses to Θ 𝑛 , this is Θ(𝑑𝑛).
◦ If we take 𝑑 to be a constant, this algorithm is linear!
Radix Sort, A Bit More Formally
◦ Let 𝑑 be the number of significant digits in our list.
◦ For 𝑖 = 1 to 𝑑:
◦ Counting-sort the list by the 𝑖th least-significant digit.
◦ Note that we rely on counting sort’s stability property – i.e., that it doesn’t change the order of anything
it doesn’t have to.
◦ Since counting sort is Θ(𝑛 + 𝑘), this is Θ 𝑑 𝑛 + 𝑘 .
◦ If our counting sort collapses to Θ 𝑛 , this is Θ(𝑑𝑛).
◦ If we take 𝑑 to be a constant, this algorithm is linear!
◦ Caveats:
◦ 𝑑 can be quite high
◦ You need 𝑑 < log 𝑛 for this to be asymptotically faster than merge sort
Bucket Sort
Bucket Sort
◦ Assume we have a well-distributed set of data – we’ll use floating-point numbers as an example.
◦ Say we have a set of 𝑛 floating-point numbers within [0, 1).
◦ We know they’re at least roughly evenly distributed.
Bucket Sort
◦ Assume we have a well-distributed set of data – we’ll use floating-point numbers as an example.
◦ Say we have a set of 𝑛 floating-point numbers within [0, 1).
◦ We know they’re at least roughly evenly distributed.
◦ Bucket sort:
◦ Break the interval [0, 1) into 𝑛 equally-sized lists corresponding to sub-intervals.
◦ Traverse the set of numbers.
◦ Put each number in its corresponding sub-interval list.
◦ Sort each sub-interval list just in case.
Bucket Sort
◦ Assume we have a well-distributed set of data – we’ll use floating-point numbers as an example.
◦ Say we have a set of 𝑛 floating-point numbers within [0, 1).
◦ We know they’re at least roughly evenly distributed.
◦ Bucket sort:
◦ Break the interval [0, 1) into 𝑛 equally-sized lists corresponding to sub-intervals.
◦ Traverse the set of numbers.
◦ Put each number in its corresponding sub-interval list.
◦ Sort each sub-interval list just in case.
◦ As long as our set of numbers really is well-distributed, this will be Θ(𝑛).
◦ The better distributed the set is, the closer to linear the results get.
Bucket Sort
◦ Assume we have a well-distributed set of data – we’ll use floating-point numbers as an example.
◦ Say we have a set of 𝑛 floating-point numbers within [0, 1).
◦ We know they’re at least roughly evenly distributed.
◦ Bucket sort:
◦ Break the interval [0, 1) into 𝑛 equally-sized lists corresponding to sub-intervals.
◦ Traverse the set of numbers.
◦ Put each number in its corresponding sub-interval list.
◦ Sort each sub-interval list just in case.
◦ As long as our set of numbers really is well-distributed, this will be Θ(𝑛).
◦ The better distributed the set is, the closer to linear the results get.
◦ This version of bucket sort is limited to real numbers in [0, 1)…
◦ …but as long as you know something about the distribution of your data, you can adapt it pretty well
Review: Linked Lists
COP3503 COMPUTER SCIENCE II
DR. MAT THEW B. GERBER
PORTIONS FROM SEAN SZUMLANSKI AND MICHAEL MCALPIN
struct list_item {
struct list_item *next;
Singly Linked
Lists – Direct
int stuff;
n
…
…
…
n
…
…
…
n
…
…
…
char more_stuff[32];
The simplest form of linked list.
Real simple to implement.
h
int id;
}
struct list {
struct list_item *head;
struct list_item *tail;
}
t
NULL
struct list_item {
struct list_item *next;
Singly Linked
Lists – Direct
int id;
int stuff;
n
…
…
…
n
…
…
…
n
…
…
…
char more_stuff[32];
The simplest form of linked list.
Real simple to implement.
h
}
Some versions don’t store a tail.
struct list {
struct list_item *head;
}
NULL
struct list_item {
struct list_item *next;
Singly Linked
Lists – Direct
int id;
int stuff;
n
…
…
…
n
…
…
…
n
…
…
…
char more_stuff[32];
The simplest form of linked list.
Real simple to implement.
h
}
Some versions don’t store a tail.
And some versions are circular.
struct list {
struct list_item *head;
}
struct list_item {
struct list_item *next;
struct list_item_data *data;
}
Singly Linked
Lists – Indirect
h
struct list_item_data {
n
d
…
…
…
n
d
…
…
…
n
d
…
…
…
int id;
You can store the data off in another
structure entirely if you want to.
int stuff;
This general idea will become
important later…
char more_stuff[32];
t
}
NULL
struct list {
struct list_item *head;
struct list_item *tail;
}
struct list_item {
struct list_item *prev;
Doubly Linked
Lists – Direct
int id;
…but is more of a pain in the neck to
implement.
h
p
n
…
…
…
p
n
…
…
…
p
n
…
…
…
int stuff;
Doubly linked lists have pointers both
directions.
This lets you perform some operations
a lot faster (and/or maintaining a lot
less state) if you’re starting in the
middle of the list…
NULL
struct list_item *next;
char more_stuff[32];
}
t
struct list {
struct list_item *head;
(At least, if you’re implementing per
data type…)
struct list_item *tail;
}
NULL
Linked List Advantages
All linked lists share some real advantages
◦ Simple to implement
◦ Basically all of you have written at least some of these before
◦ Very lightweight structure
◦ Just a few pointers per item
◦ Fast for small or sequential data sets
◦ Simplicity of the per-unit operations means they can all happen very quickly
◦ Maintain sequence unless you explicitly insert into the middle
◦ When the order of item arrival is important, you get it for free
In summary, linked lists in their various forms are good for data that are usually accessed
sequentially
◦ (Consequence: if your data are sequential, you shouldn’t underestimate linked lists!)
Linked List Disadvantage
There’s really only one, but it’s a big one
Linked lists are really, really bad at random access
This means it’s slow to
◦ Sort
◦ Find items by ID
◦ Search items by characteristic
◦ Sort items
◦ Do anything else with anything other than the first, last, or next item
◦ Or previous item if it’s a doubly linked list
By the way, if you know your list is really small anyway, this doesn’t matter
◦ Don’t bother with a complex data structure for a list of ten items!
struct int_bst {
int_bst *left;
int value;
int_bst *right;
Binary Search
Trees
These, you’ll surely remember, solve
the random-access problem quite well.
At least for searching purposes.
}
l
J
l
l
1
r
l
2
r
3
r
l
4
r
5
r
l
l
7
6
r
r
l
l
9
8
r
r
struct int_bst {
int_bst *left;
int value;
int_bst *right;
Binary Search
Trees
These, you’ll surely remember, solve
the random-access problem quite well.
At least for searching purposes.
}
l
L
l
l
…on good days.
l
l
2
1
r
r
3
r
4
r
5
r
l
6
r
l
7
r
l
8
r
l
9
r
Binary Search Tree Characteristics
◦ Fast searching and retrieval based on value
◦ As long as they don’t get imbalanced
◦ Reasonable insertion and deletion times
◦ As long as they don’t get imbalanced
◦ Reasonable overhead
The problem with binary search trees, obviously, is the need to keep them
balanced
◦ You were probably already taught at least one algorithm to do this…
◦ …but it’s better to keep them balanced the whole time
We’re going to talk about how to do just that
◦ But first, we’re going to talk more about terms of analysis
Treaps and Skip Lists
COP3503 COMPUTER SCIENCE II
DR. MATTHEW B. GERBER
PORTIONS FROM SEAN SZUMLANSKI, MICHAEL MCALPIN, AND
WIKIPEDIA
Review: Binary Search Trees
A binary search tree is a tree in which:
◦ Each node has at most two children
◦ Each node has at least the following data
elements:
l
◦ A parent pointer (NULL if the node is the root)
◦ A left child pointer (NULL if the node has no left child)
◦ A right child pointer (NULL if the node has no right child)
◦ An indexing key
◦ The insertion and deletion behaviors
guarantee that:
◦ If node 𝑦 is the left child of node 𝑥, or any descendant
of the left child of 𝑥, then 𝑦. 𝑘𝑒𝑦 ≤ 𝑥. 𝑘𝑒𝑦
◦ If node 𝑦 is the right child of node 𝑥, or any descendant
of the right child of 𝑥, then 𝑦. 𝑘𝑒𝑦 ≥ 𝑥. 𝑘𝑒𝑦
l
l
1
r
l
2
r
3
r
l
4
r
5
r
l
l
7
6
r
r
l
l
9
8
r
r
Treaps
A treap (tree-heap) has an additional property:
◦ Each node has an additional value, called priority
l
5
p8
r
Treaps
A treap (tree-heap) has an additional property:
◦ Each node has an additional value, called priority
◦ The priority of a node must be at least as great as
the priority of its children
l
l
l
1
p4
r
3
p6
5
p8
r
l
r
l
4
p2
r
9
p3
r
Treaps
A treap (tree-heap) has an additional property:
◦ Each node has an additional value, called priority
◦ The priority of a node must be at least as great as
the priority of its children
◦ This means that the effective order of insertion into
the tree is random
l
l
l
1
p4
r
3
p6
5
p8
r
l
r
l
4
p2
r
9
p3
r
Treaps
A treap (tree-heap) has an additional property:
◦ Each node has an additional value, called priority
◦ The priority of a node must be at least as great as
the priority of its children
◦ This means that the effective order of insertion into
the tree is random
◦ Since a randomly-constructed binary search tree
has an 𝒪(log 𝑛) expected search length—
l
l
l
1
p4
r
3
p6
5
p8
r
l
r
l
4
p2
r
9
p3
r
Expected Search Length in Randomly
Constructed Binary Search Trees
We want to find node 𝑛. How many ancestors is 𝑛 expected to have?
Expected Search Length in Randomly
Constructed Binary Search Trees
We want to find node 𝑛. How many ancestors is 𝑛 expected to have?
◦ Node 𝑚 is an ancestor of 𝑛 if:
◦ It was inserted before 𝑛
◦ It was inserted before any node with a value between node 𝑚’s value and node 𝑛’s value
Expected Search Length in Randomly
Constructed Binary Search Trees
We want to find node 𝑛. How many ancestors is 𝑛 expected to have?
◦ Node 𝑚 is an ancestor of 𝑛 if:
◦ It was inserted before 𝑛
◦ It was inserted before any node with a value between node 𝑚’s value and node 𝑛’s value
1
◦ So the nodes with next and previous values to 𝑛 have a 2 probability of being its ancestor…
1
◦ The next nodes out have a 3 probability… and so on
Expected Search Length in Randomly
Constructed Binary Search Trees
We want to find node 𝑛. How many ancestors is 𝑛 expected to have?
◦ Node 𝑚 is an ancestor of 𝑛 if:
◦ It was inserted before 𝑛
◦ It was inserted before any node with a value between node 𝑚’s value and node 𝑛’s value
1
◦ So the nodes with next and previous values to 𝑛 have a 2 probability of being its ancestor…
1
◦ The next nodes out have a 3 probability… and so on
◦ Then the upper bound for the expected value is the sum of two harmonic numbers 𝐻𝑘 with 𝑘 < 𝑛
Expected Search Length in Randomly
Constructed Binary Search Trees
We want to find node 𝑛. How many ancestors is 𝑛 expected to have?
◦ Node 𝑚 is an ancestor of 𝑛 if:
◦ It was inserted before 𝑛
◦ It was inserted before any node with a value between node 𝑚’s value and node 𝑛’s value
1
◦ So the nodes with next and previous values to 𝑛 have a 2 probability of being its ancestor…
1
◦ The next nodes out have a 3 probability… and so on
◦ Then the upper bound for the expected value is the sum of two harmonic numbers 𝐻𝑘 with 𝑘 < 𝑛
◦ That’s less than about 2(𝛾 + ln 𝑛)…
Expected Search Length in Randomly
Constructed Binary Search Trees
We want to find node 𝑛. How many ancestors is 𝑛 expected to have?
◦ Node 𝑚 is an ancestor of 𝑛 if:
◦ It was inserted before 𝑛
◦ It was inserted before any node with a value between node 𝑚’s value and node 𝑛’s value
1
◦ So the nodes with next and previous values to 𝑛 have a 2 probability of being its ancestor…
1
◦ The next nodes out have a 3 probability… and so on
◦ Then the upper bound for the expected value is the sum of two harmonic numbers 𝐻𝑘 with 𝑘 < 𝑛
◦ That’s less than about 2(𝛾 + ln 𝑛)…
◦ Which is 𝒪(log 𝑛)
Treaps
A treap (tree-heap) has an additional property:
◦ Each node has an additional value, called priority
◦ The priority of a node must be at least as great as
the priority of its children
◦ This means that the effective order of insertion into
the tree is random
◦ Since a randomly-constructed binary search tree
has an 𝒪(log 𝑛) expected search length—so does a
treap
l
l
l
1
p4
r
3
p6
5
p8
r
l
r
l
4
p2
r
9
p3
r
Treaps
A treap (tree-heap) has an additional property:
◦ Each node has an additional value, called priority
◦ The priority of a node must be at least as great as
the priority of its children
◦ This means that the effective order of insertion into
the tree is random
◦ Since a randomly-constructed binary search tree
has an 𝒪(log 𝑛) expected search length—so does a
treap
◦ So far, so good – but how do we maintain the heap
property?
l
l
l
1
p4
r
3
p6
5
p8
r
l
r
l
4
p2
r
9
p3
r
Insertion Into Treaps
◦ First, insert as though into a BST
l
l
l
1
p4
3
p6
l
r
l
r
2
p9
5
p8
r
r
l
4
p2
r
9
p3
r
Insertion Into Treaps
◦ First, insert as though into a BST
◦ Then rotate (similarly to an AVL…)
l
l
l
1
p4
3
p6
l
r
l
r
2
p9
5
p8
r
r
l
4
p2
r
9
p3
r
Insertion Into Treaps
◦ First, insert as though into a BST
◦ Then rotate (similarly to an AVL…)
l
l
l
l
1
p4
r
2
p9
r
3
p6
5
p8
r
l
r
l
4
p2
r
9
p3
r
Insertion Into Treaps
◦ First, insert as though into a BST
◦ Then rotate (similarly to an AVL…)
l
l
l
1
p4
r
2
p9
5
p8
r
r
l
l
3
p6
9
p3
r
r
l
4
p2
r
Insertion Into Treaps
◦ First, insert as though into a BST
◦ Then rotate (similarly to an AVL…)
◦ …until it’s where it needs to be
l
l
1
p4
2
p9
r
r
l
l
3
p6
5
p8
r
r
l
l
4
p2
r
9
p3
r
Insertion Into Treaps
◦ First, insert as though into a BST
◦ Then rotate (similarly to an AVL…)
◦ …until it’s where it needs to be
◦ Notice that this does not guarantee a perfect
result…
◦ Just, as per the expected value calculations,
makes a good one very likely
l
l
1
p4
2
p9
r
r
l
l
3
p6
5
p8
r
r
l
l
4
p2
r
9
p3
r
Insertion Into Treaps
◦ First, insert as though into a BST
◦ Then rotate (similarly to an AVL…)
◦ …until it’s where it needs to be
◦ Notice that this does not guarantee a perfect
result…
◦ Just, as per the expected value calculations,
makes a good one very likely
◦ The rotation is maximum 𝒪 ℎ , which—again,
on average—is 𝒪(log 𝑛)
l
l
1
p4
2
p9
r
r
l
l
3
p6
5
p8
r
r
l
l
4
p2
r
9
p3
r
Deletion from Treaps
◦ As always, leaves and nodes with one child are
easy
◦ If a node has two children, replace it with its
adjacent successor or predecessor…
l
l
l
1
p4
r
3
p6
5
p8
r
l
r
l
4
p2
r
9
p3
r
Deletion from Treaps
◦ As always, leaves and nodes with one child are
easy
◦ If a node has two children, replace it with its
adjacent successor or predecessor…
l
l
l
1
p4
r
3
p6
5
p8
r
l
r
l
4
p2
r
9
p3
r
Deletion from Treaps
◦ As always, leaves and nodes with one child are
easy
◦ If a node has two children, replace it with its
adjacent successor or predecessor…
l
l
l
1
p4
r
3
p6
4
p2
r
l
r
l
4
p2
r
9
p3
r
Deletion from Treaps
◦ As always, leaves and nodes with one child are
easy
◦ If a node has two children, replace it with its
adjacent successor or predecessor…
◦ …and, again, rotate it until it’s in the right place
l
l
1
p4
r
3
p6
r
l
4
p2
r
l
9
p3
r
Deletion from Treaps
◦ As always, leaves and nodes with one child are
easy
◦ If a node has two children, replace it with its
adjacent successor or predecessor…
◦ …and, again, rotate it until it’s in the right place
l
l
1
p4
3
p6
r
r
l
l
4
p2
r
9
p3
r
Skip Lists
Skip Lists
A skip list starts as an ordinary linked list…
H
1
2
3
4
5
6
7
8
Skip Lists
A skip list starts as an ordinary linked list…
◦ But adds additional layers of pointers on top of it
H
1
2
3
4
5
6
7
8
Skip Lists
A skip list starts as an ordinary linked list…
◦ But adds additional layers of pointers on top of it
◦ Each layer omits a certain number of the
pointers from the previous later (usually about
half)…
H
1
2
3
4
5
6
7
8
Skip Lists
A skip list starts as an ordinary linked list…
◦ But adds additional layers of pointers on top of it
◦ Each layer omits a certain number of the
pointers from the previous later (usually about
half)…
◦ …until all that’s left is the head element
◦ Only needs about twice as many pointers as we
had in the first place
H
1
2
3
4
5
6
7
8
Searching Skip Lists
Searching for value 𝑣 is easy:
◦ Let 𝑛 be the node at the left of
the top level
◦ Repeat
◦ If 𝑛. 𝑣 = 𝑣, succeed
◦ If 𝑛. 𝑣 < 𝑣, go right
◦ If 𝑛. 𝑣 > 𝑣 or ! 𝑛, go left then down
◦ If we’ve fallen off the bottom, fail
Obviously 𝒪(log 𝑛) on average…
◦ …as long as we keep our cut-by-half
property
H
1
2
3
4
5
6
7
8
Insertion and Deletion
Insertion and deletion are also easy
Insertion:
◦ Find the spot the node should go
◦ Randomly choose the height of the node
◦ Insert it into the linked lists up to that level, as
you normally would
◦ One search, plus log 𝑛 insertions – 𝒪(log 𝑛)
Deletion:
◦ Find the node
◦ Delete it from all the linked lists it’s in, as you
normally would
◦ Dispose of the value
◦ One search, plus log 𝑛 deletions – 𝒪(log 𝑛)
H
1
2
3
4
5
6
7
8
Re-Optimizing a Skip List
◦ We could theoretically end up deleting
too many tall or short nodes
◦ We can fix this by just going through the
list and re-balancing the height of each
node
◦ Can use straight logarithmic boundaries
if it’s an internal structure…
◦ Or randomize it if we’re worried about
adversarial values
◦ 𝒪(𝑛), but a fast 𝒪(𝑛), since we’re just
doing real simple pointer operations
◦ Can attach this to list traversals that
H
happen naturally (load/save, print, etc.)
1
2
3
4
5
6
7
8
Trees
COP3503 COMPUTER SCIENCE II
DR. MATTHEW B. GERBER
PORTIONS FROM SEAN SZUMLANSKI, MICHAEL MCALPIN, AND
WIKIPEDIA
Review: Binary Search Trees
A binary search tree is a tree in which:
◦ Each node has at most two children
◦ Each node has at least the following data elements:
◦ A parent pointer (NULL if the node is the root)
◦ A left child pointer (NULL if the node has no left child)
◦ A right child pointer (NULL if the node has no right child)
◦ An indexing key
◦ The insertion and deletion behaviors guarantee that:
◦ If node 𝑦 is the left child of node 𝑥, or any descendant of the left child of 𝑥, then 𝑦. 𝑘𝑒𝑦 ≤ 𝑥. 𝑘𝑒𝑦
◦ If node 𝑦 is the right child of node 𝑥, or any descendant of the right child of 𝑥, then 𝑦. 𝑘𝑒𝑦 ≥ 𝑥. 𝑘𝑒𝑦
Complexity of Binary Search Trees
All basic operations on BSTs take place in 𝒪 ℎ
time, where ℎ is the height of the tree
l
◦ In a well-balanced BST, this is 𝒪(log 𝑛) …
l
l
1
r
l
2
r
3
r
l
4
r
5
r
l
l
7
6
r
r
l
l
9
8
r
r
Complexity of Binary Search Trees
All basic operations on BSTs take place in 𝒪 ℎ
time, where ℎ is the height of the tree
l
◦ In a well-balanced BST, this is 𝒪(log 𝑛) …
◦ …but in a poorly-balanced one, this can
degenerate toward 𝒪(𝑛)
l
l
l
l
2
1
r
r
3
r
4
r
5
r
l
6
r
l
7
r
l
8
r
l
9
r
Searching the Tree
◦ Start at the root
◦ Look at the node we’re at
◦ If we’ve found our key, stop
◦ If our key is less than the node we’re at, go left
◦ Otherwise, go right
◦ Keep doing this until we find our key
◦ If we ever hit null instead of our key,
l 1 r
our key isn’t in the tree
◦ Can do this recursively or iteratively
l
2
l
l
r
3
r
l
4
r
5
r
l
l
7
6
r
r
l
l
9
8
r
r
Searching the Tree: Recursive
bst bstSearch(bst x, key k) {
if(x == null) {
return null;
}
if(k == x.key) {
return x;
}
l
l
l
1
r
if(k < x.key) {
return bstSearch(x.left, k) l
}
2
return bstSearch(x.right, k)
}
r
3
r
l
4
r
5
r
l
l
7
6
r
r
l
l
9
8
r
r
Searching the Tree: Iterative
bst bstSearch(bst x, key k) {
while(true) {
l
if(x == null) {
return null;
}
if(k == x.key) {
return x;
}
if(k < x.key) {
x = x.left;
}
x = x.right;
} // while
} // bstSearch
l
l
1
r
l
2
r
3
r
l
4
r
5
r
l
l
7
6
r
r
l
l
9
8
r
r
Inserting
◦ Start at the root
◦ Look at the node we’re at
◦ If it’s null, stop and insert the new node there
◦ If our key is less than the node we’re at, go left
◦ Otherwise, go right
◦ Keep doing this until we find null
l
l
l
1
r
l
2
r
3
r
l
4
r
5
r
l
l
7
6
r
r
l
l
9
8
r
r
Inserting
bstInsert(var bst t, bstnode n) {
bst x = t, y = null;
l
if(t == null) {
t = n;
return;
}
while(x != null) {
y = x;
if(n.key < x.key) {
x = x.left;
} else { x = x.right; }
} // while
n.parent = y;
if(n.key < y.key) {
y.left = n
} else { y.right = n }
} // bstSearch
l
l
1
r
l
2
r
3
r
l
4
r
5
r
l
l
7
6
r
r
l
l
9
8
r
r
Deleting
◦ If the node has no children, easy
◦ If the node only has one child, promote it
◦ If the node has two children…
l
◦ Find either its minimum right descendant or maximum left
descendant
◦ That descendant has at most one child – do you see why?
◦ Move the descendant to where the deleted node was
◦ Promote the descendant’s child if it had one
l
l
1
r
◦ The idea is straightforward, it’s cleaning up
l
the links that takes all the effort
2
r
3
r
l
4
r
5
r
l
l
7
6
r
r
l
l
9
8
r
r
Deleting
// Replace node dest with node src.
// Handles changing parenthood of src,
//
ignores children of dest.
// Handles the case where src is null.
l
5
r
bstRepl(var bst root, bst dest, bst src) {
if(dest = root) {
root = src;
} else if(dest.parent.right = dest) {
dest.parent.right = src;
} else {
dest.parent.left = src;
}
if(src != null) {
src.parent = dest.parent;
}
}
l
l
1
r
l
2
r
3
r
l
4
r
l
l
7
6
r
r
l
l
9
8
r
r
Deleting
// Has src adopt the children of dest.
bstAdopt(bst dest, bst src) {
l
5
r
src.left = dest.left;
l
if(src.left != null) {
src.left.parent = src;
}
src.right = dest.right;
if(src.right != null) {
src.right.parent = src;
}
}
l
1
r
l
2
r
3
r
l
4
r
l
l
7
6
r
r
l
l
9
8
r
r
Deleting
bstDel(var bst root, bst n) {
if(n.left == null) {
bstRepl(root, n, n.right);
} else if (n.right == null) {
bstRepl(root, n, n.left);
} else {
bst minRight = bstMin(n.right);
bstRepl(root, minRight, minRight.right);
bstRepl(root, n, minRight);
bstAdopt(n, minRight);
}
}
l
l
l
1
r
l
2
r
3
r
l
4
r
5
r
l
l
7
6
r
r
l
l
9
8
r
r
Restoring the Balance: AVL Trees
◦ The balance factor of a node in a BST is the
difference between the height of its left subtree
and the height of its right subtree
◦ In an AVL tree, the balance of any node must
have an absolute value of at most 1
l 5 r 0
l 3 r -1
l
1 r +1
l 2 r 0
l 4 r 0
l
7 r +1
l 6 r 0
l 9 r -1
l 8 r 0
Restoring the Balance: AVL Trees
◦ The balance factor of a node in a BST is the
difference between the height of its left subtree
and the height of its right subtree
◦ In an AVL tree, the balance of any node must
have an absolute value of at most 1
◦ If the tree gets imbalanced…
l 5 r 0
l 3 r -2
l
1 r +2
l 4 r 0
l 2 r +1
l 2 r 0
l
7 r +1
l 6 r 0
l 9 r -1
l 8 r 0
Restoring the Balance: AVL Trees
◦ The balance factor of a node in a BST is the
difference between the height of its left subtree
and the height of its right subtree
◦ In an AVL tree, the balance of any node must
have an absolute value of at most 1
◦ If the tree gets imbalanced…
◦ We cure it by rotating
l 5 r 0
l 3 r -2
l
1 r +2
l 4 r 0
l 2 r +1
l 2 r 0
l
7 r +1
l 6 r 0
l 9 r -1
l 8 r 0
Restoring the Balance: AVL Trees
◦ The balance factor of a node in a BST is the
difference between the height of its left subtree
and the height of its right subtree
◦ In an AVL tree, the balance of any node must
have an absolute value of at most 1
◦ If the tree gets imbalanced…
◦ We cure it by rotating
l 5 r 0
l 3 r -1
l
l 1 r 0
2 r 0
l 4 r 0
l 2 r 0
l
7 r +1
l 6 r 0
l 9 r -1
l 8 r 0
Restoring the Balance: AVL Trees
◦ The balance factor of a node in a BST is the
difference between the height of its left subtree
and the height of its right subtree
◦ In an AVL tree, the balance of any node must
have an absolute value of at most 1
◦ If the tree gets imbalanced…
◦ We cure it by rotating
◦ This keeps the tree well-balanced
l
◦ So all basic operations are 𝒪(log 𝑛)
l 1 r 0
l 5 r 0
l 3 r -1
2 r 0
l 4 r 0
l 2 r 0
l
7 r +1
l 6 r 0
l 9 r -1
l 8 r 0
Restoring the Balance: AVL Trees
◦ The balance factor of a node in a BST is the
difference between the height of its left subtree
and the height of its right subtree
l 5 r 0
◦ In an AVL tree, the balance of any node must
have an absolute value of at most 1
l 3 r -1
l 7 r +1
◦ If the tree gets imbalanced…
◦ We cure it by rotating
◦ This keeps the tree well-balanced
l 2 r 0
l 4 r 0
l 6 r 0
l 9 r -1
◦ So all basic operations are 𝒪(log 𝑛)
◦ And for any given rotation, we’ll have l 1 r 0
l 8 r 0
l 2 r 0
to rotate at most once per level…
◦ So that’s also 𝒪(log 𝑛)
