rb_tree.cpp

#include <iostream>
#include <memory>
#include <cassert>

enum class node_color {
    red,
    black
};

template<typename DataType>
struct node {
    node_color color;
    std::weak_ptr<node<DataType>> parent;
    std::shared_ptr<node<DataType>> left;
    std::shared_ptr<node<DataType>> right;
    DataType data;
};

template<typename DataType>
std::ostream& operator<<(std::ostream& os, node<DataType> const& node) {
    os  << ((node.color == node_color::black) ? '(' : '[');
    if (node.left) { os << *(node.left); } else { os << '_'; }
    os  << '|' 
        << node.data 
        << '|';
    if (node.right) { os << *(node.right); } else { os << '_'; }
    os  << ((node.color == node_color::black) ? ')' : ']');
    return os;
}

template<typename DataType>
auto rotate_left(node<DataType>& node) {
    auto right_child = node.right;
    assert(node.right);
    
    auto parent = node.parent;
    auto right_child_left = right_child->left;
    right_child->parent = parent;
    right_child->left = node;
    node.parent = right_child;
    node.right = right_child_left;
    return right_child;
}

template<typename DataType>
auto rotate_right(node<DataType>& node) {
    auto left_child = node.left;
    assert(node.left);
    
    auto parent = node.parent;
    auto left_child_right = left_child->right;
    left_child->parent = parent;
    left_child->right = node;
    node.parent = left_child;
    node.left = left_child_right;
    return left_child;
}

template<typename DataType, typename Obj>
auto push_node(std::shared_ptr<node<DataType>>& root, Obj obj) {
    if (!root) {
        root = std::make_shared<node<DataType>>(node<DataType>{
            node_color::red,
            {},
            nullptr,
            nullptr,
            std::move(obj)
        });
        return root;
    } else {
        // @todo
        return std::shared_ptr<node<DataType>>(nullptr);
    }
}

template<typename DataType>
struct rb_tree {
public:
    template<typename X>
    void push(X&& obj) {
        root = push_node(root, std::forward<X>(obj));
    }
    
    template<typename X>
    friend std::ostream& operator<<(std::ostream&, rb_tree<X> const&);
private:
    std::shared_ptr<node<DataType>> root;
};

template<typename DataType>
std::ostream& operator<<(std::ostream& os, rb_tree<DataType> const& tree) {
    os << *tree.root;
    return os;
}

int main() {
    rb_tree<int> tree;
    tree.push(123);
    std::cout << tree;
}