jeudi 16 juillet 2020

Red-Black Tree with std::unique_ptr

I'm playing with Red-Black Tree with std::unique_ptr but it doesn't work.

My node definition:

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}, parent {nullptr}, color {Color::Red} {}
};

I choose std::unique_ptr because std::shared_ptr is expensive and the parent owns its left and right child. Trivially, parent should be a raw pointer.

However, the logic behind Insert function breaks my basic design:

Here are my tree rotate functions. They accept rvalue reference of std::unique_ptr because it actually transfers ownership.

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

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

Here is my Insert function:

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

private:
    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) {
                        z = std::unique_ptr<Node<T>>(zp);
                        auto pz = z.get();
                        LeftRotate(std::move(z));
                        zp = pz->parent;
                        zpp = zp->parent;
                    }
                    zp->color = Color::Black;
                    zpp->color = Color::Red;
                    auto pzpp = std::unique_ptr<Node<T>>(zpp); // error
                    RightRotate(std::move(pzpp)); // error
                }
            } 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) {
                        z = std::unique_ptr<Node<T>>(zp);
                        auto pz = z.get();
                        RightRotate(std::move(z));
                        zp = pz->parent;
                        zpp = zp->parent;
                    }
                    zp->color = Color::Black;
                    zpp->color = Color::Red;
                    auto pzpp = std::unique_ptr<Node<T>>(zpp); // error
                    LeftRotate(std::move(pzpp)); // error
                }
            }
        }
        root->color = Color::Black;
    }

These following lines in InsertFixup are buggy:

auto pzpp = std::unique_ptr<Node<T>>(zpp); // error
LeftRotate(std::move(pzpp)); // error

What I want to do is rotate the tree around the grandma of the node z.

However, the problem is that it is impossible to get the std::unique_ptr that owns the grandma node (which is required to pass to LeftRotate function), because the parent link of my node implementation gives a raw pointer. Of course, I can track down from the root to get, but doing so will break the logarithmic time complexity of the inserting operation of RB-Tree, making it useless.

Should I use std::shared_ptr instead? Is there any way to implement RB-tree with std::unique_ptr implementation?

Aucun commentaire:

Enregistrer un commentaire