All Questions
Tagged with binary-search-trees red-black-trees
12 questions
5
votes
0
answers
83
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.
...
- 541
1
vote
1
answer
110
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 ...
- 13
0
votes
0
answers
62
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 ?
- 367
0
votes
1
answer
178
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 ...
- 367
1
vote
1
answer
173
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'...
0
votes
1
answer
77
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$...
- 261
1
vote
1
answer
69
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:
...
- 123
1
vote
1
answer
357
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:
...
- 149
0
votes
1
answer
567
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?
...
0
votes
0
answers
49
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 ...
- 103
0
votes
1
answer
42
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$ (...
user101904
2
votes
1
answer
423
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{...
- 203