Share Your Experience: Take the 2024 Developer Survey

# Tag Info

### Why are Red-Black trees so popular?

I've been researching this topic recently as well, so here are my findings, but keep in mind that I am not an expert in data structures! There are some cases where you can't use B-trees at all. One ...
• 161
Accepted

• 1,064

### Compute height of AVL tree as efficiently as possible

No. There's a $\Omega(\lg n)$ lower bound. You can't do better than $O(\lg n)$ time. In fact, any algorithm has to visit at least $H-1$ nodes, where $H$ is the height of the tree. Let $T_1$ be a ...
• 161k
Accepted

### Question on the properties of red black trees

The left subtree cannot be a chain of $n$ black nodes, since it breaks the red-black tree properties. In the worst case scenario, the left subtree is a minimal black binary tree of height $\log n$, ...
• 156
Accepted

### Insertions in Red-Black Trees

Yes, a given set can be represented by multiple red-black trees, and this works incrementally, at least some of the time. That is, there exists more than one valid red-black tree insertion algorithm, ...
• 719
Accepted

### Should one limit the maximum level of a skip list node?

Contrary to what Pugh says in that paper, I don't believe the "fix the dice" strategy has any impact on the stochastic analysis of skip list performance. The strategy demotes (reduces the level) of a ...
• 12k
If you want to show that the height is $h=\mathcal O(\log(n))$ then I would suggest the following: Define $n_h$ as the minimum vertices in tree with height $h$ Then to get the minimum vertices for ...