Isomorphism

LLRB trees, quicksort, and counting sorts.

1. Left-Leaning Red-Black Trees
   1. Rotation
   2. One-to-one correspondence and isomorphism
   3. What would a 2-3 tree do?
2. Quicksort
   1. Partitioning
   2. Single-pivot quicksort
   3. Dual-pivot quicksort
3. Counting Sorts
   1. Sorting decision tree
   2. Counting sorts and enumeration
   3. Radix sorts
   4. 3-way radix quicksort

Left-Leaning Red-Black Trees

1. Given a 2-3 tree, identify its corresponding LLRB tree (and vice-versa).
2. Apply rotations and color flips for a single LLRB tree insertion.
3. Using 1-1 correspondence, give the LLRB tree for a series of insertions.

Although 2-3 trees addressed the worst-case runtime problem with binary search trees by overstuffing and splitting nodes, they are rarely used in the real world. Overstuffing and splitting nodes involves constructing many 2-nodes and 3-nodes, which is not only complicated to design and implement, but also incurs a significant runtime cost since new nodes are constantly created or removed from a 2-3 tree. While this doesn’t affect the asymptotic analysis, it is often noticeable in experimental analysis.

In Java, TreeSet is the standard implementation of a set that uses a self-balancing binary search tree data structure called a red-black tree. We were careful to note that 2-3 trees were not binary search trees because 3-nodes (nodes with 2 keys and 3 non-null children) can’t be found in a binary search tree. The difference with red-black trees is that they are valid binary search trees. Red-black trees take the idea of overstuffing and splitting in a 2-3 tree and map them back to binary search tree operations. This data structure has all the asymptotic runtime guarantees of a 2-3 tree without the experimental runtime slowdowns.

Rotation

Before we introduce red-black trees formally, we’ll first need a way to reorganize elements in a binary search tree. Depending on the order elements are inserted into the tree, there are many different ways to construct a binary search tree containing the same set of elements. But insertion order is not the only way to build different configurations of the same set of elements. We can change the structure of a binary tree through rotation.

Each rotation makes a local adjustment to the tree. Sometimes, this local adjustment increases the height of the tree; other times, it decreases the height of the tree; and in yet other times the overall height of the tree might not change at all. However, rotations always respect the binary search tree invariant. Elements that are ordered between B and D in the example below stay ordered after a rotation.

Given a particular node in a tree, we can either rotate it to the left or to the right by making it the child of one of its parents. In these definitions, G and P correspond to their labels in the tree shown below.

rotateLeft(G)

Let x be the right child of G. Make G the new left child of x. We can think of this as temporarily merging G and P, then sending G down and left.

rotateRight(P)

Let x be the left child of P. Make P the new right child of x. We can think of this as temporarily merging G and P, then sending P down and right.

These two rotations are inverse operations: one operation undoes the other.

One-to-one correspondence and isomorphism

Our goal is to develop a self-balancing binary search tree using the self-balancing property of 2-3 trees. Certain 2-3 trees are already valid binary search trees. 2-3 trees that only contain 2-nodes are already valid binary search trees. How might we represent 3-nodes in a binary search tree?

Using an idea from rotation, we can separate a 3-node with the keys B and D into two nodes exactly as shown during the node rotation process. A left-leaning binary search tree is a binary search tree representation of a 2-3 tree where 3-nodes are represented as two binary tree nodes connected with a left-leaning “glue” edge.

The preference for left-leaning is historical and cultural: perhaps if the data structure inventors preferred how right-leaning looked, we might instead be learning about right-leaning binary search trees instead. Either approach is equally good as long as we’re consistent in our decision.

We now have a complete binary search tree representation for any 2-3 tree. The steps for converting a 2-3 tree are as follows. For each node:

• If the node is a 2-node, then leave it the same since it’s already a valid binary tree node.
• Otherwise, the node is a 3-node, so represent it with 2 binary tree nodes with a left-leaning “glue” edge.

Converting from 2-3 trees to left-leaning BSTs is not too bad. But the opposite is not so easy! In the slides above, it’s hard to tell that d and f are the two nodes that are glued together in the 2-3 tree. This is even harder to do in code, so today’s topic of left-leaning red-black trees introduces a little bit of extra information in the form of a colorful “glue” edge.

The left-leaning red-black (LLRB) tree data structure is exactly the same as left-leaning BSTs except “glue” edges connecting 3-nodes (in the corresponding 2-3 tree) are colored red. Red edges help us immediately tell which nodes are part of a 3-node in the corresponding 2-3 tree.

One-to-one correspondence (bijection)

A mapping between two types of elements where elements of each type are paired with exactly one other element of the other type. One-to-one correspondence between 2-3 trees and LLRB trees implies that every 2-3 tree has a unique corresponding LLRB tree associated with it, and vice versa.

Algorithmic isomorphism

A one-to-one correspondence between two types of data structures or algorithms that also preserves structure. Isomorphism between 2-3 trees and LLRB trees implies that a change in a 2-3 tree produces a proportional change in the isomorphic LLRB tree, and vice versa.

LLRB tree invariants follow entirely from isomorphism with 2-3 trees.

• Red edges lean left because that’s the convention we chose to represent 3-nodes.
• No node has two red edges connected to it because 2-3 trees only allow 2-nodes and 3-nodes.
• Every root-to-null path has the same number of black edges because all 2-3 tree leaf nodes are the same depth from the root.

We’ll often use “corresponding” and “isomorphic” interchangeably, but isomorphism is a stronger and more descriptive term because it implies the structure-preserving property. Isomorphism allows us to switch between thinking about a 2-3 tree as an LLRB tree or vice versa at any point in time.

What would a 2-3 tree do?

Isomorphism enables a powerful way of thinking about LLRB tree operations. In any situation, we can always ask: What would a 2-3 tree do?

The following slides visualize the procedure for adding several elements to a LLRB tree. Nodes are recursively added to the LLRB tree as new leaf nodes just like in a binary search tree. After reaching the recursive base case and creating the new leaf node, before returning, the program will perform rotations and color flips to maintain LLRB tree invariants.

LLRB tree balance is maintained using only 3 lines of code. But it’s also possible to reason about the data structure by visualizing the corresponding 2-3 tree: try simulating the sequence of insertions from the slides below in the 2-3 Tree Visualization and compare the results.

Quicksort

1. Compare comparison sorting algorithms on efficiency and stability.
2. Given the runtime of a partitioning algorithm, describe the runtime of quicksort.
3. Describe the search trees analogies for quicksort algorithms.

Isomorphism not only inspires new ideas for data structures, but also new ideas for algorithms too. In our study of sorting algorithms, we learned that a sorting algorithm is considered stable if it preserves the original order of equivalent keys. Which sorting algorithms does Java use when you call Arrays.sort? It depends on whether we need stability.

Stable system sort

When sorting an array of objects (like emails), Java uses a sorting algorithm called Timsort, which is based on merge sort and has the same linearithmic worst-case runtime as merge sort.

Timsort is a hybrid sort that combines ideas from merge sort with insertion sort. Experimental analysis reveals that the fastest sorting algorithm for small arrays is often insertion sort. Instead of merge sort’s base case of 1 element, Java Timsort uses a base case of 32 elements which are then insertion sorted. Insertion sort can be further sped up by using binary search to find the insertion point for the next unsorted element.

Timsort is also an adaptive sort that changes behavior depending on the input array. Many real-world arrays are not truly random. They often contain natural runs, or sorted subsequences of elements that could be efficiently merged. Rather than recursively dividing top-down, Timsort works bottom-up by identifying natural runs in the input array and combining them from left to right.

Unstable system sort

When sorting an array of numbers or booleans, Java uses a sorting algorithm called quicksort. Quicksort has many variants, but we’ll focus on two in this course:

1. Single-pivot quicksort, which is isomorphic to binary search trees.
2. Dual-pivot quicksort, which is like a 2-3 tree that only contains 3-nodes.

Partitioning

Quicksort relies on the idea of recursively partitioning an array around a pivot element, data[i].

A partitioning of an array rearranges its elements in a weaker way than sorting by requiring elements in the order:

• All elements to the left of the pivot are less than or equal to the pivot element.
• The pivot element, data[i], moves to position j. (The pivot might not need to move.)
• All elements to the right of the pivot are greater than or equal to the pivot element.

Single-pivot quicksort

Partitioning an array around a pivot element in quicksort is like selecting a root element in a binary search tree. All the elements in the left subtree will be less than the root element, and all the elements in the right subtree will be greater than the root element.

The quicksort on the left always chooses the leftmost element as the pivot element and uses an ideal partitioning that maintains the relative order of the remaining elements. The binary search tree on the right shows the result of inserting each element in the left-to-right input order given by the array.

Open the VisuAlgo module to visualize sorting algorithms. Press Esc to exit the e-Lecture Mode, and choose QUI from the top navigation bar to switch to quicksort. Run the sorting algorithm using Sort from the bottom left menu.

Sorting Visualization

Note that the visualization does not use an ideal partitioning algorithm for quicksort.

Dual-pivot quicksort

Dual-pivot quicksort chooses 2 pivots on each recursive call, just like how 3-child nodes in 2-3 trees maintain 2 keys and 3 children. If choosing 1 pivot element is like choosing 1 root element in a binary node, then choosing 2 pivot elements is like choosing 2 root elements in a 3-child node.

Strictly speaking, dual-pivot quicksort is not isomorphic to 2-3 trees because there does not exist a one-to-one correspondence. Consider 2-3 trees that only contain 2-child nodes: the corresponding quicksort is single-pivot quicksort, not dual-pivot quicksort.

Partitioning an array around 2 pivot elements, p₁ and p₂ where p₁ ≤ p₂, rearranges its elements by requiring elements in the order:

• All elements less than p₁.
• The pivot element p₁.
• All elements x where p₁ ≤ x ≤ p₂.
• The pivot element p₂.
• All elements greater than p₂.

Dual-pivot quicksort is a relatively new algorithm published in 2009. Experimental analysis revealed that dual-pivot quicksort is significantly faster than single-pivot quicksort on modern computers. Computer scientists attribute the performance improvement due to advances in CPU caching and memory hierarchy since the 1960s and 1970s when single-pivot quicksort was first introduced.

Counting Sorts

1. Explain the worst-case lower bound for comparison sorting.
2. Describe counting sort, MSD radix sort, and LSD radix sort.
3. Explain how the subsort is used in MSD and LSD radix sort.

In practice, Java’s system sorts like Timsort and dual-pivot quicksort have a linearithmic order of growth. Is it possible to sort in faster than worst case Θ(N log N) time? In the best case, we know that sorting algorithms like insertion sort can tell that an already-sorted array is indeed sorted in linear time. But can we design an algorithm that sorts an array of N elements in linear time in the worst case?

Sorting decision tree

We can start by asking, “How many comparisons do we need to make in order to know how to sort an array?” We’ve actually already asked this question before: in merge sort, we relied on knowing that a single element subarray is already sorted with respect to itself. In other words:

• Sorting an array with 1 element requires 0 comparisons.
• Sorting an array with 2 elements requires 1 comparison.
• Sorting an array with 3 elements requires either 2 or 3 comparisons depending on the questions.

We can draw a sorting decision tree to see exactly what questions we need to ask to determine the sorted order for 3 elements. Each leaf in the decision tree represents a possible sorted order for the elements, and each branch represents a choice of answering either “Yes” or “No” to each comparison question.

This decision tree is not only a conceptual visualization, but it can also be implemented as a program consisting of a hierarchy of nested if conditional statements. This decision tree represents the optimal comparison sorting algorithm: a comparison sort that requires the absolute least number of comparisons to sort a given input array.

if (a < b)
    if      (b < c) return {a, b, c};
    else if (a < c) return {a, c, b};
    else            return {c, a, b};
else
    if      (a < c) return {b, a, c};
    else if (b < c) return {b, c, a};
    else            return {c, b, a};

If N elements have N! factorial potential permutations, and each potential permutation is a leaf in a balanced sorting decision tree, then the optimal comparison sorting algorithm in the worst case needs about log₂ N! comparisons to determine the correct sorting of the elements. Stirling’s approximation can be used to show that log₂ N! ∈ Θ(N log N).

In other words, the optimal comparison sorting algorithm requires Θ(N log N) comparisons in the worst case. It’s not possible to design a comparison sorting algorithm that takes linear time in the worst case.

Counting sorts and enumeration

The worst case lower bound on comparison sorting algorithms only apply to comparison sorts that use operations like <, >, or compareTo to determine the order of elements. A counting sort sorts an array of elements by relying on enumeration instead of comparison. Elements are considered comparable if they can be compared with one another. Elements are considered enumerable if they can be listed-out in a sequence from first to last.

Counting sort

1. Create a count array that will be used to store the number of times each element occurs in the input array.
2. Iterate over the input array, updating the count array to reflect the occurrence of each element.
3. Iterate over the count array, unraveling the number of times each element occurs back into the input array.

Open the VisuAlgo module to visualize sorting algorithms. Press Esc to exit the e-Lecture Mode, and choose COU from the top navigation bar to switch to counting sort. Run the sorting algorithm using Sort from the bottom left menu.

Sorting Visualization

Radix sorts

Counting sorts work great with small integer values when we know the range between the smallest integer and the largest integer. But many other data types, like strings, are more difficult to enumerate because we can always make a more complicated string. For example, suppose we have a string “a” and we decide to put it at index 0 in the count array. Where would the string “b” belong in the count array? We know it comes after “a”, but how far after “a”? We might run into strings like “aa”, “aaa”, “aaaa”, etc. and not know how many spaces to reserve for these elements.

To address this issue, we can take inspiration from tries. Just as tries divided a string into its constituent letters and processed each letter individually, we can do the same and apply counting sort on each letter. Radix sorts represent a category of counting sorts that divide strings (or string-like objects) into individual subunits that can be separately counting-sorted.

Most-Significant Digit (MSD) radix sort

Starts from the leftmost (in English, the most significant) character and proceeds to the right.

Recursively counting sorts the characters separately, proceeding to the next index into the strings.

Least-Significant Digit (LSD) radix sort

Starts from the rightmost (in English, the least significant) character and proceeds to the left.

For each index into the strings, iteratively counting sorts all the elements again on the current index.

Open the VisuAlgo module to visualize sorting algorithms. Press Esc to exit the e-Lecture Mode, and choose RAD from the top navigation bar to switch to an LSD radix sort. Run the sorting algorithm using Sort from the bottom left menu.

Sorting Visualization

3-way radix quicksort

Is there a sorting algorithm analogy for ternary search trees? It exists, and it combines the ideas of radix sort with quicksort just like how ternary search trees represent a midpoint between tries and binary search trees.

3-way radix quicksort

Select a pivot element for the current index into the strings.

Partition the array into elements less than, equal to, and greater than the pivot element.

Recursively sort each of the less than, equal to, and greater than subarrays.