Questions tagged [red-black-trees]
The red-black-trees tag has no usage guidance.
11
questions
0
votes
0answers
34 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 ...
2
votes
1answer
43 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 ...
0
votes
0answers
16 views
In the right-rotation case for red-black trees, there is a less efficient way to recolor it, why is it not O(log(n)) anymore?
So the first time I tried to recolor this insertion case from memory, I ended up with the right-hand side recoloring; of course the left recoloring is more efficient as the loop ends at this point. If ...
0
votes
1answer
32 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?
As far as I know, in red-black tree we also consider the leaf nodes at the NULLS of the visible leaf nodes ...
0
votes
0answers
20 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 ...
2
votes
0answers
74 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 ...
1
vote
1answer
51 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 ...
0
votes
0answers
33 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?
...
4
votes
1answer
426 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 ...
0
votes
1answer
31 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$ (...
2
votes
1answer
77 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{...
