Skip to main content
Share Your Experience: Take the 2024 Developer Survey
16 votes

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 ...
matklad's user avatar
  • 161
12 votes
Accepted

Why is b-tree search O(log n)?

You have introduced $n$ and $m$ as the order of B-tree, I will stick to $m$. Their height will be in the best case $\lceil log_m(N + 1) \rceil$, and the worst case is height $\lceil log_{\frac{m}{2}}(...
Evil's user avatar
  • 9,465
6 votes

Why are Red-Black trees so popular?

Well, this is not an authoritative answer, but whenever I have to code a balanced binary search tree, it's a red-black tree. There are a few reasons for this: 1) Average insertion cost is constant ...
Matt Timmermans's user avatar
6 votes

rope data structure - undo operation

The approach is to build a fully persistent version of the rope data structure. This then lets you keep a pointer to each version of the data structure: you have a pointer to version 1 ("hello world")...
D.W.'s user avatar
  • 161k
6 votes
Accepted

Is every AVL tree a BST or just BT?

Yes every AVL tree is a BST also note that every binary search tree itself is a binary tree (binary tree is basically a tree that each node has at most two child) so therefore every AVL is a binary ...
John P's user avatar
  • 750
5 votes

Are degree and order the same thing when referring to a B-Tree?

I have seen three ways to characterize B-tree so far: With degree of the B-tree $t$ (either minimum, as in CLRS Algorithms book, or maximum as in B-tree Visualizer). The simplest B-tree occurs ...
Mr. Tao's user avatar
  • 163
5 votes
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 @...
Gil Hamilton's user avatar
5 votes
Accepted

Why is this not a valid Red-Black tree?

If you go to the empty leaf from the root in the pattern [Right, Left], you get to an empty leaf encountering 1 black node. If you go [Right, Right, Left] or [Right, Right, Right], you get to an empty ...
Cricket's user avatar
  • 66
5 votes
Accepted

How many rotations after AVL insertion and deletion

The obvious resource, Wikipedia, I did not find very helpful. When inserting an element at most one (single or double) rotation is needed, at the lowest point where the tree is out of balance. After ...
Hendrik Jan's user avatar
  • 30.7k
4 votes
Accepted

Zero-based array implementation with logarithmic insertion time

All tree data structures that use pointers can be re-worked to use array indices as well, and that is probably your best bet. If you come across a design that uses NULL pointers, use the array index $-...
Martin Kochanski's user avatar
4 votes

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 ...
D.W.'s user avatar
  • 161k
4 votes
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$, ...
alonkol's user avatar
  • 156
4 votes
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, ...
Jonas Kölker's user avatar
4 votes
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 ...
rici's user avatar
  • 12k
4 votes

BVL Balanced Tree

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 ...
Omer Nizri's user avatar
4 votes

how does rotation works in AVL trees and what is a good way to understand it?

One needs three subtrees to describe rotation, as the operation reconnects the three subtrees of a pair of nodes, one the child of the other. The operation can be seen as a associative property: $...
Hendrik Jan's user avatar
  • 30.7k
4 votes
Accepted

Difficulty in updating the balance factor of nodes in AVL tree

The reason that the number of possible values for the balance factors at $y$ and $z$ is limited is not only the fact that the tree has been AVL before insertion, but also the precise location where ...
Hendrik Jan's user avatar
  • 30.7k
4 votes
Accepted

Finding an interval in a binary search tree that contains a point

You can't find a better algorithm for your problem using comparisons, because a lower bound of $\Omega(\log n)$ can be proven for these setings (proof below). What you can do is some minor ...
lox's user avatar
  • 1,669
4 votes
Accepted

Height of epsilon-balanced binary search tree

Take any path in the tree, starting at the root, and consider the number of nodes at the subtree rooted at each vertex along the path. For the root, it's $n$ nodes. For the second vertex, it's at most ...
Yuval Filmus's user avatar
3 votes

Average depth of a Binary Search Tree and AVL Tree

Your question refers to average depth of the nodes in a BST, but it's easiest answer this by thinking about the overall height of the tree first. In the worst case, the depth of the tree can be $n$, ...
Edward Ned Harvey's user avatar
3 votes
Accepted

Why do we need double-rotations to rebalance AVL trees?

I think you are right for this example. But the title of your question is misleading. Let me explain. After insertion the tree can be rebalanced with one (single or double) rotation at the lowest ...
Hendrik Jan's user avatar
  • 30.7k
3 votes

Imagine a red-black tree. Is there always a sequence of insertions and deletions that creates it?

The insert and delete operations in a red-black tree include the balancing needed to maintain the red-black properties. The problem with non(left- or right-) leaning red black trees is that there ...
Johan's user avatar
  • 1,080
3 votes

weight balanced binary tree vs height balanced binary tree

The way to answer your question is to find the peer-reviewed papers that first described the trees (or that later chose to reference them) and read their explanations of why the authors felt the need ...
jbapple's user avatar
  • 3,380
3 votes

Red-Black tree height from CLRS

step 1 : At first let me say that , property 4 which states that children of a red node , should be black , comes from the definition of red-black tree , because 2 (or more) red nodes can't come after ...
Farehe.s's user avatar
3 votes
Accepted

For AVL trees, how do we know if a RL or a LR rotation is needed?

In this case the tree is right-left unbalanced. That's because when you insert $B$ it causes the root node to become unbalanced. You can tell its right-left unbalanced from the path that goes from the ...
cpx's user avatar
  • 252
3 votes
Accepted

How to retrieve reset bit in constant time in a bit array

Access into a bit array is constant time. In particular, if you have an array that is stored contiguously in memory, indexing into the array takes constant time: reading $A[i]$ takes constant time, ...
D.W.'s user avatar
  • 161k
3 votes
Accepted

How many node does the final B-tree have?

Every node contains between $\lceil(m/2)\rceil-1$ and $m-1$ keys (where m is the degree), so we can say that every node has between $\lceil(m/2)\rceil$ and $m$ children. If we imagine to construct a ...
Lorenzo Tagliabue's user avatar
3 votes
Accepted

Deletion from 2,3,4 tree

The problem you're encountering is that a deletion is cascading and triggering another deletion. In particular, you're deleting from a node with only one key. Rather than working from the bottom up, ...
roctothorpe's user avatar
  • 1,158
3 votes
Accepted

AVL tree worst case height proof

We want to show that the number of nodes $n$ in a height-balanced binary tree with height $h$ grows exponentially with $h$ and at least as fast as the Fibonacci sequence. Let $N_h$ denote the ...
Ashwin Ganesan's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible