induction – 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 these cases:

  1. $h$ odd $implies$ black height $=$ $frac{h}{2} + 1$, root node black
  2. $h$ even $implies$ black height $=$ $frac{h+1}{2}$, root node red

After that the root node is colored black.


I’m trying to prove this inductively. Let’s start with the base case $h=1$. Then there is only one node (the root node) and it gets colored black (using case 2) which yields a valid red-black tree.

Now suppose the statement is true for some $h geq 1$. Then for any node $u$ in the AVL tree, the height difference between their children is less than $1$. That is, for an AVL tree of height $h+1$ either both subtrees of the root node have height $h$ or one has height $h-1$.

By the induction hypothesis we know how to color the subtree of height $h$, depending on the parity of $h$. I’m unsure if I should use strong induction instead because it is not given in the hypothesis how to color a subtree of height $h-1$.

If we would know how to color both subtrees, then consider the following cases:

  1. $h+1$ is even
    • one subtree has height $h$, the other height $h-1$
    • both subtrees have height $h$
  2. $h+1$ is odd
    • one subtree has height $h$, the other height $h-1$
    • both subtrees have height $h$

For case 1.1 we would get
$$
begin{align*}
quad & h+1 &text{even} \
implies quad & h &text{odd} \
implies quad & text{black height} = frac{h}{2} + 1 \
implies quad & h-1 &text{even} \
implies quad & text{black height} = frac{(h-1)+1}{2} = frac{h}{2}
end{align*}
$$

So their black heights differ by $1$. How would I take that into consideration?

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 conceptually.

Do they have anything to do with each other?

C++ : Red-Black Tree with std::unique_ptr

This is my C++ implementation of a Red-Black Tree, referring the CLRS book.
Half for fun, half for studying.

  • As implementing child node, I chose std::unique_ptr over std::shared_ptr because std::unique_ptr is cheaper/faster and the nodes are not shared across multiple threads with indeterminate access order. Of course, this decision made the implementation extremely annoying.

  • To test it, I inserted and deleted integers from 1 to 100000 with random order. Comparing with std::set (which uses raw pointers), the benchmark gives:

Inserting 100000 elements:
unique ptr red-black tree : 40 ms
standard red-black tree : 35 ms
Deleting 100000 elements:
unique ptr red-black tree : 49 ms
standard red-black tree : 45 ms

Features could be useful but not been implemented:

  • Iterators.
  • Join operation.

Any feedback will be welcomed, thanks!

#include <cassert>
#include <iostream>
#include <memory>
#include <utility>
#include <numeric>
#include <vector>
#include <random>
#include <set>
#include <chrono>

std::mt19937 gen(std::random_device{}());

enum class Color {
    Red,
    Black
};

template <typename T>
struct Node {
    T key;
    Color color;
    std::unique_ptr<Node<T>> left;
    std::unique_ptr<Node<T>> right;
    Node<T>* parent;

    Node(const T& key) : key {key}, color {Color::Red}, parent {nullptr} {}
};

template <typename T>
struct RBTree {
public:
    std::unique_ptr<Node<T>> root;

private:
    void LeftRotate(std::unique_ptr<Node<T>>&& x) {
        auto y = std::move(x->right);
        x->right = std::move(y->left);
        if (x->right) {
            x->right->parent = x.get();
        }
        y->parent = x->parent;
        auto xp = x->parent;
        if (!xp) {
            auto px = x.release();
            root = std::move(y);
            root->left = std::unique_ptr<Node<T>>(px);
            root->left->parent = root.get();
        } else if (x == xp->left) {
            auto px = x.release();
            xp->left = std::move(y);
            xp->left->left = std::unique_ptr<Node<T>>(px);
            xp->left->left->parent = xp->left.get();
        } else {
            auto px = x.release();
            xp->right = std::move(y);
            xp->right->left = std::unique_ptr<Node<T>>(px);
            xp->right->left->parent = xp->right.get();
        }
    }

    void RightRotate(std::unique_ptr<Node<T>>&& x) {
        auto y = std::move(x->left);
        x->left = std::move(y->right);
        if (x->left) {
            x->left->parent = x.get();
        }
        y->parent = x->parent;
        auto xp = x->parent;
        if (!xp) {
            auto px = x.release();
            root = std::move(y);
            root->right = std::unique_ptr<Node<T>>(px);
            root->right->parent = root.get();
        } else if (x == xp->left) {
            auto px = x.release();
            xp->left = std::move(y);
            xp->left->right = std::unique_ptr<Node<T>>(px);
            xp->left->right->parent = xp->left.get();
        } else {
            auto px = x.release();
            xp->right = std::move(y);
            xp->right->right = std::unique_ptr<Node<T>>(px);
            xp->right->right->parent = xp->right.get();
        }
    }

public:
    Node<T>* Search(const T& key) {
        return Search(root.get(), key);
    }

    void Insert(const T& key) {
        auto z = std::make_unique<Node<T>>(key);
        Insert(std::move(z));
    }

    void Delete(const T& key) {
        auto z = Search(key);
        Delete(z);
    }

private:
    Node<T>* Search(Node<T>* x, const T& key) {
        if (!x || x->key == key) {
            return x;
        }
        if (key < x->key) {
            return Search(x->left.get(), key);
        } else {
            return Search(x->right.get(), key);
        }
    }

    void Insert(std::unique_ptr<Node<T>> z) {
        Node<T>* y = nullptr;
        Node<T>* x = root.get();
        while (x) {
            y = x;
            if (z->key < x->key) {
                x = x->left.get();
            } else {
                x = x->right.get();
            }
        }
        z->parent = y;
        if (!y) {
            root = std::move(z);
            InsertFixup(std::move(root));
        } else if (z->key < y->key) {
            y->left = std::move(z);
            InsertFixup(std::move(y->left));
        } else {
            y->right = std::move(z);
            InsertFixup(std::move(y->right));
        }
    }

    void InsertFixup(std::unique_ptr<Node<T>>&& z) {
        auto zp = z->parent;
        while (zp && zp->color == Color::Red) {
            auto zpp = zp->parent;
            if (zp == zpp->left.get()) {
                auto y = zpp->right.get();
                if (y && y->color == Color::Red) {
                    zp->color = Color::Black;
                    y->color = Color::Black;
                    zpp->color = Color::Red;
                    zp = zpp->parent;
                } else {
                    if (z == zp->right) {
                        LeftRotate(std::move(zpp->left));
                        zp = zpp->left.get();
                    }
                    zp->color = Color::Black;
                    zpp->color = Color::Red;
                    auto zppp = zpp->parent;
                    if (!zppp) {
                        RightRotate(std::move(root));
                    } else if (zpp == zppp->left.get()) {
                        RightRotate(std::move(zppp->left));
                    } else {
                        RightRotate(std::move(zppp->right));
                    }
                }
            } else {
                auto y = zpp->left.get();
                if (y && y->color == Color::Red) {
                    zp->color = Color::Black;
                    y->color = Color::Black;
                    zpp->color = Color::Red;
                    zp = zpp->parent;
                } else {
                    if (z == zp->left) {
                        RightRotate(std::move(zpp->right));
                        zp = zpp->right.get();
                    }
                    zp->color = Color::Black;
                    zpp->color = Color::Red;
                    auto zppp = zpp->parent;
                    if (!zppp) {
                        LeftRotate(std::move(root));
                    } else if (zpp == zppp->left.get()) {
                        LeftRotate(std::move(zppp->left));
                    } else {
                        LeftRotate(std::move(zppp->right));
                    }
                }
            }
        }
        root->color = Color::Black;
    }

    Node<T>* Transplant(Node<T>* u, std::unique_ptr<Node<T>>&& v) {
        if (v) {
            v->parent = u->parent;
        }
        Node<T>* w = nullptr;
        if (!u->parent) {
            w = root.release();
            root = std::move(v);
        } else if (u == u->parent->left.get()) {
            w = u->parent->left.release();
            u->parent->left = std::move(v);
        } else {
            w = u->parent->right.release();
            u->parent->right = std::move(v);
        }
        return w;
    }

    Node<T>* Minimum(Node<T>* x) {
        if (!x) {
            return x;
        }
        while (x->left) {
            x = x->left.get();
        }
        return x;
    }

    void Delete(Node<T>* z) {
        if (!z) {
            return;
        }
        Color orig_color = z->color;
        Node<T>* x = nullptr;
        Node<T>* xp = nullptr;
        if (!z->left) {
            x = z->right.get();
            xp = z->parent;
            auto pz = Transplant(z, std::move(z->right));
            auto upz = std::unique_ptr<Node<T>>(pz);
        } else if (!z->right) {
            x = z->left.get();
            xp = z->parent;
            auto pz = Transplant(z, std::move(z->left));
            auto upz = std::unique_ptr<Node<T>>(pz);
        } else {
            auto y = Minimum(z->right.get());
            orig_color = y->color;
            x = y->right.get();
            xp = y;
            if (y->parent == z) {
                if (x) {
                    x->parent = y;
                }
                auto pz = Transplant(z, std::move(z->right));
                y->left = std::move(pz->left);
                y->left->parent = y;
                y->color = pz->color;
                auto upz = std::unique_ptr<Node<T>>(pz);
            } else {
                xp = y->parent;
                auto py = Transplant(y, std::move(y->right));
                py->right = std::move(z->right);
                py->right->parent = py;
                auto upy = std::unique_ptr<Node<T>>(py);
                auto pz = Transplant(z, std::move(upy));
                py->left = std::move(pz->left);
                py->left->parent = py;
                py->color = pz->color;
                auto upz = std::unique_ptr<Node<T>>(pz);
            }
        }
        if (orig_color == Color::Black) {
            DeleteFixup(x, xp);
        }
    }

    void DeleteFixup(Node<T>* x, Node<T>* xp) {
        while (x != root.get() && (!x || x->color == Color::Black)) {
            if (x == xp->left.get()) {
                Node<T>* w = xp->right.get();
                if (w && w->color == Color::Red) {
                    w->color = Color::Black;
                    xp->color = Color::Red;
                    auto xpp = xp->parent;
                    if (!xpp) {
                        LeftRotate(std::move(root));
                    } else if (xp == xpp->left.get()) {
                        LeftRotate(std::move(xpp->left));
                    } else {
                        LeftRotate(std::move(xpp->right));
                    }
                    w = xp->right.get();
                }
                if (w && (!w->left || w->left->color == Color::Black)
                    && (!w->right || w->right->color == Color::Black)) {
                    w->color = Color::Red;
                    x = xp;
                    xp = xp->parent;
                } else if (w) {
                    if (!w->right || w->right->color == Color::Black) {
                        w->left->color = Color::Black;
                        w->color = Color::Red;
                        auto wp = w->parent;
                        if (!wp) {
                            RightRotate(std::move(root));
                        } else if (w == wp->left.get()) {
                            RightRotate(std::move(wp->left));
                        } else {
                            RightRotate(std::move(wp->right));
                        }
                        w = xp->right.get();
                    }
                    w->color = xp->color;
                    xp->color = Color::Black;
                    w->right->color = Color::Black;
                    auto xpp = xp->parent;
                    if (!xpp) {
                        LeftRotate(std::move(root));
                    } else if (xp == xpp->left.get()) {
                        LeftRotate(std::move(xpp->left));
                    } else {
                        LeftRotate(std::move(xpp->right));
                    }
                    x = root.get();
                } else {
                    x = root.get();
                }
            } else {
                Node<T>* w = xp->left.get();
                if (w && w->color == Color::Red) {
                    w->color = Color::Black;
                    xp->color = Color::Red;
                    auto xpp = xp->parent;
                    if (!xpp) {
                        RightRotate(std::move(root));
                    } else if (xp == xpp->left.get()) {
                        RightRotate(std::move(xpp->left));
                    } else {
                        RightRotate(std::move(xpp->right));
                    }
                    w = xp->left.get();
                }
                if (w && (!w->left || w->left->color == Color::Black)
                    && (!w->right || w->right->color == Color::Black)) {
                    w->color = Color::Red;
                    x = xp;
                    xp = xp->parent;
                } else if (w) {
                    if (!w->left || w->left->color == Color::Black) {
                        w->right->color = Color::Black;
                        w->color = Color::Red;
                        auto wp = w->parent;
                        if (!wp) {
                            LeftRotate(std::move(root));
                        } else if (w == wp->left.get()) {
                            LeftRotate(std::move(wp->left));
                        } else {
                            LeftRotate(std::move(wp->right));
                        }
                        w = xp->left.get();
                    }
                    w->color = xp->color;
                    xp->color = Color::Black;
                    w->left->color = Color::Black;
                    auto xpp = xp->parent;
                    if (!xpp) {
                        RightRotate(std::move(root));
                    } else if (xp == xpp->left.get()) {
                        RightRotate(std::move(xpp->left));
                    } else {
                        RightRotate(std::move(xpp->right));
                    }
                    x = root.get();
                } else {
                    x = root.get();
                }
            }
        }
        if (x) {
            x->color = Color::Black;
        }
    }

};

template <typename T>
std::ostream& operator<<(std::ostream& os, Node<T>* node) {
    if (node) {
        os << node->left.get();
        os << node->key;
        if (node->color == Color::Black) {
            os << "● ";
        } else {
            os << "○ ";
        }
        os << node->right.get();
    }
    return os;
}

template <typename T>
std::ostream& operator<<(std::ostream& os, const RBTree<T>& tree) {
    os << tree.root.get();
    return os;
}

int main() {
    constexpr size_t SIZE = 100'000;
    std::vector<int> v (SIZE);
    std::iota(v.begin(), v.end(), 1);
    std::shuffle(v.begin(), v.end(), gen);
    RBTree<int> rbtree;
    auto t1 = std::chrono::steady_clock::now();
    for (auto n : v) {
        rbtree.Insert(n);
    }
    auto t2 = std::chrono::steady_clock::now();
    auto dt1 = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1);

    std::set<int> rbset;
    t1 = std::chrono::steady_clock::now();
    for (auto n : v) {
        rbset.insert(n);
    }
    t2 = std::chrono::steady_clock::now();
    auto dt2 = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1);

    std::cout << "Inserting " << SIZE << " elements:n";
    std::cout << "unique ptr red-black tree : " << dt1.count() << " msn";
    std::cout << "standard red-black tree : " << dt2.count() << " msn";

    std::shuffle(v.begin(), v.end(), gen);

    t1 = std::chrono::steady_clock::now();
    for (auto n : v) {
        rbtree.Delete(n);
    }
    t2 = std::chrono::steady_clock::now();
    auto dt3 = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1);

    t1 = std::chrono::steady_clock::now();
    for (auto n : v) {
        rbset.erase(n);
    }
    t2 = std::chrono::steady_clock::now();
    auto dt4 = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1);

    std::cout << "Deleting " << SIZE << " elements:n";
    std::cout << "unique ptr red-black tree : " << dt3.count() << " msn";
    std::cout << "standard red-black tree : " << dt4.count() << " msn";

}
```

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?

Proof of red-black tree height

I know that the height of a red-black tree is at most 2 lg (n + 1). But what is the mathematical proof of this? I have searched various sites, but I have not found any good evidence. I already know the properties of a red-black tree.

Temporal Complexity – In the case of a right rotation for red-black trees, there is a less efficient way to recolor it, why is it no longer O (log (n))?

So, the first time I tried to recolor this memory insertion case, I ended up coloring the right side again; Of course, left-handed coloring is more efficient because the loop ends at this point. If, however, we check in the right case if the grandparent of a is the root (the color is black) and if not continue the loop of this node, I read that it makes the recoloration not O (log (n)) more, why is it? I always seem to be O (log (2n)) at worst, even if the number of rotations made is no longer O (1). red-black coloring alternatives

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

I made a red-black tree and I think it's not valid. Can any one please check it?
Red-black tree
As far as I know, in the red-black tree, we also consider leaf nodes located at the NULLS of visible leaf nodes and these NULL nodes are considered black.
So, by this logic, if we consider the order root->left->left->left in black, then no. black nodes at this NULL node are 2.
Also, if we consider the node root->right->right->right->right->right as black, none of the black nodes at this NULL node are 3.
So, according to the argument above, it should not work from a valid red-black tree.
Am I right or missing an important concept?

Data Structures – Restructuration of the trinode of red-black tree after insertion and deletion

When you perform an insert / delete on a red-black tree, how can one argue or prove that it requires at most one / two trinode restructuring (s), respectively?
My thoughts up to now were as follows: after inserting a node and the existence of two consecutive red nodes along a path from the root to the leaf , a restructuring is carried out, followed by a re-coloring, culminating in a red-black tree. Does this mean that after inserting a node, there can only be one red double problem in the tree, which requires a restructuring to solve it? ?

algorithms – Why use heap on red-black tree?

Heap supports insertion operations in O (logn) time. And while the segmentation media suppress the min / max times in O (logn), to remove any element (not min / max), the segment takes O (n) time.

However, the red-black tree supports inserting / removing both in O (logn) time. We can simply delete the first / last element of a red-black tree to remove min / max in O (logn) time.

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

Is there a distinctive advantage to using piles on red-black trees?

Thank you!