Assignment 14: Index

A tree that keeps its promise, and a shape that does not

Note

Your own private GitHub repository is waiting for you (see Getting the code below), clone it and open it in VS Code.

Plan to set aside about 3 hours. The tree (§4) is the bulk of it; parts 2, 3 and 4 are short once it works. findings.txt (§8) is worth taking seriously it is where the assignment actually happens.

Objectives

By the end of this assignment, you will be able to:

State the binary search tree property, and explain why it makes a search cheap
Implement insert, contains and getHeight recursively, on a structure with two children per node
Explain why an in-order traversal of a BST comes out sorted, without any sorting code
Use std::map for the same job, and say what it gives you that your tree does not
Measure the height of trees you built yourself, and compare that with lg(N)
Put a number on the constant that Big-Oh throws away

This assignment covers skills F1 (implement BST insertion and traversals) and G1/G2 (use the STL containers), from clusters F and G.

Important

Window 2’s reference date is Friday of this week, Nov 20. You are preparing for a check-in in the same week you do this, which is why this assignment is deliberately moderate. Do not let it crowd out your preparation.

Note

Lab and homework. You start this in lab on Tuesday Nov 17, with Monday’s lecture on the BST property and insert behind you. §4’s TODOs 1–3 need only Monday.

TODO 7 uses std::map, which is Friday’s lecture, but it is five lines and the comment in the file tells you what you need, so do not wait for it if you are ready.

There is no remove in this assignment. Wednesday’s lecture codes that one live, on the board, together.

1. Introduction

Every container you have built this semester is a promise about where things are.

An array promises that the thing you want is at a place you can compute. A linked list promises nothing about place, only about order. A stack promises the newest thing; a queue the oldest. a11’s hash table promises that a key can be turned into a place, which is a strange promise until you notice that a key is not a number and a place is.

A tree promises something none of them do:

everything smaller is on one side, everything larger is on the other, and that is true at every node, all the way down.

That is the binary search tree property, and one rule kept everywhere is the whole of it. It buys two things that look unrelated and are not:

Searching is cheap. At each node you learn which half of what remains you can stop caring about. Half, then half of that, then half of that again.
The items are already in order. Walk left, then the node, then right, and the items come out sorted, with no sorting code anywhere.

You will use both. And then you will measure the thing nobody tells you at first, which is that the promise is only as good as the shape, and the shape is not a property of the tree. It is a property of the order the data arrived in.

2. Getting the Code

Your private GitHub repository for this assignment is created for you inside the course organization, with the starter code already in it. There is nothing to accept and nothing to set up, if you are on the roster, it is there.

gh repo clone 26fa-cs112/cs112-a14-YOURUSERNAME
cd cs112-a14-YOURUSERNAME
make
./a14
make test

Note

Cannot find it? Ask GitHub what you have.

If gh repo clone answers Could not resolve to a Repository, this lists every repository you can actually see, spelled exactly right:

gh repo list 26fa-cs112

If yours is in that list, you mistyped the name, copy it from the output and try again. Watch for usernames that already contain a hyphen or a number; the pattern is cs112-<assignment>-<your username>, so the two halves run together and it often looks wrong when it is right.

If the list is empty, or the command errors, that is mine to fix rather than yours to work around. The usual causes are an organization invitation you have not accepted yet (check your email, including spam and the Promotions tab), or a username I mistyped when I built the roster. Either way, email me at eric.araujo@calvin.edu and I will sort it out the same day.

While you wait, do not create a repository yourself and do not start the work somewhere else. Only the repository I create for you is connected to grading, so anything written outside it has to be moved by hand later, and that is a worse afternoon than a short wait.

make succeeds, ./a14 stops and tells you to do TODO 1, and make test reports 1 / 36.

3. What You Were Given

You edit three files: BST.h, Index.cpp and findings.txt. Nine TODOs.

File	Yours?	What it is
`BST.h`	yes	the tree, TODOs 1–5
`Index.cpp`	yes	TODOs 6–8
`findings.txt`	yes	TODO 9, the four questions
`Index.h`	no	the specification. Read this first.
`given.cpp`	no	file loading, the sampler, the statistics, the chart
`main.cpp`	no	runs all four parts
`Exceptions.h`	no	`BSTException`
`fieldnotes.txt`	no	the text you index
`words.txt`	no	a11’s dictionary, already sorted

Note

Header-only, for the third time. BST is a class template, so its definitions live in BST.h below the class, the same rule as Trace in a06, List in a08, and Stack and Queue in a10. There is no BST.cpp and that is not an oversight.

Every operation is written twice

This is the one structural thing to get straight before you start.

BST::insert     handles the empty tree, keeps the count, and otherwise
                passes the buck to the root node
Node::insert    the recursive one, decides left or right, and either
                recurses or attaches a new Node

The BST method is the doorway; the Node method does the work. Keep that split and each half stays about four lines long. Merge them and you will fight the null root forever.

4. TODOs 1 to 5, the tree

TODO 1, the constructor. Two lines.

TODO 2, insert. Three cases, and they are exactly the three ways two items can compare: smaller goes left, larger goes right, equal is already here and throws.

Note

Why throw on a duplicate? There is nowhere sensible to put a second copy of a value that is already in the tree, it is neither less than nor greater than itself. Silently ignoring it would be defensible, but it throws away information the caller wants.

And this caller wants it very much. Counting how often insert refuses is how §5’s index counts repeated words and how §7’s experiment counts duplicate draws. The refusal is not an error condition; it is a measurement.

try {
    tree.insert(word);
    ++distinct;
} catch (BSTException&) {
    ++repeats;
}

Warning

BST::insert must count after the recursive call, not before. Node::insert throws when the item is already there, and a refused insert must not make the tree think it grew.

TODO 3, contains. The same walk, without the writing. Return what the recursive call gives you, dropping that answer and falling off the end of the function was the single most common way to lose marks on this in spring.

TODO 4, getHeight. Heights here count nodes, not edges:

an empty tree	0
one node	1
a root with one child	2

The recursive definition is one line: a node’s height is one more than the taller of its two subtrees. The interesting part is the base case, and it is more interesting than it looks, you can either say outright that a childless node has height 1, or decide that a missing subtree has height 0 and let it fall out of the arithmetic. The second is shorter and worth working out.

Everything in §7 rests on this method. Check it against a tree you have drawn on paper before you trust it.

TODO 5, the two traversals. traversePreorder is written for you as the model. Copy it and move one line:

pre-order    me, left, right
in-order     left, me, right
post-order   left, right, me

Note

In-order is why it is a search tree and not just any tree. Everything to the left of a node is smaller and everything to the right is larger, so walking left, then me, then right visits the items in ascending order.

Your index will print itself alphabetically and nothing will have sorted it.

5. TODOs 6 and 7, index a text, twice

TODO 6, indexText. Put every word of the text into the tree. Each successful insert is a word you had not seen; each BSTException is a repetition. An in-order traversal then prints the vocabulary alphabetically.

TODO 7, indexWithMap. The same job, about five lines:

counts[word]++;

A missing key is created with a value-initialized int, which is 0, and then incremented.

Important

Look at what the map does that your tree does not.

Your BST<string> is a set. It remembers which words appeared, and catching the exception is the only way to learn that one appeared twice.

A map is a set with a value attached to every key, so it can hold the count itself. That is the whole difference between std::set and std::map, and it is Friday’s lecture, which you will have had by the time you read this, or will have shortly.

A map also walks in key order, for exactly the same reason your in-order traversal does: it is a balanced binary search tree underneath. You are not using a different idea. You are using a better-built version of the one you just wrote.

6. TODO 8, one trial

runTrial builds a fresh tree from a list of words and reports how tall it came out. Three lines, if you use TODO 6 to do the inserting, which you should; it already counts the two things a trial wants.

Make the tree a local variable so its destructor frees it. main.cpp runs this ten times on twenty thousand words each.

7. The experiment

Run ./a14 and look at what it prints, and at results.html.

Ten trees from random samples

Ten times, the program draws 20,000 words at random from the dictionary, with replacement, so the same word can come up twice, and builds a tree. On a typical run:

   trial   height   distinct   duplicates
       1       36      17605         2395
       2       33      17531         2469
       ...
   smallest 31   largest 36   mean 33.40   median 33.00   stdev 1.85
   lg(N) for N = 17516 is 14.10

Seventeen and a half thousand words, in a tree thirty-three deep. That is what O(lg N) looks like when you measure it rather than assert it.

Note

Why the experiment gives the same answer on every machine. The sampler in given.cpp is a linear congruential generator with a fixed seed, the same one a13’s snake uses. It is not a good source of randomness and is not trying to be; it is repeatable, which is what makes a measured height something a grader can check. Genuinely random data would give a different answer every run and there would be nothing to compare against.

The same words, two orders

Then the program takes 5,000 words and inserts them twice: shuffled, and in the order they already sit in words.txt, which is alphabetical.

   shuffled first:      height 30
   already in order:    height 5000
   lg(5000) is 12.29

Five thousand. Every word is greater than the one before it, so every word goes right, and a tree that only ever goes right is a linked list that has forgotten what it is.

Look up a word in each:

   in the shuffled tree:   0.036 microseconds
   in the sorted tree:     24.684 microseconds
   the shape cost you a factor of 690.

Important

Nothing went wrong. The code is correct. Every node still keeps the BST property. The structure is still a binary search tree by every definition in Monday’s lecture.

It is simply useless, because usefulness was never a property of the definition. It was a property of the shape, and the shape is a property of the order the data arrived in, which is not something the tree controls or even knows about.

Sorted input is not an exotic case, either. It is one of the commonest ways data arrives.

This is why week 12 exists

There are two honest responses to what you just measured.

The first is to watch, to measure the height of the trees you actually build, on the data you actually have. That is this assignment, and it is a skill.

The second is to make the structure defend itself, so that no order of arrival can ruin it. That is a rotation, and it is what next week is for.

You are meeting the problem a week before you meet the solution, on purpose. A solution to a problem you have watched happen is a very different thing from a solution to a problem you were told about.

Warning

Why 5,000 and not all 73,419. Inserting the whole sorted dictionary into an unbalanced tree is about 2.7 billion comparisons, and it would hang. The collapse is exactly as visible at 5,000, and it already takes noticeably longer than the shuffled case, which is itself the point.

8. TODO 9, `findings.txt`

Three numbers out of your own run, and four questions. These four are spring’s, kept because they are better than anything newer would be.

Is lg(N) or N a better approximation for your measured heights? Why?
How much variance is there in the ten heights? Is that surprising?
How many duplicate values were there on average? Is that surprising?
Big-Oh O(f(n)) implies constants a and b such that a·f(n) + b describes the reality it approximates. A balanced BST of N items has height O(lg N). Using your experimental results, what is a reasonable value for a?

Important

Question 4 is the sharpest question in this course.

Big-Oh deliberately throws the constant away. It tells you the height is O(lg N) and refuses to say whether that means 14 or 140. You have now measured it: you know lg(N), and you know the height you actually got. Dividing one by the other puts the constant back, as a number you obtained rather than one you were given.

That is what a09 was building towards, and this is where it pays off.

Two of the four are graded on a factual point rather than on prose: answer 1 must start with lg or N, and answer 4 must start with your value for a, as a number. The rest of each answer wants at least twenty words. Nobody is marking the writing.

9. Testing Your Work

make test         # all 36 checks

Important

There are no hidden tests. What you run with make test is exactly what the grader runs, all 36 checks, every one of them in a file in your repository.

6	the tree, insert, contains, duplicates
5	height
5	the three traversals
7	the index and the map
4	the experiment
5	the program runs, and `results.html`
4	`findings.txt`

Heights are graded exactly; microseconds are not graded at all. A height is a fact about the data and the order it arrived in, the same on every machine. Your timings are a fact about your laptop at that moment. Same rule as a09.

The check named “Trial: a sorted sample collapses to a height equal to its size” is the one this whole assignment is built around, and it is exact: N sorted items must give a tree of height N, for several values of N.

10. Submit

git add .
git commit -m "Complete a14"
git push

findings.txt must be committed. results.html need not be.

Important

Put your name at the top of README.md before your final push.

Push as often as you like, the most recent submission counts, and there is no deadline beyond the last day of classes.

The last container you will build by hand

That is thirteen assignments and eight containers: a growing array, a linked list, a stack, a queue, a hash table, and now a search tree, plus every STL container you have reached for along the way.

Not one of them is fast at everything. There is no such container and there never will be, which is why the course is a tour rather than an answer. Choosing well is the whole job, and measuring is how you find out whether you chose well.

Next week the tree learns to defend its own shape. After that, the last assignment is not about containers at all.

Objectives

1. Introduction

2. Getting the Code

3. What You Were Given

Every operation is written twice

4. TODOs 1 to 5, the tree

5. TODOs 6 and 7, index a text, twice

6. TODO 8, one trial

7. The experiment

Ten trees from random samples

The same words, two orders

8. TODO 9, findings.txt

9. Testing Your Work

10. Submit

8. TODO 9, `findings.txt`