# Tag Info

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

To quote from the answer to “Traversals from the root in AVL trees and Red Black Trees” question For some kinds of binary search trees, including red-black trees but not AVL trees, the "fixes" to ...

### 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 ...
Accepted

### A median of an AVL. How to take advantage of the AVL?

If you modify the AVL tree by storing the size of the subtree at each node rather than just its height, then you can find the median in time $O(\log n)$ using the fact that the tree is balanced. To ...

Accepted

### Balance factor changes after local rotations in AVL tree

EDIT: @Maxym's answer is correct after all and is actually equivalent. I had simply misinterpreted the notation. Leaving this answer anyway as the cited link provides a useful explanation. While @...

### 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 ...
Accepted

### AVL tree such that each insert causes rotation (single or double)

Short answer: it depends. The answer depends on what is the set of the possible elements of the AVL tree. Natural numbers, no duplicates allowed. Yes, there is an AVL tree requiring a rotation on ...
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$, ...