Questions tagged [red-black-trees]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
38 views

Can a Red Black Tree have a black node with a black descendant? Is this image wrong?

How the story begins? I was learning about Red Black Trees on my own. When one opens the Wikipedia article, it can be read: (Conclusion) If a node N has exactly one child, it must be a red child, ...
tac's user avatar
  • 101
5 votes
0 answers
75 views

Completeness of red-black tree operations

Red-black trees are defined to have the following invariants: The nodes are in sorted order (it is a binary search tree). The root is black, and leaves are black. Every red node has black children. ...
Mario Carneiro's user avatar
1 vote
1 answer
44 views

Merge K BST of N elements in total into a single RBT in O(N log K) time

I have the following question to solve; Given $K$ BST consisting of $N$ total elements, show how you can create a Red Black Tree in $O(N\log K)$ time. I had the following idea but it falls on the ...
Alon .G.'s user avatar
0 votes
1 answer
156 views

Prove that the subtree rooted at any node $x$ in a red black tree contains at least $2^{bh(x)} - 1$ internal nodes

To prove this, Introduction to Algorithms by Cormen et al., makes the assumption that the node has two children. For the inductive step, consider a node $x$ that has positive height and is an ...
ihsingh2's user avatar
1 vote
0 answers
51 views

Merge two red black trees with the same black height

Consider two red-black trees T1 and T2, each with black-height h, with all values in T1 less than all values in T2. How to merge these two trees to obtain a red-black tree in O(h). The root is always ...
nicku's user avatar
  • 143
2 votes
0 answers
46 views

How to delete node from RB-tree

I need to implement my own red-black tree and I am stuck with deletion. I have found this book (Introduction to Algorithms) (p.222) and in the following code I can't understand this marked line. ...
Euler-Maskerony's user avatar
0 votes
0 answers
69 views

Red-Black Tree - Top-down deletion

I learned the red-black tree top-down deletion from RB-tree tree: top-down deletion start from page 56 However, I'm quite confused about below page. Why do the root need to change to red. I thought ...
samli50801's user avatar
2 votes
0 answers
79 views

Problem about variation of red-black trees

I got an exercise about a variation of RB trees but I am struggling to see how to solve it, therefore I'll be happy to hear your opinion about it. The exercise is: Let us define a binary search tree ...
Yarin's user avatar
  • 229
1 vote
1 answer
287 views

A red-black full tree where every black node has at most 1 red child has at most (n-1)/4 red nodes

Let us call a red-black tree strict when every black node has at most one red child. Show that a strict red-black full tree has at most $(n − 1)/4$ red nodes; a binary tree is full when every node has ...
SVMteamsTool's user avatar
0 votes
0 answers
51 views

Red Black Tree: number of internal nodes vs leaf nodes

Given a generic Red Black Tree with n nodes is correct to say that the number of internal nodes is ⌊n/2⌋ and the number of leaf nodes is ⌊n/2⌋ + 1 ?
Bender's user avatar
  • 367
0 votes
1 answer
133 views

Depth-first search (DFS) time complexity for a Red-Black Tree

If we indicate n as the number of nodes of a Red-Black Tree, which is the time complexity of a DFS algorithm that analyzes only the internal nodes of the Tree? I think that the complexity is O(n), but ...
Bender's user avatar
  • 367
1 vote
1 answer
82 views

Least-balanced possible red-black tree of n distinct nodes

Let's say we have a red-black tree of $n$ total nodes where all keys are distinct. The subtree rooted at the root node's left child has $n_L$ nodes, and similarly the subtree rooted at the root node'...
Intrastellar Explorer's user avatar
-1 votes
1 answer
70 views

Are AVL&RB Trees without additional storage for balance information in each node feasible?

One advantage claimed for scapegoat trees over other balanced trees like AVL or red-black(RB trees - just mentioning AVL henceforth) is not needing to store additional balance information. But can't ...
greybeard's user avatar
  • 977
2 votes
0 answers
140 views

How is red-black tree insertion more effective than avl tree insertion

I'm having trouble understanding why RB tree insertion is called more effective in all sources. It's said that AVL trees require "more rotations" than RB trees, but from what I've learned I ...
Sviatozar Petrenko's user avatar
0 votes
1 answer
114 views

updating n elements in $O(\lg{n})$ time

I need to devise a data structure $S$ with the following functions: BUILD($S$) - build the data structure from a series of $n$ elements in time $O(n \lg{n})$ INSERT($S$, $k$) - insert a new element ...
CforLinux 's user avatar
0 votes
0 answers
177 views

Create a data structure with D-SUCCESSOR running in $O(1)$

Given an integer $d$, I need to devise a data structure $S$ with the following actions: BUILD(S): build the data structure $S$ from $n$ elements in $\Theta(n\lg{n})$ INSERT(S, k): insert a new ...
CforLinux 's user avatar
0 votes
1 answer
74 views

Finding 2 nodes which sum equals twice their common ancestor in RBT in $\Theta(n\lg n)$

I have a red black tree, $T$, and I need to write an algorithm to find 2 nodes $x$ and $y$ so that $key[x] + key[y] = 2 \cdot key[p(x, y)]$, where $p(x, y)$ is the lowest common ancestor of $x$ and $y$...
CforLinux 's user avatar
1 vote
1 answer
65 views

If a key in a red-black tree has exactly one child (which isn't null) then it is always red

I have the following claim: Prove or disprove: If a key in a red-black tree has exactly one child (which isn't null) then it is always red. My attempt: Disproof. We will exhibit a counterexample: ...
Chopin's user avatar
  • 123
2 votes
2 answers
78 views

Self-balancing BST supporting in-order-sequential multi-insertions / multi-deletions in logn+klogk time?

Given a self-balancing binary search tree of size $n$, I want to perform the following operations: InsertInOrderSequentialBatch an ordered sequence of $k$ values (...
Warty's user avatar
  • 141
0 votes
1 answer
223 views

Cormen RB-DELETE_FIXUP(T,x) when x has no siblings

I am working on chapter 13 of CLRS. I am studying how to fix the colors on a red-black tree after deleting a black node. Suppose we want to delete the node 2. This is a black node. He will be ...
carlos palma's user avatar
1 vote
1 answer
197 views

Cormen problem 13-1 part d

I am going through problem 13-1 in CLRS 3rd edition. I came up with the following algorithm as a solution: ...
carlos palma's user avatar
0 votes
0 answers
60 views

Having trouble understanding Red-Black trees

Exam question: Draw the Red Black Tree that results from inserting the following values in the given order: [10, 20, 30, 4, 5, 50] Draw the red connections with a dotted line and the black ones with ...
Segmentation fault's user avatar
1 vote
1 answer
1k views

Every AVL tree can be colored to be a red-black tree

I want to prove any AVL tree can be turnt into a red-black tree by coloring nodes appropriately. Let $h$ be the height of a subtree of an AVL tree. It is given that such a coloring is constrained by ...
PsychoKitten's user avatar
2 votes
1 answer
536 views

Prove that any subtree in a red-black tree has at least $2^{bh(x)} -1$ internal nodes

I'm reading the book Introduction to Algorithms. In the book, in the initial step of proving that a red-black tree with $n$ internal nodes has height at most $2\lg(n+1)$, they prove that any subtree ...
iRestMyCaseYourHonor's user avatar
0 votes
1 answer
37 views

Are colored graphs and red-black trees related?

I've come across the concepts of colored graphs (register allocation) and red-black trees. They both seem to have this notion of "coloring", but I've never seen them being connected ...
master_of_privates's user avatar
0 votes
1 answer
293 views

Tight upper bound for forming an $n$ element Red-Black Tree from scratch

I learnt that in a order-statistic tree (augmented Red-Black Tree, in which each node $x$ contains an extra field denoting the number of nodes in the sub-tree rooted at $x$) finding the $i$ th order ...
Abhishek Ghosh's user avatar
0 votes
1 answer
358 views

Prove that a red-black tree with $n$ internal nodes has height at most $2\lg(n+1)$

I cannot understand the first paragraph of the proof, which comes from the known book Introduction to Algorithms, third-edition, and I consider it has some errors, could anyone help me check about it? ...
Ning's user avatar
  • 249
0 votes
0 answers
65 views

Red-Black Tree Height Proof

I know that the height of a red-black tree is at most 2 lg(n + 1). However, what is the mathematical proof of this? I searched various sites, however I couldn't find a good proof. I already know the ...
nishantc1527's user avatar
1 vote
0 answers
16 views

Confusion with "every path from a given node to any of the leaves goes through the same number of black nodes" property of RB trees

One of the properties of Red Black trees is: "every path from a given node/vertex to any of the leaves goes through the same number of black nodes" Two related questions about this property: 1) is ...
James Ronald's user avatar
1 vote
0 answers
464 views

Is the internal structure of a red-black-tree dependent on the insertion order?

Is the internal structure of a red-black tree (which nodes are red or black, the disposition of the branches, the location of each value...) dependent on the order in which the elements were inserted? ...
Daniel Díaz Carrete's user avatar
1 vote
0 answers
433 views

Red-Black tree with index

I want to create a Red-Black Tree, with 2 values, (index, value) and I want to insert into the RB_tree based on the index. So if I have the function: $\text{insert}(root, value, index)$ it will ...
C. Cristi's user avatar
  • 187
2 votes
1 answer
56 views

What would happen if we added this rule to red-black trees?

So, I know that a normal r-b tree has a height of O(logn). What would happen is we let a red node have a red child if its parent is black? Would the height still be O(logn)? Would you have to have a ...
Curious_CS_student's user avatar
0 votes
1 answer
539 views

Is the tree shown a valid red-black tree?

I have made a red-black tree and I think that it is not valid. Could someone please verify? ...
Swapnil Agarwal's user avatar
0 votes
0 answers
46 views

RB trees from any balanced BST?

Given any perfectly balanced binary search tree, is it always possible to assign a coloring to the nodes so that it becomes a Red-Black tree? If so, how do you prove this, and if false, what would be ...
Anon's user avatar
  • 103
2 votes
0 answers
174 views

Red-black tree trinode restructuring after insertion and deletion

When performing an insertion/deletion on a red-black tree, how can be argued or proved that it requires at most one/two trinode restructuring(s) respectively? My thoughts so far were: after inserting ...
PapaCode's user avatar
2 votes
1 answer
266 views

Introduction To Algorithms 3rd Edition MIT Press: Red Black Tree insertion error in pseudo-code?

I'm implementing the algorithm on page 316 of the book Introduction to Algorithms. When I look at the pseudo-code, I feel that there is something wrong between line 10 to 14. I feel it's missing a ...
Melvin Roest's user avatar
0 votes
0 answers
47 views

Red Black Tree Property

Although it may sound trivial... I was going trough the definitions for Red Black Tree in the book "Introduction to Algorithms" and I still cannot understand, why this is not a RBT? ...
NiRvanA's user avatar
  • 159
12 votes
1 answer
3k views

Why use heap over red-black tree?

Heap supports insert operation in $O(\log n)$ time. And while heap supports remove min/max in $O(\log n)$ time, to remove any element (non min/max) heap takes $O(n)$ time. However, red-black tree ...
Wonjoo Lee's user avatar
0 votes
1 answer
40 views

Augmenting a tree such that we preserve the insertion operation optimal runtime

Suppose we are given a red-black tree with $n$ vertices with distinct keys and we want to store, as addition information in each vertex $v$, the biggest key out of the keys that are smaller than $v$ (...
user avatar
2 votes
1 answer
416 views

Proof that a subtree of a red-black tree has no more than $\frac{3n}{4}$ nodes

I have a red-black tree with $n$ nodes, rooted at $x$. How can I prove or disprove that the number of nodes in any subtree of $x$ (including the root of the subtree) will never be greater than $\frac{...
rtheunissen's user avatar
3 votes
1 answer
454 views

I don't understand the case 4 of red-black tree deletion

I don't know why case 4 will resolve the issue of the double black of $x$ described in Introduction to algorithm p.329. I know case 1 is transformed into one of {2,3,4} case, and case 2 re-point $x$ ...
Ning's user avatar
  • 249
1 vote
1 answer
2k views

Red-Black Tree deletion algorithm (CLRS, 3rd edition) : Deleting the root

I have been following the third edition of Introduction to Algorithms (by Cormen, Rivest, et al.), and have been studying the deletion algorithm for red-black trees. However, I am confounded at the ...
nerdier.js's user avatar