Красно-черная вставка дерева CLRS

Question

Красно-черная вставка дерева CLRS

Алгоритм, описанный в CLRS 3 изд. выглядит неправильно. Я пытался реализовать, но вставка не работает нормально.

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>

using namespace std;

const char BLACK = 'B';
const char RED = 'R';

template <class T>
class Node{

    public:
        Node *left;
        Node *right;
        Node *parent;
        char color;
        T key;

        Node(T x){
            this->left = NULL;
            this->right = NULL;
            this->parent = NULL;
            this->key = x;
            this->color = RED;
        };

        virtual ~Node(){};
};

template <class T>
class RedBlackTree{

    private:

        int ammount;
        int h;
        int lastAmmount;
        Node<T> *root;
        Node<T> *NIL;

        void destroy_node(Node<T> *&node);
        Node<T> *remove_node(Node<T> *&node, T x);  // not imeplemented yet
        Node<T> *search_node(Node<T> *&node, T x);  // not imeplemented yet

        void printInfo(Node<T> *&x);
        void printInOrder_node(Node<T> *&node);

        void printInLevel_node(Node<T> *&node, int level);
        int calculeHeight(Node<T> *&node);

        void rotateLeft(Node<T> *&x);
        void rotateRight(Node<T> *&y);
        void insertFixUp(Node<T> *&x);


    public:

        RedBlackTree();
        virtual ~RedBlackTree();
        void destroy();

        void insert(T x);
        void remove(T x);       // not imeplemented yet
        Node<T> *search(T x);   // not implemented yet

        int height();
        void printInOrder();
        void printInLevel();
};


template <class T>
RedBlackTree<T>::RedBlackTree(){

    this->ammount = 0;
    this->lastAmmount = -1;
    this->h = 0;

    this->NIL = new Node<T>(-1);
    this->NIL->color = BLACK;
    this->NIL->left = this->NIL->right = this->NIL->parent = this->NIL;


    this->root = this->NIL;
    this->root->color = BLACK;
}

template <class T>
RedBlackTree<T>::~RedBlackTree(){
    delete this->root;
}



template <class T>
void RedBlackTree<T>::destroy_node(Node<T> *&node){
    if(node != NULL){
        this->destroy(node->left);
        this->destroy(node->right);
        delete node;
    }
}

template <class T>
void RedBlackTree<T>::destroy(){
    this->destroy_node(this->root);
}





// RB methods
template <class T>
void RedBlackTree<T>::rotateLeft(Node<T> *&x){

    Node<T> *y = x->right;
    x->right = y->left;

    if(y->left != this->NIL)
        y->left->parent = x;

    y->parent = x->parent;

    if(x->parent == this->NIL)
        this->root = y;
    else if(x == x->parent->left)
        x->parent->left = y;
    else
        x->parent->right = y;

    y->left = x;
    x->parent = y;
}


template <class T>
void RedBlackTree<T>::rotateRight(Node<T> *&y){

    Node<T> *x = y->left;
    y->left = x->right;

    if(x->right != this->NIL)
        x->right->parent = y;

    x->parent = y->parent;

    if(y->parent == this->NIL)
        this->root = x;
    else if(y == y->parent->left)
        y->parent->left = x;
    else
        y->parent->right = x;

    x->right = y;
    y->parent = x;
}


template <class T>
void RedBlackTree<T>::insertFixUp(Node<T> *&z){


    Node<T> *y;

    while(z != this->root and z->parent->color == RED){
        if(z->parent == z->parent->parent->left){
            y = z->parent->parent->right;
            if(y->color == RED){
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            }
            else{
                if(z == z->parent->right){
                    z = z->parent;
                    this->rotateLeft(z);
                }

                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                this->rotateRight(z->parent->parent);
            }
        }
        else{
            y = z->parent->parent->left;
            if(y->color == RED){
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            }
            else{
                if(z == z->parent->left){
                    z = z->parent;
                    this->rotateRight(z);
                }

                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                this->rotateLeft(z->parent->parent);
            }
        }
    }


    this->root->color = BLACK;

}



template <class T>
void RedBlackTree<T>::insert(T val){

    Node<T> *z = new Node<T>(val);
    Node<T> *x = this->root;
    Node<T> *y = this->NIL;

    while(x != this->NIL){
        y = x;
        if(z->key < x->key)
            x = x->left;
        else
            x = x->right;
    }


    z->parent = y;

    if(y == this->NIL)
        this->root = z;
    else if(z->key < y->key)
        y->left = z;
    else
        y->right = z;


    z->left = this->NIL;
    z->right = this->NIL;
    z->color = RED;

    this->insertFixUp(z);
}





template <class T>
int RedBlackTree<T>::height(){

    if(this->lastAmmount == this->ammount)
        return this->h;

    this->h = this->calculeHeight(this->root);
    this->lastAmmount = this->ammount;
    return this->h;
}


template <class T>
int RedBlackTree<T>::calculeHeight(Node<T> *&node){
    if(node == this->NIL)
        return 0;

    int l_h = this->calculeHeight(node->left);
    int r_h = this->calculeHeight(node->right);

    if(l_h > r_h)
        return l_h+1;

    return r_h+1;
}



template <class T>
void RedBlackTree<T>::printInfo(Node<T> *&x){
    cout << "key=";
    cout << x->key;

    cout << "  l->key=";
    if( x->left == this->NIL) 
        cout << "N";
    else 
        cout << x->left->key;

    cout << "  r->key=";
    if( x->right == this->NIL) 
        cout << "N";
    else 
        cout << x->right->key;

    cout << "  p->key=";
    if( x->parent == this->NIL) 
        cout << "N";
    else 
        cout << x->parent->key;

    cout << "  color=" << x->color << endl;
}

template <class T>
void RedBlackTree<T>::printInOrder_node(Node<T> *&node){
    if(node != this->NIL){
        this->printInOrder_node(node->left);
        //cout << " " << node->key;
        this->printInfo(node);
        this->printInOrder_node(node->right);
    }
}

template <class T>
void RedBlackTree<T>::printInOrder(){
    this->printInOrder_node(this->root);
}



template <class T>
void RedBlackTree<T>::printInLevel(){
    int h = this->height();
    for(int i=1; i<=h; i++)
        this->printInLevel_node(this->root, i);
}


template <class T>
void RedBlackTree<T>::printInLevel_node(Node<T> *&node, int level){
    if(node == this->NIL)
        return;

    if(level == 1)
        this->printInfo(node); //cout << node->key << " ";
    else if(level > 1){
        this->printInLevel_node(node->left, level-1);
        this->printInLevel_node(node->right, level-1);
    }
}





int main(){


    RedBlackTree<int> *bt = new RedBlackTree<int>();

    int v[9] = {11, 2, 14, 1, 7, 15, 5, 8, 4};
    for(int i=0; i<9; i++){
        int x = v[i];
        cout << x << " ";
        bt->insert(x);
    }

    cout << endl;

    cout << "In Level:" << endl; 
    bt->printInLevel();
    cout << endl;



    delete bt;

    return 0;
}

Я пытался найти некоторые другие объяснения в предыдущих темах, но, похоже, не работает. Этот код в основном равен псевдокоду книги. Ожидаемый результат для основного примера находится на уровне:

       7
     /   \
   2      11
 /  \    /  \
1    5  8    14
    /         \
   4           15

Так что не так? Спасибо!

2

c++ binary-tree red-black-tree

Источник

user4181815 26 окт '14 в 04:18

1 ответ

Другие вопросы по тегам c++ binary-tree red-black-tree

user128940 26 окт '14 в 06:35 2014-10-26 06:35 · Answer 1 · 2014-10-26 06:35

Посмотрите, что происходит, когда вы добавляете второй узел. Вы начинаете с этого:

11 (black)

затем добавьте новый узел:

  11 (black)
 /
2 (red)

затем попытайтесь исправить это:

template <class T>
void RedBlackTree<T>::insertFixUp(Node<T> *&z){
  Node<T> *y;

  while(z != this->root and z->parent->color == RED){
    ...
  }
this->root->color = BLACK;
}

Обратите внимание, что с 11 черный для начала, управление никогда не входит в цикл, поэтому вызов insertFixUp ничего не делает. Таким образом, у вас осталось дерево с красным листом, которое не является действительным красно-черным деревом. После этого, если ваш код рассчитан на корректное красно-черное дерево, он может ошибиться.

Могут быть и другие ошибки, но вы должны попытаться заставить дерево с двумя узлами работать, прежде чем пытаться добавить третий узел.