Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Intuitively, "balanced trees" should be trees where left and right sub-trees at each node must have "approximately the same" number of nodes.

Of course, when we talk about red-black trees*(see definition at the end) being balanced, we actually mean that they are height balanced and in that sense, they are balanced.

Suppose we try to formalize the above intuition as follows:

Definition: A Binary Tree is called $\mu$-balanced, with $0 \le \mu \leq \frac{1}{2}$, if for every node $N$, the inequality

$$ \mu \le \frac{|N_L| + 1}{|N| + 1} \le 1 - \mu$$

holds and for every $\mu' \gt \mu$, there is some node for which the above statement fails. $|N_L|$ is the number of nodes in the left sub-tree of $N$ and $|N|$ is the number of nodes under the tree with $N$ as root (including the root).

I believe, these are called weight-balanced trees in some of the literature on this topic.

One can show that if a binary tree with $n$ nodes is $\mu$-balanced (for a constant $\mu \gt 0$), then the height of the tree is $\mathcal{O}(\log n)$, thus maintaining the nice search properties.

So the question is:

Is there some $\mu \gt 0$ such that every big enough red-black tree is $\mu$-balanced?


The definition of Red-Black trees we use (from Introduction to Algorithms by Cormen et al):

A binary search tree, where each node is coloured either red or black and

  • The root is black
  • All NULL nodes are black
  • If a node is red, then both its children are black.
  • For each node, all paths from that node to descendant NULL nodes have the same number of black nodes.

Note: we don't count the NULL nodes in the definition of $\mu$-balanced above. (Though I believe it does not matter if we do).

share|improve this question
    
There seem to be multiple (equivalent?) definitions for red-black trees around. Can you please fix one? –  Raphael Mar 14 '12 at 8:49
1  
@Raphael: Good point. I have edited. Thanks! –  Aryabhata Mar 14 '12 at 9:01
    
@Aryabhata: what's with the uniqueness ($\mu'>\mu$) in your edit? I'm fine with the fact that $\frac13$-balanced implies $\frac14$-balanced. I don't think you should have to find the exact $\mu$ to prove height is $O(\log n)$. Am I missing something? –  jmad Mar 14 '12 at 12:34
    
Furthermore, you require a negative statement to provide a counterexample chain with one tree for every $n \in \mathbb{N}$. Any infinite chain that is non-decreasing in node size would be sufficient, wouldn't it? –  Raphael Mar 14 '12 at 14:03
1  
An earlier version of this question claimed that the runtime of a recursive algorithm on a red-black tree which does linear amount of work at each step is not necessarily $O(n\log n)$. This claim was incorrect; height-balance implies that the depth of an $n$-node red-black tree is $O(\log n)$. Thus, if you perform $O(n)$ work at each level of the tree, the total work is $O(n \log n)$. –  JeffE Mar 14 '12 at 14:48

2 Answers 2

up vote 19 down vote accepted

Claim: Red-black trees can be arbitrarily un-$\mu$-balanced.

Proof Idea: Fill the right subtree with as many nodes as possible and the left with as few nodes as possible for a given number $k$ of black nodes on every root-leaf path.

Proof: Define a sequence $T_k$ of red-black trees so that $T_k$ has $k$ black nodes on every path from the root to any (virtual) leaf. Define $T_k = B(L_k, R_k)$ with

  • $R_k$ the complete tree of height $2k - 1$ with the first, third, ... level colored red, the others black, and
  • $L_k$ the complete tree of height $k-1$ with all nodes colored black.

Clearly, all $T_k$ are red-black trees.

For example, these are $T_1$, $T_2$ and $T_3$, respectively:


$T_1$
[source]


$T_2$
[source]


$T_3$
[source]


Now let us verify the visual impression of the right side being huge compared to the right. I will not count virtual leaves; they do not impact the result.

The left subtree of $T_k$ is complete and always has height $k-1$ and therefore contains $2^k - 1$ nodes. The right subtree, on the other hand, is complete and has height $2k - 1$ and thusly contains $2^{2k}-1$ nodes. Now the $\mu$-balance value for the root is

$\qquad \displaystyle \frac{2^k}{2^k + 2^{2k}} = \frac{1}{1 + 2^k} \underset{k\to\infty}{\to} 0$

which proves that there is no $\mu > 0$ as requested.

share|improve this answer
    
Nice pictures!! –  JeffE Mar 14 '12 at 15:02
    
+1: Agree with JeffE! –  Aryabhata Mar 14 '12 at 15:10

No. Consider a red-black tree with the following special structure.

  • The left subtree is a complete binary tree with depth $d$, in which every node is black.
  • The right subtree is a complete binary tree with depth $2d$, in which every node at odd depth is red, and every node at even depth is black.

It's straightforward to check that this is a valid red-black tree. But the number of nodes in the right subtree ($2^{2d+1}-1$) is roughly the square of the number of nodes in the left subtree ($2^{d+1}-1$).

share|improve this answer
    
You beating me to it by a minute is what I get for wrestling with graphviz! XD –  Raphael Mar 14 '12 at 15:00
    
+1: Thanks! But the number of nodes is of the from $2^{2d+1} + 2^{d+1} - 1$. Can we perhaps 'pad' these sufficiently to get a tree a given size $n$? (It looks like that should be do-able). –  Aryabhata Mar 14 '12 at 15:03
1  
You already have a counterexample for infinitely many $n$, so why bother?. But I suppose if you wanted to, you could add more red nodes to the left subtree, or take some red nodes out of the right subtree. –  JeffE Mar 14 '12 at 15:05
    
@JeffE: Basically the counterexample chain would then be a 'dense' subset, rather than a 'sparse' subset. Perhaps I will change the formulation of the question. –  Aryabhata Mar 14 '12 at 15:08
    
I am going to accept Raphael's answer because of the figures. Thank you. –  Aryabhata Mar 14 '12 at 15:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.