Category Archives: Data Structures

My Vote Goes to Red-Black

On Geomblog, Piotr mentioned a problem that I think many of us can share: if we really have to pick just one to teach (as in his case), do we go with 2-4 trees or red-black trees?

For the most part, the pros and cons of the two approaches are quite, urr, balanced. :P But there has been one critical issue that tilt my preference towards RB. On the surface, the issue is “augmentation”, ala CLRS chapter 14 style. But it really is about the number of rotations used during insertions and deletions…

There is a fascinating history behind this, which is summarized by Ottmann and Wood up to 1990. It all started with a design from Olivie and a swift response from Tarjan. The rest of the juicy bits, well, I offer no spoiler. This post merely needs the following fact to make sense: in the worst case, some implementations of RB need only $O(1)$ rotations during restructuring and the remaining work are color changes; some implementations need logarithmic number of rotations.

But if we can afford a logarithmic number of color changes in the worst case, isn’t it just “a matter of constants” even if we have to do a logarithmic number of rotations as well?

In many cases, the answer is indeed yes, but there is no lack of interesting cases due to augmentations that make rotations “expensive”. For a starter: see section 13.4 of Bob’s textbook, pp 570-571 in the C++ 3rd edition, where this very issue is raised and the model answer is presented. Here is a favorite example of mine: Seidel and Aargon used this to highlight why treaps are preferable to splay trees in applications like segment trees. Let’s end with one more related to this post: McCreight’s priority search trees, used as the motivating example in Ottmann and Wood, also critically rely on search trees that use only $O(1)$ number of rotations to restructure. More precisely, doing $p$ rotations yields a bound of $O(p \log n)$. See, it’s not just in the constants!

I will finish this by saying that this doesn’t imply a landslide victory for RB. Conceptually, 2-4 trees are really hard to beat! In fact, even though I would be speaking RB in my mouth, I would be thinking about 2-4 at the back of my mind! (Kind of like some foreign language speakers, no? Ten years ago I was exactly like this, haha.) And really, if we ever get to more advanced stuff like supporting finger searches, I will pick 2-4 on most but not all days. Complications… complications… :P

Exercise: To understand how a 2-4 speaker would speak in RB, what is “black-height” in the 2-4 language?

Reference: Thomas Ottmann, Derick Wood: How to Update a Balanced Binary Tree with a Constant Number of Rotations. SWAT 1990: 122-131

A Small Constant

This is not a post to argue for or against the big-O notation. Instead I just want to share an observation using a toy example.

Consider a dictionary data structure that supports access in logarithmic time. Suppose we have two implementations A and B where A is two times faster than B. (To make it precise but toyish, imagine an access takes $\log n$ time and $2 \log n$ time respectively where $n$ is the number of elements.)

How would this factor of two become important?

Well, when there is a hard upperbound on the amount of time allowed in an access, then the maximum number of elements that can be stored in A is actually the square of that of B.

It’s squared, not just doubled.

Now here’s something to think about. You can have a digital photo album that can store a maximum of two thousand photos or another one with four million photos. They are equally responsive on your computer. Which one would you prefer as a customer?

(Or, perhaps we can wait 18 months and be happy with the former one? :P )

Deamortization – Part 2: Binomial Heaps

In Part 1, I have shown how you can increment a “binary” counter in `O(1)` time if you use a redundant number system. Now I am going to show you how you can apply this simple abstraction to deamortize Binomial Heaps (here is the Wikipedia page for Binomial Heaps if you want a refresher).

Where does the amortization come in for Binomial Heaps? Well, all the time bounds are indeed stated as worst-case bounds. But, as is commonly taught in many places, you can have a more precise time bound for Insert if you do an amortized analysis. The argument is particularly simple if we use a binary counter abstraction.

We will encode the configuration of the binomial trees using a binary counter `d_{log n}…d_1d_0`. We set `d_i` to be 1 iff a binomial tree of rank `i` is present. Inserting into a binomial heap is now precisely incrementing this counter. Linking two binomial tree of rank `i` to form a binomial tree of rank `i+1` is exactly converting a 2 in `d_i` to a 1 in `d_{i+1}`. Guess there must be a reason why it’s called a binomial heap. :)

The amortized analysis can be done using the credit invariant method. We argue that over a series of `n` insertions, the digits only changed at most `2n` times. For each rank (digit), we open a bank account. Each insertion pays two dollars: one spent immediately for the actual insertion and one deposited at the account of the first 0 that turned into a 1—observe that precisely one 0 will turn into a 1 in every increment as the propagation will stop immediately afterwards. The dollar deposited in the account of this 1 will be used to turn it back into a 0 during a future insertion.

Check that we will have enough money to pay for all digit changes during any insertion. As we never go bankrupt, we conclude that 2 dollars per insertion is enough. In other words, insertion actually takes “only” amortized `O(1)` time.

Equipped with our technology from Part 1, now we can implement insertion in worst-case `O(1)` time simply by using a redundant counter. Indeed we will allow two binomial trees of rank `i` to co-exist for a while, until the counter needs to link the two when fixing its regularity. Simple enough.

For those of you who want to know how redundant counters were invented in the first place, see

  • Michael J. Clancy and Donald E. Knuth. A Programming and Problem-Solving Seminar. Technical Report STAN-CS-77-606, Computer Science Department, Stanford University, April 1977.

Note that over the years many extensions to redundant counters have been developed, and in fact the terminologies used in this series are “modern”. We will talk more about those in the future.

Deamortization – Part 1: Redundant Number Systems

In the positional number system of base `b`, the representation `d_{n}d_{n-1}…d_{1}d_{0}` denotes the number `\sum_{i = 0}^{n} d_i b^i`. For example, the binary (`b = 2`) number `(1001)_2` is 8 + 1 = 9. Notice that when `d_i \in {0, …, b – 1}`, there is only one way to denote any number. This is what we are all used to.

In a redundant number system, we allow `d_i` to be chosen from a larger set of digits. For this series, we will stick to `{0, …, b – 1, b}`. To make things even more concrete, we further set `b` to 2, i.e., we are considering the redundant binary numbers with the sets of digits {0, 1, 2}.

The decimal number 9 can still be written as `1001` in binary (I am dropping the subscripts and will display binary numbers in math mode). But since we are using the redundant binary system, we also have other choices. In particular, `201` (2 * 4 + 1 = 9) and `121` (4 + 2*2 + 1 = 9) are also valid representations.

Let me introduce three terms before I continue.

  • We say that a redundant binary number is regular if the 2s and 0s alternate. So `2012` is regular, but `2120` is not.
  • When the last non-1 digit of a redundant binary number is 0, we say that it’s 0-exposed. For example, `2001` is 0-exposed. (But note that it is not regular.)
  • When the last non-1 digit is 2, we say that it is 2-exposed. For example, `2102` is 2-exposed.

The regularity constraint is very special. First, convince yourself that even when restricting to regular representations, there are still redundancy in the representation of a number. For example, both `1202` and `1210` denote 18 and both of which are regular since the 2s and the 0s alternate.

Also note that if a number is either 2-exposed or 0-exposed.

The only operation that we will consider in this post is:

  • add 1 to the least significant digit of a number (i.e., the rightmost)

We will denote this operation with an intuitive expression. For example, consider `12(1+1)`. That would be `122`. Easy, huh?

Let’s repeat the operation one more time. Hmm, `12(2+1)` would be `123`, but that wouldn’t be too good since 3 is not an allowed digit. Well, we need carry. `123` = `131` = `211`. OK, problem solved.

At this point, make sure you know how to do this add-one-to-the-last-digit operation.

For those of us that own the whole series of the Worst-Case Scenario Survival Handbook :) , you will have noticed that this operation can take time linear to the number of digits. Consider the input `22222222222222222(2+1)`. Oh no!

This is where the regularity constraint comes in. Suppose the number you start with is regular. How long can add-1 take? Consider the last digit of the number.

  • If it’s a 0 or 1, then you can just bump it up to 1 or 2 respectively.
  • If it’s a 2, then we need to carry 1 to the next digit (to the left). Ah! But since the number is regular, that digit cannot be a 2. The previous case now applies.

So in at most two steps, we will be done. That’s like `O(1)` time, right?

But, we may not be left with a regular number any more. For example, `12(1+1)` is `122` and that’s not regular. The key observation is that we will end up with an irregular number if we start with a 2-exposed regular number. So we never want to increment a 2-exposed number.

The claim is that you can convert a 2-exposed number into a 0-exposed equivalent in `O(1)` time if you know where the rightmost 2 is. Let the number be written as `xy2z`, where `z` is the sequence of digits to the right of the rightmost 2, `y` is the digit immediate to the left of it, and `x` is the sequence to the left of `y`. Due to the regularity constraint, note that `z` must be all 1s if it is not null, and `y` only has two possibilities:

  • `x02z` = `x10z`
    `x` must be 2-exposed, so `x10z` is regular.
  • `x12z` = `x20z`
    `x` must be 0-exposed, so `x20z` is regular.

And both of these are 0-exposed and we know adding 1 to them takes `O(1)` time.

The remaining issue is how we know where the rightmost 2 is. This is easy. We maintain a stack of the locations of the 2s, with the rightmost on the top of the stack. Verify that the above two fixing operations both operate at the top of the stack.

Now do you understand how to add 1 in `O(1)` time?

Indeed, if the number is 2-exposed, fix it to become 0-exposed first. And we know that adding 1 to a 0-exposed number is easy.

But why am I telling you about redundant number systems? That would be the subject of Part 2.