Questions tagged [red-black-trees]
The red-black-trees tag has no usage guidance.
32
questions
0
votes
0answers
16 views
What is the maximum height of a red-black tree containing 13 keys?
If I go by the upper bound of 2 * log (n+1), it comes out to be 7. But I am not sure if that is achievable or not. So how can one determine the max possible in this case?
0
votes
1answer
22 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 ...
2
votes
0answers
41 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 ...
0
votes
1answer
60 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 ...
0
votes
0answers
56 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 ...
0
votes
1answer
39 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$...
0
votes
0answers
33 views
Counting the number of comparisons in red black tree
I have an array with $N$ elements and I run an algorithm that find how many distinct elements are in the array by using a red black tree as follows:
for each element
if element not in tree
insert ...
1
vote
1answer
55 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:
...
2
votes
2answers
59 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 (...
0
votes
1answer
28 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 ...
1
vote
1answer
73 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:
...
0
votes
0answers
31 views
Order-statistic tree: Worst-case running time of a sequence of $n$ insertions/deletions and $m$ calls to SELECT operation
Assume I have an order-statistic tree, $T$, which is a red-black tree where every node $x$ also has the attribute $x.size$. How can I compute the worst-case running time of an arbitrary sequence of $n$...
0
votes
0answers
38 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 ...
1
vote
1answer
269 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 ...
2
votes
1answer
107 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 ...
0
votes
1answer
33 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 ...
0
votes
1answer
200 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 ...
0
votes
1answer
149 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?
...
0
votes
0answers
30 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 ...
1
vote
0answers
14 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 ...
1
vote
0answers
239 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? ...
1
vote
0answers
289 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
51 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
1answer
234 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
36 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
138 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 ...
2
votes
1answer
172 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
39 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?
...
9
votes
1answer
2k 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
39 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
322 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{...
1
vote
1answer
1k 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 ...
