The C Paradox

I don't think C gets enough credit. Sure, C doesn't love you. C isn't about love--C is about thrills. C hangs around in the bad part of town. C knows all the gang signs. C has a motorcycle, and wears the leathers everywhere, and never wears a helmet, because that would mess up C's punked-out hair. C likes to give cops the finger and grin and speed away. Mention that you'd like something, and C will pretend to ignore you; the next day, C will bring you one, no questions asked, and toss it to you with a you-know-you-want-me smirk that makes your heart race. Where did C get it? "It fell off a truck," C says, putting away the boltcutters. You start to feel like C doesn't know the meaning of "private" or "protected": what C wants, C takes. This excites you. C knows how to get you anything but safety. C will give you anything but commitment. In the end, you'll leave C, not because you want something better, but because you can't handle the intensity. C says "I'm gonna live fast, die young, and leave a good-looking corpse," but you know that C can never die, not so long as C is still the fastest thing on the road.

Class 19: Tries!

The goal today is to generate all of the words in a given rack.

Today's data structure of choice is a trie, also known as a radix tree or prefix tree.

The phrase "trie" is borrowed from the middle letters of retrieval.

Here's a picture containing call, cater, cake, cope, bat, bake:

The construct is simple. We make a tree where each node is a character (or an indicator that the word is done) and its children are follow up characters. Now all paths from the root to a leaf are words.

Comlexity Task 1: Imagine that you've loaded the entire dictionary into a structure like this. How long would take to check the existence of the word: ALGORITHMS?

Complexity Task 2: Given a rack of \(n\) tiles, how expensive is it to use a dictionary trie to find all \(m\) words in that rack?

The idea is simple enough. Now how should we implement it?

Choices to make

So we want to extend our idea of a binary search tree. Still nodes, but now instead of a binary tree we're a full blown tree (many children). How do we want to store the pointers to children?

• Option 1: an array of length 27 node pointers (26 letters and a possible null character), any null pointers don't exist.
• Option 2: a map (key/value store) of pointers by next letter
• Option 3: 2 pointers, Node* child and Node* sibling

That last one would look like this (for baby, bad, bank, box, dad, dance):

Analysis Task 3: Which one takes up the most space?

Analysis Task 4: Which one would perform the fastest?

Analysis Task 5: Which one takes the least space?

Trie with Map Nodes

Alright, so I coded this version of option 2 as a gift for you. I'll walk you through the process from nothing to done then give you a final task (load a whole dictionary with it).

Step 1: Insert a word, Check a word

STL Nonsense 6: What does the method hasChild(char key) do? How?

Insert Trace 7: Where is my recrusive step in insert? What happens when we get to an empty input? What happens when a letter in my word is not in the correct node?

Check Trace 8: In the pictures nodes contain a letter, in this version I didn't store a value in each node. How does hasWord work despite that choice?

Step 2: Traverse the tree

Understand 9: andy contains and. How does this printAll method display both?

Step 3: Collecting results

Difference 10: How is this snippet different than the last one?

Step 4: Dealing with a rack

This is just the choice I made, it might not be the best choice:

Analyze 11: I chose a histogram style rack (keys are tiles and values are the tile count). In my recursive step, why do I decrement and increment the value?

Apply It!

Now, if there is time, I want you to gather with your group (if they are here) and try to load the scrabble dictionary into a trie. Then display all of the words in the rack 'RETINAS'.

Other choices

So a trie is a classic data structure for this task (and fill-in boxes and spell checking etc). Other options for Scrabble games are listed at the bottom of the project 3 specs. Most of them are variations on this idea. The fastest takes 5 times as much space but allows you to walk forward or backward from a letter in a word.