UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 12.3 Free with a free account
Choosing the Right Tree: Layouts and Applications
Data Structures and Algorithms · Chapter 12: TreesSection 12.3 · lesson 51 of 8711 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Data Structures and Algorithms.
Lesson complete
Earn the 3 college credits for Data Structures and Algorithms
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: The Priority Queue: Why Some Lines Need to Prioritize →← Binary Trees: Structure, Properties, and TraversalsNext lesson: The Priority Queue: Why Some Lines Need to Prioritize →
In this lesson
Matching heaps, search trees, B-trees, tries and more to tasks.
- Compare the shape and ordering rules of seven common kinds of tree
- Explain why search cost follows the number of levels in a tree
- Identify the strongest operation and main limit of each tree
- Choose a tree for a problem by starting from its most frequent operation
Free study notes
Get this lesson's notes by email
The key points and 4 practice questions with answers, in your inbox. One email, free.
One email. Unsubscribe in one click.
Transcript
Everything said in the video, section by section (1,685 words). Read along, or search it.
Opening Question
Every Tree Makes One Promise
Your phone's autocomplete, a bank's database index, a calculator, and a hospital waiting list all use trees. And each of them uses a different tree. Why not just pick one good tree and use it everywhere? Because every tree makes one promise. It forces its nodes into a particular shape, and that shape makes one operation fast. Choosing a tree means choosing the promise your problem needs.
Key Terms
Shape Rules, Ordering Rules and Levels
Two words for this lesson. A shape rule says how the nodes may be arranged. An ordering rule says how the values must relate to each other. And since this lesson compares measured trees, it counts levels: the number of nodes on the longest path from the root down. A single node is one level.
Overview
Seven Trees and Their Rules
Here are the seven trees. A binary search tree keeps smaller keys left and larger keys right. An AVL tree is a search tree that also keeps sibling subtrees within one level of each other. A heap is a binary tree filled row by row, where every parent comes before its children. A B-tree packs many keys into each node, with all its leaves at the same depth. A trie spells words one letter per step, so words with the same beginning share a path. An expression tree holds a formula: values at the leaves, operators inside. And a decision tree asks a question at each inner node, with the answers at its leaves. The first four order values. The last three have no ordering rule at all.
Strengths
Each Tree's Strongest Operation
Each one's strongest operation follows from its rule. Search trees find, insert and remove by key. The AVL tree adds a speed guarantee. A heap reads and removes its smallest or largest item. A B-tree searches with very few node reads, a trie searches by prefix, and the last two evaluate a formula, or reach a decision. In Java, TreeMap and TreeSet are balanced search trees: red-black trees, a close cousin of the AVL tree, with the same speed promise. PriorityQueue is a heap. The other trees, you build or import.
Why Shape Matters
A Chain Versus Three Levels
Why does the shape rule matter so much? Searching, inserting and removing in a search tree all walk one path down from the root, so the cost is about the number of levels. The ordering rule alone doesn't control that. Feed the keys one to seven, in increasing order, to a plain binary search tree. Each key goes to the right of the last, and you get a chain. Feed the same keys, in the same order, to an AVL tree, and its shape rule keeps it three levels tall. Seven levels against three, from the very same keys.
Measured Results
Sorted Versus Random Keys
This isn't a toy effect. Build both trees with a thousand keys, once in sorted order and once at random, and measure. Sorted keys ruin the plain tree: a thousand levels, and five hundred comparisons on average to find a key. It has become a linked list. Random keys rescue it, but only by luck: in one test run, twenty-seven levels. The AVL tree doesn't depend on luck: ten levels for sorted keys, twelve for random. The fewest possible for a thousand keys is ten. At ten thousand keys, the pattern repeats: ten thousand levels for the sorted plain tree, fourteen for the AVL tree.
Cost Summary
What Each Tree Charges
So here's what each tree charges. A plain search tree costs order log n on average, but order n in the worst case. The AVL tree costs order log n always. A heap gives its smallest item in constant time, removes it in order log n, but searching it for a key is order n, because there's no order across the whole tree. A B-tree is order log n with a very large base, so it has very few levels. And a trie costs the length of the word, however many words it holds.
Quick Check
Increasing Timestamps in a Search Tree
Quick check. A logging system stores a hundred thousand timestamps in a plain binary search tree. Timestamps only ever increase. About how many levels does the tree end up with? Pause, and decide. It's c: about a hundred thousand. Each new timestamp is larger than every key before it, so it always goes right. The tree is a chain. Seventeen is what an AVL tree would give, since its shape rule forbids a chain. Fifty thousand is the average number of comparisons, not the levels.
Experiment
A Heap Is Not Sorted
Now one experiment per tree, showing its promise and its limit. A heap: add five, three, eight, one, nine and two to Java's priority queue, and print it. It prints one, three, two, five, nine, eight. That's the heap read row by row, and it isn't sorted. A heap only promises each parent comes before its children. Taking items out one at a time with poll does give sorted order: one, two, three, five, eight, nine. And a heap of a million items has only twenty levels.
Experiment
Ends, Neighbors and Ranges in a TreeMap
A balanced search tree keeps every key in order. Put fifty, twenty, seventy, ten, thirty, sixty and eighty into a TreeMap. The keys come back sorted. The first key is ten, and the last is eighty. The floor of sixty-five, the largest key at or below it, is sixty, and its ceiling is seventy. And the sub map from twenty-five up to sixty-five holds thirty, fifty and sixty. Both ends, neighbors, and ranges: a heap can't answer any of those.
Experiment
Fewer Disk Reads With Wide Nodes
A B-tree fights a different cost. Reading one node from a disk is thousands of times slower than reading one from memory, so the number of levels is what counts. For fifty million keys, with every node full, a binary tree needs twenty-six levels. Four children per node, thirteen. A hundred children per node: about four. A thousand: three. Twenty-six disk reads against four. That's why databases and file systems use B-trees.
Experiment
Shared Prefixes in a Trie
A trie: the path spells the word. Store car, card, care, cat, dog and do. Together they have nineteen letters, but the trie needs only ten nodes, root included, because words share their beginnings. Type c a, and the search follows two letters, then lists everything below: car, card, care and cat. The work depends on the length of the prefix, not on how many words are stored. The price is memory: every node can point to many letters.
Experiment
The Shape Is the Formula
An expression tree: the shape is the formula. Three plus four, times two, puts times at the root, plus below it on the left, and the values three, four and two as leaves. Nothing is sorted. Visit left, node, right with brackets, and you get the usual notation. Left, right, node gives three four plus two times. Node, left, right gives times plus three four two. The value is fourteen whichever way you write it, and the tree needs no brackets: the position of each operator says what comes first.
Experiment
Questions Leading to a Travel Choice
A decision tree turns a rule into questions. How should I travel? Is it raining? If yes, do I have an umbrella? If not raining, is the trip far? Raining with no umbrella: take the bus. Raining with an umbrella: walk. Dry and short: walk. Dry and far: bus. Every case is decided after two questions, because the tree is two levels of questions deep. The number of questions is bounded by the height.
Decision Guide
Questions to Pick a Tree
So how do you choose? Start from the operation your program does most, not from the data, and ask these questions in order. Stop at the first yes. Do you only ever need the smallest or largest item next? Then a heap. Are the items words, searched by their beginning? A trie. Is the data on disk, or too big for memory? A B-tree. Does it describe a formula? An expression tree. Are you sorting cases into answers by asking questions? A decision tree. Do you need sorted, in-memory lookup with a guaranteed speed? An AVL tree, or Java's TreeMap. Only if none of these apply does a plain search tree make sense.
Quick Check
A Leaderboard Too Big for Memory
Quick check. A game keeps a leaderboard of four hundred million players, too big for memory, so it lives on disk. It must answer questions like: who scored between five hundred and six hundred? Using the guide, which tree should it use? Pause, and decide. It's c, a B-tree. A heap fails the first question, since ranges need more than the top item. A trie doesn't apply. Then comes the disk question, and the answer is yes, so the guide stops there. An AVL tree answers ranges too, but on disk it would need about twenty-nine reads per lookup, where a B-tree needs a handful.
Combined Needs
When One Promise Is Not Enough
Real problems often combine needs. A min heap gives only one end. Peek shows the smallest, but the largest is somewhere among the leaves, so finding it means scanning. If you need both ends plus ranges, choose the balanced tree. If you only need the next most urgent item, the heap does less work. Notice that each domain wants one promise: B-trees in databases, expression trees in compilers, tries in search boxes, heaps in schedulers, and balanced trees behind sorted maps.
Common Mistakes
Four Classic Tree Mistakes
The classic mistakes follow. Feeding sorted keys to a plain search tree. Expecting a heap to be sorted, or searching it for a value. Using a binary tree for data on disk: twenty-six reads where a B-tree needs four. And treating expression and decision trees as search trees: their shape carries meaning, with no ordering rule.
Key Takeaways
Match the Promise to the Operation
To recap. Each tree makes one operation fast by forcing a shape on its nodes, so choose the tree whose promise matches your main operation. Search cost follows the number of levels. Sorted input turns a plain search tree into a chain, while an AVL tree stays near the minimum. A heap gives the smallest or largest first, but isn't sorted. A balanced tree answers ends, neighbors and ranges. B-trees cut disk reads, and tries search by prefix.
Think About It
Urgent Patients and Arrival Ranges
Here's something to think about. A hospital system must always treat the most urgent patient next, but staff also ask for every patient who arrived between two and three o'clock. Is one tree enough? Or does the system need two structures, and if so, which two?
About Data Structures and Algorithms at UPI Study
Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →
Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms
Why take it here
Why students take Data Structures and Algorithms with UPI Study
Where the credit goes
Universities that work with NCCRS
Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About Choosing the Right Tree: Layouts and Applications
Why does a balanced tree beat a plain binary search tree on sorted input?
Why do databases use B-trees instead of binary search trees?
How do you choose the right tree data structure for a problem?
Why can't a heap answer range queries like a TreeMap can?
About the Data Structures and Algorithms course
How many college credits is Data Structures and Algorithms?
How much does Data Structures and Algorithms cost and what is included?
Which universities accept UPI Study credits?
How long does Data Structures and Algorithms take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in Data Structures and Algorithms.
87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →