Questions tagged [red-black-trees]
The red-black-trees tag has no usage guidance.
29
questions
0
votes
1answer
55 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
48 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
34 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
25 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
50 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
55 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
22 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
68 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
26 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
197 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
59 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
150 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
101 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
26 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
13 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
192 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
235 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
50 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
174 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
35 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
132 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
150 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
38 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
37 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
259 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 ...
