Balanced Trees Compared: Red-Black Trees and TreeMap

UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 15.4 Free with a free account

Balanced Trees Compared: Red-Black Trees and TreeMap

Data Structures and Algorithms · Chapter 15: Balanced Search TreesSection 15.4 · lesson 66 of 879 min · free with a free account

← Multiway Search Trees: 2-3 Trees, 2-4 Trees, and B-TreesNext lesson: Elementary Sorts: Bubble Sort and Selection Sort →

Earn 3 college credits for Data Structures and AlgorithmsRecommended for credit by NCCRS · Computer Science 251 · self-paced · one payment, lifetime access
Enroll in Data Structures and Algorithms · $250 →Download the syllabus (PDF)

In this lesson

Red-black trees as 2-4 trees, compared with AVL trees and TreeMap.

  • Map each red-black tree rule to a matching 2-4 tree rule
  • Trace red-black insertion with recoloring and rotations on sorted keys
  • Compare red-black and AVL trees on height, search cost and deletion repairs
  • Use TreeMap and TreeSet navigation methods, range views and comparators correctly

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,326 words). Read along, or search it.

Opening Question

What Sits Inside TreeMap

Java programs rarely build their own balanced tree. They reach for TreeMap, and its documentation says what's inside: a red-black tree. Red-black trees look strange at first, with every node colored red or black. But they're an old friend in disguise: a 2-4 tree, written as a binary tree. So first the colors, then red-black trees against AVL trees on real measurements, and then TreeMap and TreeSet at work.

Encoding

Wide Nodes as Red and Black Groups

A 2-4 tree node holds one to three keys, and all its leaves sit at one depth. Wide nodes are awkward to code. So a red-black tree writes each wide node as a small group of binary nodes. A black node starts a group. A red node is glued to the black node above it. A 2-node is a single black node. A 3-node is a black node with one red child, on either side. And a 4-node is a black node with two red children. The middle key sits on the black node.

Rules

Red-Black Rules as 2-4 Rules

Every red-black rule is a 2-4 rule in disguise. The root is black. And a red node never has a red child, so a group holds at most three keys. Every path from the root down to a missing child passes the same number of black nodes. That count is the 2-4 tree's depth, called the black height. And a new node starts red: a new key joins an existing group, just as a key joins a 2-4 leaf. Reds can't stack, so the longest path is at most twice the shortest. The height is at most two times log base two of the quantity n plus one.

In Code

Insertion and the Balance Step

Here's insertion in Java. It inserts like a plain search tree, and every new node starts red. Then, on the way back up, balance looks for a black node over a red child over a red grandchild. That's a group of three keys in the wrong shape. There are four possible layouts. In each one, the middle key moves up as a red node, and the other two become separate black groups. That's a 2-4 node splitting, written with pointers. And after every insert, the root is painted black.

Worked Example

Inserting Keys in Sorted Order

Run it, inserting 10, 20, 30, 40, and 50, in order. Each line shows the tree, with R for red and B for black, and then its 2-4 view. At 30, the three keys would form a chain. The repair splits them: 20 on top, 10 and 30 below, all black. At 50, the red 40 has joined 20's group. In 2-4 terms, the root holds 20 and 40, over three leaves. Then 10 through 100, in sorted order. A plain tree would be a chain of ten levels. This one has five, and every 2-4 leaf sits on level three.

Measured Comparison

Red-Black Versus AVL Trees

How do red-black trees compare with AVL trees? A test built both from the same keys, sorted and random, up to 100,000. The AVL tree is flatter. With 100,000 sorted keys, it had 17 levels, against 22 for the red-black tree. But the average search was almost identical: 15.69 steps against 15.72. Most nodes aren't on the longest path. Both did about one repair per insert on sorted keys. Red-black trees win on deletes: at most three rotations, where an AVL delete may rotate at every level.

Decision Guide

AVL, Red-Black, B-Tree or Hash Table

So which structure fits which job? Many lookups and few updates, in memory: an AVL tree saves a few steps on the worst lookups. Frequent inserts and deletes, in memory: a red-black tree, which in Java usually means TreeMap. Data too large for memory, stored in disk blocks: a B-tree, with one wide node per block read. And if only exact lookups matter, with no order at all: a hash table.

Java Example

A Day of Bookings in a TreeMap

Now TreeMap in practice. This map keeps a day's bookings, with times written as numbers, so 1130 means half past eleven. Printing the map lists the keys in sorted order, whatever order they were put in. floorKey of 1200 is the latest start at noon or before: 1130. ceilingKey of 1200 is the first start at noon or after: 1400. subMap from 1000 to 1500 includes its start, and excludes its end. headMap of 1130 holds everything before 1130. And pollFirstEntry removes and returns the smallest entry. Each of these calls costs order log n.

Navigation Methods

Lower, Floor, Ceiling and Higher

The four navigation methods are easy to mix up. Lower is the largest key strictly below the query. Floor is the largest key at or below it. Ceiling is the smallest key at or above the query, and higher is the smallest strictly above it. So floor and ceiling may return the query itself, and lower and higher always skip past it. In the set 10 to 50, a query of 35 gives 30 for both lower and floor. A query of 40 is stored. Floor and ceiling return 40 itself, while lower drops to 30, and higher climbs to 50.

Quick Check

Navigation at the Edges

Quick check, with the same five keys. This program prints lower of 10, floor of 45, ceiling of 45, and higher of 50. What does it print? Pause and predict. It prints null, 40, 50, null. Nothing is below 10, so lower of 10 is null. Lower never returns the query itself. 45 isn't stored, so floor and ceiling are its neighbors, 40 and 50. And nothing is above 50, so higher of 50 is null too.

Range Views

SubMap Is a Window, Not a Copy

Range methods like subMap don't copy anything. They return a view: a window onto the original map. Here the window covers keys 20 through 40. Passing true for both ends includes both of them. Clear the window, and those three entries vanish from the map itself. If a range must stay separate, copy it into a new TreeMap first.

Common Surprise

The Comparator Decides Duplicates

Here's a surprise. A TreeSet or TreeMap never calls equals. Two keys count as the same whenever the comparator returns zero for them. With natural string order, capital letters sort first. So APPLE comes before Banana, and apple is a different key. The size is four. With a case-insensitive comparator, apple and APPLE compare as equal. The set keeps the first one it saw, so its size is three. A map works the same way. Put Tree, then TREE: the second put replaces the value, and the key stays as first written.

Quick Check

A Set Ordered by Length

Quick check, with a new comparator. This set orders words by their length. Five words are added: pear, fig, kiwi, apple, and plum. What gets printed? Pause and predict. It prints fig, pear, apple. The comparator looks only at length, so kiwi and plum tie with pear. It returns zero, and the set treats them as duplicates. A duplicate add is simply ignored, so the first four-letter word, pear, stays. Alphabetical order never comes into it. To keep all five, the comparator must break ties, for example by comparing the words themselves next.

Robustness

Sorted Keys Without Stack Overflow

Remember the plain search tree that ran out of call stack on 200,000 sorted keys? TreeMap takes the same keys without trouble. It rebalances as it goes, so its height stays logarithmic, and every put and get is a short walk.

Comparison

TreeMap Versus HashMap

Finally, TreeMap or HashMap? Put five names into each. The HashMap lists them in an order that Java doesn't promise. The TreeMap lists them alphabetically, every time. A HashMap's get and put take expected constant time. A TreeMap's take order log n, but it can answer floor, ceiling, and range questions. So use HashMap when only exact lookups matter, and TreeMap when the keys must stay in order, or nearby keys are needed.

Key Takeaways

Colors, Comparisons and TreeMap

To sum up. A red-black tree is a 2-4 tree in binary form. A black node starts a group, and red nodes join it. Equal black counts on every path keep the height under two log n. AVL trees are a little flatter, red-black trees repair less, and B-trees suit disks. TreeMap and TreeSet give sorted order, floor, ceiling, and range views, in order log n. And the comparator alone decides which keys count as duplicates.

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

How programs store and search dataData Structures and Algorithms teaches how to organize data and measure how fast code runs: arrays, linked lists, stacks, queues, trees, heaps, hash tables, sorting and graphs, all written in Java. It is a core course in computer science and software degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

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 UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks 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 Balanced Trees Compared: Red-Black Trees and TreeMap

How is a red-black tree related to a 2-4 tree?
A red-black tree is a binary encoding of a 2-4 tree: each black node together with its red children forms one 2-4 node of one, two or three keys. The color rules mirror the 2-4 rules. No red node has a red child, so a group never exceeds three keys, and every path from the root to an empty link passes the same number of black nodes, matching the rule that all 2-4 leaves share one depth.
Is an AVL tree or a red-black tree better?
An AVL tree is flatter, while a red-black tree does less repair work on deletion. A red-black tree can reach about twice the minimum height; with 100,000 sorted keys, one test gave 22 levels for red-black against 17 for AVL. Yet average searches were nearly equal, 15.72 against 15.69 steps. A red-black deletion needs at most three rotations, while an AVL deletion may rotate at every level.
Why does Java's TreeMap use a red-black tree?
A red-black tree guarantees O(log n) search, insertion and deletion, with a height of at most 2 log2(n + 1), even when keys arrive already sorted. Its repairs are cheap, at most two rotations per insertion and three per deletion, with any other fixes done by recoloring. That keeps TreeMap's ordered operations, including firstKey, floorKey, ceilingKey and subMap, fast in the worst case.
Why does a TreeSet with a comparator drop some elements?
A TreeSet treats two elements as duplicates whenever its comparator returns 0, even if equals says they differ. With new TreeSet<String>(Comparator.comparingInt(String::length)), adding pear, fig, kiwi, apple and plum keeps only [fig, pear, apple], because kiwi and plum have the same length as pear. Adding a tie-breaker, as in Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()), keeps all five.

About the Data Structures and Algorithms course

How many college credits is Data Structures and Algorithms?
Data Structures and Algorithms (Computer Science 251) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Data Structures and Algorithms cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Data Structures and Algorithms take?
It is self-paced with no deadlines. The 87 lessons total about 15 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

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.

Enroll in Data Structures and Algorithms →Download the syllabusEvery course with PRO →
Data Structures and Algorithms
3 credits · NCCRSEnroll →