chan blog: 13 Red-black Trees Implementation

13 Red-black Trees Impl
2020-09-27
더 해야 할 것
binary search tree 편하게 console에 찍는 함수 이해해서 개량하기
insert 되는 상황 직접 손으로 다 케이스 규명해서 완전 이해하기
delete 되는 상황 직접 손으로 다 케이스 규명해서 완전 이해하기
join 함수 더 테스트
2020-11-22
기존 m_nil 처리가 무언가 이상함을 발견. 따라서 CLRS/rbtree.cpp at master · gzc/CLRS (github.com) 여기 링크를 따라서, 그런 처리를 없애보았더니 insert delete가 잘된다. 좀 더 로직 하나 하나에 대한 이해가 더 필요하다.

xxxxxxxxxx
#pragma once
#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
{
    /*
        Red-black Properties
        1. Every nod is either red or black
        2. The root is black
        3. Every leaf (NIL) is black
        4. If  a node is red, then both its children are black
        5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes
    */
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)
    {
        // TODO : left, right, x key validation that
        // keys of left tree are smaller than x
        // keys of right tree are greater than x
        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)
        {
            // join right into left
            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
        {
            //join left into right
            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]);
        }
    }
    // https://stackoverflow.com/a/13755911
    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; // does not include root color
    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;                      // set x
        y->left = x->right;                     // turn x's right subtree into y's left subtree
        if (x->right != m_nil)
        {
            x->right->parent = y;
        }
        x->parent = y->parent;                  // link y's parent to x
        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;                          // set x
        if (x != m_nil)
        {
            y->left = x->right;                     // turn x's right subtree into y's left subtree
            if (x->right != m_nil)
            {
                x->right->parent = y;
            }
            x->parent = y->parent;                  // link y's parent to x
            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;           // case 1
                    y->color = e_color_black;                   // case 1
                    zpp->color = e_color_red;       // case 1
                    z = zpp;
                }
                else
                {
                    if (z == z->parent->right)
                    {
                        z = z->parent;                          // case 2
                        left_rotate(z);                         // case 2
                    }
                    z->parent->color = e_color_black;           // case 3
                    zpp->color = e_color_red;       // case 3
                    right_rotate(zpp);
                }
            }
            else
            {
                node* y = zpp->left;
                if (y->color == e_color_red)
                {
                    z->parent->color = e_color_black;           // case 1
                    y->color = e_color_black;                   // case 1
                    zpp->color = e_color_red;       // case 1
                    z = zpp;
                }
                else
                {
                    if (z == z->parent->left)
                    {
                        z = z->parent;                          // case 2
                        right_rotate(z);                        // case 2 
                    }
                    z->parent->color = e_color_black;           // case 3
                    zpp->color = e_color_red;       // case 3
                    left_rotate(zpp);               // case 3
                }
            }
        }
        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;                       // case 1
                    x->parent->color = e_color_red;                 // case 1
                    left_rotate(x->parent);                         // case 1
                    w = x->parent->right;
                }
                if (w->left->color == e_color_black && w->right->color == e_color_black)
                {
                    w->color = e_color_red;                         // case 2
                    x = x->parent;                                  // case 2
                }
                else
                {
                    if (w->right->color == e_color_black)
                    {
                        w->left->color = e_color_black;             // case 3
                        w->color = e_color_red;                     // case 3
                        right_rotate(w);                            // case 3
                        w = x->parent->right;                       // case 3
                    }
                    w->color = x->parent->color;                    // case 4
                    x->parent->color = e_color_black;               // case 4
                    w->right->color = e_color_black;                // case 4
                    left_rotate(x->parent);                         // case 4
                    x = m_root;
                }
            }
            else
            {
                w = x->parent->left;
                if (w->color == e_color_red)
                {
                    w->color = e_color_black;                       // case 1
                    x->parent->color = e_color_red;                 // case 1
                    right_rotate(x->parent);                        // case 1
                    w = x->parent->left;
                }
                if (w->left->color == e_color_black && w->right->color == e_color_black)
                {
                    w->color = e_color_red;                         // case 2
                    x = x->parent;                                  // case 2
                }
                else
                {
                    if (w->left->color == e_color_black)
                    {
                        w->right->color = e_color_black;            // case 3
                        w->color = e_color_red;                     // case 3
                        left_rotate(w);                             // case 3
                        w = x->parent->left;                        // case 3
                    }
                    w->color = x->parent->color;                    // case 4
                    x->parent->color = e_color_black;               // case 4
                    w->left->color = e_color_black;                 // case 4
                    right_rotate(x->parent);                        // case 4
                    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;
            // we don't count root color,
            // but root is always black color
            // so set it at first as -1
            int black_height = -1;
            // goto a leaf node
            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
chan blog

Post Lists

2020년 9월 27일 일요일

13 Red-black Trees Implementation

댓글 없음:

댓글 쓰기
