Questions tagged [red-black-trees]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
39 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
30 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
21 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
52 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
21 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
55 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
24 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
37 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
156 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
37 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
138 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
88 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
175 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
212 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
49 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
131 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
131 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
143 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? ...
8
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
252 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 ...