#ifndef __RED_BLACK_TREE_H__

#define __RED_BLACK_TREE_H__

#include "precompiled.h"

template<typename rb_t_key, typename rb_t_value>

class red_black_tree

public:

    enum node_color : uint8_t

        e_color_red,

        e_color_black

};

    struct node

        node* parent;

        node* left;

        node* right;

        rb_t_key key;

        rb_t_value value;

        node_color color;

};

    red_black_tree()

        : m_nil{ allocate_node(rb_t_key(), rb_t_value(), e_color_black) }

        , m_root(m_nil)

        , m_node_count(0)

        , m_black_height(0)

{}

    ~red_black_tree()

        if (m_nil != nullptr && m_root != m_nil)

            free_node_recursive(m_root);

            m_root = nullptr;

        if (m_nil != nullptr)

            free_node(m_nil);

            m_nil = nullptr;

    red_black_tree(const red_black_tree<rb_t_key, rb_t_value>& other)

        : m_nil{ allocate_node(rb_t_key(), rb_t_value(), e_color_black) }

        , m_root(m_nil)

        , m_node_count(other.m_node_count)

        , m_black_height(other.m_black_height)

        if (other.m_root != other.m_nil)

            m_root = copy_from_other_red_black_tree_recursive(m_nil, m_nil, other.m_root, other.m_nil);

    red_black_tree(red_black_tree<rb_t_key, rb_t_value>&& other)

        : m_nil(other.m_nil)

        , m_root(other.m_root)

        , m_node_count(other.m_node_count)

        , m_black_height(other.m_black_height)

        other.m_nil = nullptr;

        other.m_root = nullptr;

        other.m_node_count = 0;

        other.m_black_height = 0;

    red_black_tree<rb_t_key, rb_t_value>& operator=(const red_black_tree<rb_t_key, rb_t_value>& other)

        if (this != &other)

            if (m_nil != nullptr && m_root != m_nil)

                free_node_recursive(m_root);

            if (m_nil == nullptr)

                m_nil = allocate_node(rb_t_key(), rb_t_value(), e_color_black);

            m_root = copy_from_other_red_black_tree_recursive(m_nil, m_nil, other.m_root, other.m_nil);

            m_node_count = other.m_node_count;

            m_black_height = other.m_black_height;

        return *this;

    red_black_tree<rb_t_key, rb_t_value>& operator=(red_black_tree<rb_t_key, rb_t_value>&& other)

        if (this != &other)

            if (m_nil != nullptr && m_root != m_nil)

                free_node_recursive(m_root);

            if (m_nil != nullptr)

                free_node(m_nil)

            m_nil = other.m_nil;

            m_root = other.m_root;

            m_node_count = other.m_node_count;

            m_black_height = other.m_black_height;

            other.m_nil = nullptr;

            other.m_root = nullptr;

            other.m_node_count = 0;

            other.m_black_height = 0;

        return *this;

    void insert(const rb_t_key& key, const rb_t_value& value)

        node* n = allocate_node(key, value, e_color_red);

        rb_insert(n);

        ++m_node_count;

    void erase(const rb_t_key& key)

        node* n = m_root;

        while (n != m_nil && key != n->key)

            if (key < n->key)

                n = n->left;

            else

                n = n->right;

        if (is_nil(*n) == false)

            rb_delete(n);

            free_node(n);

            --m_node_count;

    const node& find(const rb_t_key& key) const

        node* x = m_root;

        while (x != m_nil && key != x->key)

            if (key < x->key)

                x = x->left;

            else

                x = x->right;

        return *x;

    const node& find_maximum()

        node* n = get_maximum(m_root);

        return *n;

    const node& find_minimum()

        node* n = get_minimum(m_root);

        return *(n);

    bool is_nil(const node& n) const

        return &n == m_nil;

    int get_black_height() const

        return m_black_height;

    static red_black_tree<rb_t_key, rb_t_value> join(const red_black_tree<rb_t_key, rb_t_value>& left, const node& x, const red_black_tree<rb_t_key, rb_t_value>& right)

        int left_black_height = left.get_black_height();

        int right_black_height = right.get_black_height();

        red_black_tree<rb_t_key, rb_t_value> result;

        if (left_black_height > right_black_height)

            result = left;

            int black_height = -1;

            node* largest_node_with_right_black_height = result.m_root;

            while (largest_node_with_right_black_height != result.m_nil)

                if (largest_node_with_right_black_height->color == e_color_black)

                    ++black_height;

                if (black_height == right_black_height)

                    node* largest_node_parent = largest_node_with_right_black_height->parent;

                    node* new_x_node = result.allocate_node(x.key, x.value, e_color_red);

                    new_x_node->parent = largest_node_parent;

                    new_x_node->left = largest_node_with_right_black_height;

                    new_x_node->right = copy_from_other_red_black_tree_recursive(result.m_nil, new_x_node->right, right.m_root, right.m_nil);

                    if (largest_node_parent->left == largest_node_with_right_black_height)

                        largest_node_parent->left = new_x_node;

                    else

                        largest_node_parent->right = new_x_node;

                    result.rb_insert_fixup(new_x_node);

                    result.update_tree_black_height();

                    result.m_node_count = left.m_node_count + 1 + right.m_node_count;

                    break;

                else

                    largest_node_with_right_black_height = largest_node_with_right_black_height->right;

        else

            result = right;

            int black_height = -1;

            node* smallest_node_with_left_black_height = result.m_root;

            while (smallest_node_with_left_black_height != result.m_nil)

                if (smallest_node_with_left_black_height->color == e_color_black)

                    ++black_height;

                if (black_height == left_black_height)

                    node* smallest_node_parent = smallest_node_with_left_black_height->parent;

                    node* new_x_node = result.allocate_node(x.key, x.value, e_color_red);

                    new_x_node->parent = smallest_node_parent;

                    new_x_node->left = copy_from_other_red_black_tree_recursive(result.m_nil, new_x_node->left, left.m_root, left.m_nil);

                    new_x_node->right = smallest_node_with_left_black_height;

                    if (smallest_node_parent->left == smallest_node_with_left_black_height)

                        smallest_node_parent->left = new_x_node;

                    else

                        smallest_node_parent->right = new_x_node;

                    result.rb_insert_fixup(new_x_node);

                    result.update_tree_black_height();

                    result.m_node_count = left.m_node_count + 1 + right.m_node_count;

                    break;

                else

                    smallest_node_with_left_black_height = smallest_node_with_left_black_height->left;

        return result;

    void print_console_graphically(void(*print_key_value_func)(char[20], const rb_t_key&, const rb_t_value&, node_color))

        constexpr int max_tree_height = 8;

        constexpr int max_node_count = (1 << max_tree_height);

        if (m_root != m_nil)

            char s[32][255];

            for (int i = 0; i < 32; i++)

                sprintf(s[i], "%80s", " ");

            print_console_graphically_recursive(m_root, 0, 0, 0, s, print_key_value_func);

            for (int i = 0; i < 32; ++i)

                printf("%s\n", s[i]);

    int print_console_graphically_recursive(node* node, int is_left, int offset, int height, char s[20][255], void(*print_key_value_func)(char[20], const rb_t_key&, const rb_t_value&, node_color))

        char b[20];

        int width = 7;

        if (node == m_nil) return 0;

        print_key_value_func(b, node->key, node->value, node->color);

        int left = print_console_graphically_recursive(node->left, 1, offset, height + 1, s, print_key_value_func);

        int right = print_console_graphically_recursive(node->right, 0, offset + left + width, height + 1, s, print_key_value_func);

        for (int i = 0; i < width; ++i)

            s[height][offset + left + i] = b[i];

        if (height && is_left)

            for (int i = 0; i < width + right; i++)

                s[height - 1][offset + left + width / 2 + i] = '-';

            s[height - 1][offset + left + width / 2] = '.';

        else if (height && !is_left)

            for (int i = 0; i < left + width; i++)

                s[height - 1][offset - width / 2 + i] = '-';

            s[height - 1][offset + left + width / 2] = '.';

        return left + width + right;

    enum print_flag : uint8_t

        e_print_preorder,

        e_print_inorder,

        e_print_postorder

};

    void print_tree(print_flag flag, void(*print_key_value_func)(const rb_t_key&, const rb_t_value&))

        if (m_root != m_nil)

            switch (flag)

            case e_print_preorder:

                traverse_preorder(m_root, print_key_value_func);

                break;

            case e_print_inorder:

                traverse_inorder(m_root, print_key_value_func);

                break;

            case e_print_postorder:

                traverse_postorder(m_root, print_key_value_func);

                break;

private:

    node* m_nil;

    node* m_root;

    int m_node_count;

    int m_black_height;

    node* allocate_node(const rb_t_key& key, const rb_t_value& value, node_color color)

        node* n = new node();

        n->parent = nullptr;

        n->left = nullptr;

        n->right = nullptr;

        n->color = color;

        n->key = key;

        n->value = value;

        return n;

    void free_node(node* node)

        delete node;

    void free_node_recursive(node* node)

        if (node->left != m_nil)

            free_node_recursive(node->left);

        if (node->right != m_nil)

            free_node_recursive(node->right);

        free_node(node);

    void left_rotate(node* x)

        node* x = y->left;

        y->left = x->right;

        if (x->right != m_nil)

            x->right->parent = y;

        x->parent = y->parent;

        if (y->parent == m_nil)

            m_root = x;

        else if (y == y->parent->left)

            y->parent->left = x;

        else

            y->parent->right = x;

        x->right = y;

        y->parent = x;

    void right_rotate(node* y)

        node* x = y->left;

        if (x != m_nil)

            y->left = x->right;

            if (x->right != m_nil)

                x->right->parent = y;

            x->parent = y->parent;

            if (y->parent == m_nil)

                m_root = x;

            else if (y == y->parent->left)

                y->parent->left = x;

            else

                y->parent->right = x;

            x->right = y;

            y->parent = x;

    void rb_insert(node* z)

        node* y = m_nil;

        node* x = m_root;

        while (x != m_nil)

            y = x;

            if (z->key < x->key)

                x = x->left;

            else

                x = x->right;

        if (y == m_nil)

            m_root = z;

        else if (z->key < y->key)

            y->left = z;

        else

            y->right = z;

        z->parent = y;

        z->left = m_nil;

        z->right = m_nil;

        z->color = e_color_red;

        rb_insert_fixup(z);

        update_tree_black_height();

    void rb_insert_fixup(node* z)

        while (z->parent->color == e_color_red)

            node* zpp = z->parent->parent;

            if (z->parent == zpp->left)

                node* y = zpp->right;

                if (y->color == e_color_red)

                    z->parent->color = e_color_black;

                    y->color = e_color_black;

                    zpp->color = e_color_red;

                    z = zpp;

                else

                    if (z == z->parent->right)

                        z = z->parent;

                        left_rotate(z);

                    z->parent->color = e_color_black;

                    zpp->color = e_color_red;

                    right_rotate(zpp);

            else

                node* y = zpp->left;

                if (y->color == e_color_red)

                    z->parent->color = e_color_black;

                    y->color = e_color_black;

                    zpp->color = e_color_red;

                    z = zpp;

                else

                    if (z == z->parent->left)

                        z = z->parent;

                        right_rotate(z);

                    z->parent->color = e_color_black;

                    zpp->color = e_color_red;

                    left_rotate(zpp);

        m_root->color = e_color_black;

    void rb_transplant(node* u, node* v)

        if (u->parent == m_nil)

            m_root = v;

        else if (u == u->parent->left)

            u->parent->left = v;

        else

            u->parent->right = v;

        v->parent = u->parent;

    void rb_delete_fixup(node* x)

        while (x != m_root && x->color == e_color_black)

            node* w = nullptr;

            if (x == x->parent->left)

                w = x->parent->right;

                if (w->color == e_color_red)

                    w->color = e_color_black;

                    x->parent->color = e_color_red;

                    left_rotate(x->parent);

                    w = x->parent->right;

                if (w->left->color == e_color_black && w->right->color == e_color_black)

                    w->color = e_color_red;

                    x = x->parent;

                else

                    if (w->right->color == e_color_black)

                        w->left->color = e_color_black;

                        w->color = e_color_red;

                        right_rotate(w);

                        w = x->parent->right;

                    w->color = x->parent->color;

                    x->parent->color = e_color_black;

                    w->right->color = e_color_black;

                    left_rotate(x->parent);

                    x = m_root;

            else

                w = x->parent->left;

                if (w->color == e_color_red)

                    w->color = e_color_black;

                    x->parent->color = e_color_red;

                    right_rotate(x->parent);

                    w = x->parent->left;

                if (w->left->color == e_color_black && w->right->color == e_color_black)

                    w->color = e_color_red;

                    x = x->parent;

                else

                    if (w->left->color == e_color_black)

                        w->right->color = e_color_black;

                        w->color = e_color_red;

                        left_rotate(w);

                        w = x->parent->left;

                    w->color = x->parent->color;

                    x->parent->color = e_color_black;

                    w->left->color = e_color_black;

                    right_rotate(x->parent);

                    x = m_root;

        x->color = e_color_black;

    void rb_delete(node* z)

        node* x = m_nil;

        node* y = z;

        node_color y_original_color = y->color;

        if (z->left == m_nil)

            x = z->right;

            rb_transplant(z, z->right);

        else if (z->right == m_nil)

            x = z->left;

            rb_transplant(z, z->left);

        else

            y = get_minimum(z->right);

            y_original_color = y->color;

            x = y->right;

            if (y->parent == z)

                x->parent = y;

            else

                rb_transplant(y, y->right);

                y->right = z->right;

                y->right->parent = y;

            rb_transplant(z, y);

            y->left = z->left;

            y->left->parent = y;

            y->color = z->color;

        if (y_original_color == e_color_black)

            rb_delete_fixup(x);

        update_tree_black_height();

    node* get_minimum(node* x)

        while (x->left != m_nil)

            x = x->left;

        return x;

    node* get_maximum(node * x)

        while (x->right != m_nil)

            x = x->right;

        return x;

    node* get_successor(node* x)

        if (x->right != m_nil)

            return get_minimum(x->right);

        node* y = x->parent;

        while (y != m_nil && x == y->right)

            x = y;

            y = y->parent;

        return y;

    node* get_predecessor(node* x)

        if (x->left != m_nil)

            return get_maximum(x->left);

        node* y = x->parent;

        while (y != m_nil && x == y->left)

            x = y;

            y = y->parent;

        return y;

    static node* copy_from_other_red_black_tree_recursive(node* my_nil, node* my_parent, node* other_node, node* other_node_nil)

        node* new_node = new node();

        new_node->color = other_node->color;

        new_node->key = other_node->key;

        new_node->value = other_node->value;

        new_node->parent = my_parent;

        new_node->left = my_nil;

        new_node->right = my_nil;

        if (other_node->left != other_node_nil)

            new_node->left = copy_from_other_red_black_tree_recursive(my_nil, new_node, other_node->left, other_node_nil);

        if (other_node->right != other_node_nil)

            new_node->right = copy_from_other_red_black_tree_recursive(my_nil, new_node, other_node->right, other_node_nil);

        return new_node;

    void update_tree_black_height()

        if (m_root != m_nil)

            node* x = m_root;

            int black_height = -1;

            while (x != m_nil)

                if (x->color == e_color_black)

                    ++black_height;

                if (x->left != m_nil)

                    x = x->left;

                else if (x->right != m_nil)

                    x = x->right;

                else

                    x = m_nil;

            m_black_height = black_height;

        else

            m_black_height = 0;

    void traverse_preorder(node* n, void(*print_key_value_func)(const rb_t_key&, const rb_t_value&))

        print_key_value_func(n->key, n->value);

        if (n->left != m_nil)

            traverse_preorder(n->left, print_key_value_func);

        if (n->right != m_nil)

            traverse_preorder(n->right, print_key_value_func);

    void traverse_inorder(node* n, void(*print_key_value_func)(const rb_t_key&, const rb_t_value&))

        if (n->left != m_nil)

            traverse_inorder(n->left, print_key_value_func);

        print_key_value_func(n->key, n->value);

        if (n->right != m_nil)

            traverse_inorder(n->right, print_key_value_func);

    void traverse_postorder(node* n, void(*print_key_value_func)(const rb_t_key&, const rb_t_value&))

        if (n->left != m_nil)

            traverse_postorder(n->left, print_key_value_func);

        if (n->right != m_nil)

            traverse_postorder(n->right, print_key_value_func);

        print_key_value_func(n->key, n->value);

};

#endif

13 Red-black Trees Implementation

댓글