## data structures – If a key in a red-black tree has exactly one child (which isn’t null) then he is always red

I have the following claim:

If a key in a red-black tree has exactly one child (which isn’t null) then he is always red. prove or disprove it.

My attempt:

$$Disproof.$$

we shall represent a counter-example:

This tree satisfies the conditions of being a red-black tree,

since:

1. the root is black.
2. all leaves are black.
3. there isn’t a red key.
4. in each path there is the same amount of black keys, in particular, we have three black keys in such paths.

However, we have two keys in level-1, which have one child and he is black.

$$qquad qquad qquad qquad qquad qquad qquad qquad qquad qquad qquad qquad qquad qquad blacksquare$$

Is this disproof right? because perhaps I missed something, and this counter-example doesn’t represent a counter-example. Thanks!

## algorithms – Insertions in Red–Black tree with size property of each node

Assume that I have a Red-Black tree. Furthermore, let each node, $$x$$, in the Red-Black tree have the field $$size$$ that shows the number of nodes in the sub-tree rooted at $$x$$. How would I then update the insertion algorithm as shown in pages 315-316 in CLRS (the excerpt can be seen here) to properly maintain this $$size$$ field for each node $$x$$?

I think that I already know how to update the LEFT-ROTATE and RIGHT-ROTATE functions such that $$x.size$$ property is maintained for every node $$x$$ in the Red-Black tree after calling the rotate functions. But what else would I need to do to maintain the $$x.size$$ property for every node $$x$$?

## algorithms – 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 a continuous line.

What I understand about Red Black Trees:

1. Every node is either red or black.

2. The root and leaves are black.

3. If a node is red, then its parent is black.

4. For every leaf, the path has the same number of black nodes (the tree is balanced).

My profs solution:

Solution from this website

I’m very confused as to how to solve this, my prof’s PPTs say that all the red connections are to the left, I’ve found places that say that all reds are to the right, others where it’s irrelevant.
Can someone explain how to solve this?

## 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 $$2lg(n+1)$$, they prove that any subtree rooted at any node $$x$$ in a red-black tree has at least $$2^{bh(x)} -1$$ internal nodes. However I couldn’t wrap my head around this proof.

They do an induction where this holds for the base case when $$x$$ is a leaf by $$2^{bh(x)}-1 = 2^0 – 1 = 0$$. However, when they do the induction, they say that a child of node $$x$$ has at least $$2^{bh(x)-1}$$ internal nodes (by the way isn’t the correct way to put is to start with subtree rooted at a child of node $$x$$?). This part confuses me a little bit, is it too trivial to say that it has $$2^{bh(x)-1}$$ nodes given that $$bh(x)$$ is the black-height (the number of black nodes on any simple path from a node not including itself), or is this related to the rules of the red-black tree which are:

1. Every node is either red or black.
2. The root is black.
3. Every leaf (NIL) is black.
4. If a node is red, then both its children are black.
5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

## algorithms – 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 statistics can be done in $$O(lg(n))$$ time in the worst case. Now in case of an array representing the dynamic set of elements finding the $$i$$ th order statistic can be achieved in the $$O(n)$$ time in the worst case.( where $$n$$ is the number of elements).

Now I felt like finding a tight upper bound for forming an $$n$$ element Red-Black Tree so that I could comment about which alternative is better : “maintain the set elements in an array and perform query in $$O(n)$$ time” or “maintaining the elements in a Red-Black Tree (formation of which takes $$O(f(n))$$ time say) and then perform query in $$O(lg(n))$$ time”.

So a very rough analysis is as follows, inserting an element into an $$n$$ element Red-Black Tree takes $$O(lg(n))$$ time and there are $$n$$ elements to insert , so it takes $$O(nlg(n))$$ time. Now this analysis is quite loose as when there are only few elements in the Red-Black tree the height is quite less and so is the time to insert in the tree.

I tried to attempt a detailed analysis as follows (but failed however):

Let while trying to insert the $$j=i+1$$ th element the height of the tree is atmost $$2.lg(i+1)+1$$. For an appropriate $$c$$, the total running time,

$$T(n)leq sum_{j=1}^{n}c.(2.lg(i+1)+1)$$

$$=c.sum_{i=0}^{n-1}(2.lg(i+1)+1)$$

$$=c.left(sum_{i=0}^{n-1}2.lg(i+1)+sum_{i=0}^{n-1}1right)$$

$$=2csum_{i=0}^{n-1}lg(i+1)+cntag1$$

Now

$$sum_{i=0}^{n-1}lg(i+1)=lg(1)+lg(2)+lg(3)+…+lg(n)=lg(1.2.3….n)tag2$$

Now $$prod_{k=1}^{n}kleq n^n, text{which is a very loose upper bound}tag 3$$

Using $$(3)$$ in $$(2)$$ and substituting the result in $$(1)$$ we have $$T(n)=O(nlg(n))$$ which is the same as the rough analysis…

Can I do anything better than $$(3)$$?

All the nodes referred to are the internal nodes in the Red-Black Tree.

## What’s the role of nil leaves in red-black trees?

In red-black trees, there is this idea that you should have nil (empty) leafs that are always marked as black.
I don’t quite understand their role, why have them in the first place? Is it not just an extra requirement on the data-structure?

## Red-black tree height proof

I know that the height of a red and black tree is at most 2 lg (n + 1). But what is the mathematical proof of this? I searched various websites, but couldn't find any good evidence. I already know the properties of a red and black tree.

## Does the internal structure of a red-black tree depend on the insertion order?

Does the internal structure of a red-black tree (which nodes are red or black, the arrangement of the branches, the position of the individual values ​​…) depend on the order in which the elements were inserted? Or does it just depend on them to adjust of inserted elements without considering the order? Do different advertising orders always lead to the same tree?

In the event that the order really does matter, there is an algorithm that returns a sequence of elements on a red and black tree, so pasting in the same order results in a tree that is structurally identical to the one we used started?

## Time Complexity – In the case of right rotation for red-black trees, there is a less efficient way to re-color them. Why is not it O (log (n))?

So the first time I tried to color that insertion point out of memory, it was repainted on the right side. Of course, the left side's staining is more efficient as the loop ends up here. If it does, we will check in the right case whether the grandparent of one If the root is (color is black) and the loop continues from this node otherwise, I've read that it does not make the stain any longer O (log (n)), why is that? In the worst case, it still seems to be O (log (2n)), even though the number of revolutions performed is no longer O (1).

## Data Structures – Is the tree displayed as a valid red-black tree?

I have made a red and black tree and think that it is not valid. Could someone please check?

As far as I know, in the red-black tree we also look at the leaf nodes at the NULLs of the visible leaf nodes, and those NULLs are considered black.
So, according to this logic, when we look at the order root->left->left->left as black, then no. from black nodes to this NULL node are 2.
Even if we look at the knot root->right->right->right->right->right as black, then there are no black nodes to this NULL node 3.
So, according to the argument above, it should not be a valid red-black tree.
Am I right or do I miss an important concept?