## 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}1\right]$$

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

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}k\leq 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.

## 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 properties of a red-black tree.

## 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 totally different insertion scheme to maintain the height?

## In the right-rotation case for red-black trees, there is a less efficient way to recolor it, why is it not O(log(n)) anymore?

So the first time I tried to recolor this insertion case from memory, I ended up with the right-hand side recoloring; of course the left recoloring is more efficient as the loop ends at this point. If however, we check in the right case for whether the grandparent of a is the root (color it black) and otherwise continue the loop from that node, I read that it makes the recoloring not O(log(n)) anymore, why is that? It still seems to me to be O(log(2n)) at worst, even if the number of rotations performed is not O(1) anymore.

## 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 and these NULL nodes are considered to be black.
So, by this logic, if we consider the order root->left->left->left as black, then no. of black nodes to that NULL node are 2.
Also, if we consider the node root->right->right->right->right->right as black, then no of black nodes to that NULL node are 3.
So, according to the above argument, it should not be a valid red-black tree. Am I right or am I missing some important concept?

## 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 a node and two consecutive red nodes exist along a path from root to a leaf a restructuring is done followed by recoloring, resulting in a red-black tree. Does this mean that after inserting a node there can only exist at most one double red problem in the tree which requires one restructuring to fix it?

## Proofs for red-black tree insertion and deletion

I need to proof that the insertion into a red-black tree takes up to O(logn) recolorings and maximum 1 trinode reconstructions.

Additionally I need to show that deletion in a red black tree takes up to O(logn) recolorings and up to two reconstructions.

Insertion

It seems logic that for the insertion and deletion takes up to log(n) recoloring because the tree has always a height of log(n). And also 1 reconstruction seem plausible, becuase the tree is already balanced before we insert a new element. However I’m am not sure how to show that mathematically and proof the 2 theorems. Can you help me with a sketch of the proofs?

## Why use heap over red-black tree?

Heap supports insert operation in O(logn) time. And while heap supports remove min/max in O(logn) time, to remove any element (non min/max) heap takes O(n) time.

However, red-black tree supports insert/remove both in O(logn) time. We can just remove the first/last element in a red-black tree to remove min/max in O(logn) time.

I do understand that heaps are used specifically to remove the min/max, but it seems like red-black trees can do what heaps can do but just faster/equal.

Is there any distinctive advantage to using heaps over red-black trees?

Thanks!

## How to re-color a red-black tree with a specific property

Let us consider a red-black tree in which for every path from the root to a leaf of minimal depth, there is exactly one red-colored vertex in it. How should we re-color the tree so that, after the re-coloring, all those paths described above contain only black-colored vertices?

I am thinking of just coloring the red-colored vertices on the respective paths black. However, I don’t know how to prove that the resulting tree is still a red-black tree that respects all the properties.

Also, I don’t know what algorithm would determine those red vertices by traversing the tree.

## 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{3n}{4}$$?