[C++] Nieprawidłowe przekolorowywanie drzewa czerwono czarnego po dodaniu nowego elementu.

#include "pch.h"
#include <iostream>
#include <random>
#include <string>
#include <functional>
using namespace std;

enum Color { Black, Red };
template < typename T >
class RBTree;

template < typename T >
class Node
{
    friend class RBTree < T >;
    T data;
    Color color;
    Node * parent;
    Node * leftChild;
    Node * rightChild;
public:
    Node()
    {
        this->parent = nullptr;
        this->leftChild = nullptr;
        this->rightChild = nullptr;
        //color = Red;
    }
    void gibColor( Node < T >* x )
    {
        if( x->color == Black )
             cout << "czarny";
        else
             cout << "czerowny";
       
    }
};

template < typename T >
class RBTree
{
    Node < T >* root;
    int size;
public:
    RBTree()
    {
        root = nullptr;
        size = 1;
    }
   
    void leftRotate( Node < T >* child, Node < T >* parent )
    {
        child = parent->rightChild;
        parent->rightChild = child->leftChild;
        if( child->leftChild != nullptr )
        {
            child->leftChild->parent = parent;
        }
       
        child->parent = parent->parent;
        if( parent->parent == nullptr )
        {
            root = child;
        }
        else if( parent == parent->parent->leftChild )
        {
            parent->parent->leftChild = child;
        }
        else {
            parent->parent->rightChild = child;
        }
       
        child->leftChild = parent;
        parent->parent = child;
    }
    void rightRotate( Node < T >* child, Node < T >* parent )
    {
        child = parent->leftChild;
        parent->leftChild = child->rightChild;
        if( child->rightChild != nullptr )
        {
            child->rightChild->parent = parent;
        }
        child->parent = parent->parent;
        if( parent->parent == nullptr )
        {
            root = child;
        }
        else if( parent == parent->parent->rightChild )
        {
            parent->parent->rightChild = child;
        }
        else
        {
            parent->parent->leftChild = child;
        }
       
        child->rightChild = parent;
        parent->parent = child;
    }
    void fixViolation( Node < T >* n )
    {
        Node < T >* grandparent;
        Node < T >* parent;
        Node < T >* uncle;
        parent = n->parent;
        while( parent != nullptr && parent->color == Red )
        {
            grandparent = n->parent->parent;
            if( grandparent->leftChild == parent )
            {
                uncle = grandparent->rightChild;
                if( uncle != nullptr && uncle->color == Red )
                {
                    parent->color = Black;
                    uncle->color = Black;
                    grandparent->color = Red;
                    n = grandparent;
                    parent = n->parent;
                }
                else
                {
                    if( parent->rightChild == n )
                    {
                        n = parent;
                        leftRotate( n->parent, n );
                    }
                   
                    parent->color = Black;
                    grandparent->color = Red;
                    rightRotate( parent, grandparent );
                }
            }
            else
            {
                uncle = grandparent->leftChild;
                if( uncle != nullptr && uncle->color == Red )
                {
                    uncle->color = Black;
                    parent->color = Black;
                    grandparent->color = Red;
                    n = grandparent;
                    parent = n->parent;
                }
                else
                {
                    if( parent->leftChild == n )
                    {
                        n = parent;
                        rightRotate( n->parent, n );
                    }
                   
                    parent->color = Black;
                    grandparent->color = Red;
                    leftRotate( parent, grandparent );
                }
            }
            //root->color = Black;
        }
        root->color = Black;
    }
   
    void addElement( T el )
    {
        Node < T >* n = new Node < T >();
        n->data = el;
        n->leftChild = nullptr;
        n->rightChild = nullptr;
        n->color = Red;
        Node < T >* temp = this->root;
        Node < T >* y = nullptr;
        if( root == nullptr )
        {
            n->color = Black;
            root = n;
        }
        else
        {
            while( temp != nullptr )
            {
                y = temp;
                if( temp->data < n->data )
                {
                    temp = temp->rightChild;
                }
                else
                {
                    temp = temp->leftChild;
                }
            }
            n->parent = y;
            if( y->data == n->data )
            {
                cout << "Duplikaty won!" << endl;
                return;
            }
            if( y->data < n->data )
            {
                y->rightChild = n;
                size = size + 1;
            }
            else
            {
                y->leftChild = n;
                size = size + 1;
            }
            fixViolation( n );
        }
       
    }
    void print( Node < T >* x )
    {
       
        //cout << "size: " << size << endl;
        if( x == nullptr )
        {
            return;
        }
        if( x->parent == nullptr )
        {
            cout << "(" << x->data << ")";
            cout << "[" << "kolor:";
            x->gibColor( x );
            cout << ", rodzic: NULL," << " l.dziecko: ";
            if( x->leftChild == nullptr )
            {
                cout << "NIL";
            }
            else
                 cout << x->leftChild->data;
           
            cout << ", p. dziecko: ";
            if( x->rightChild == nullptr )
            {
                cout << "NIL";
            }
            else
                 cout << x->rightChild->data;
           
            cout << "]";
            cout << "-korzen " << endl;
            //rodzic, l.dziecko, p.dziecko
           
        }
        else if( x->parent->leftChild == x )
        {
            //int c = x->gibColor(x);
            cout << "(" << x->data << ")";
            cout << "[" << "kolor:";
            x->gibColor( x );
            cout << ", rodzic: " << x->parent->data << ", l.dziecko: ";
            if( x->leftChild == nullptr )
            {
                cout << "NIL";
            }
            else
                 cout << x->leftChild->data;
           
            cout << ", p. dziecko: ";
            if( x->rightChild == nullptr )
            {
                cout << "NIL" << "]" << endl;
            }
            else
                 cout << x->rightChild->data << "]" << endl;
           
        }
        else
        {
            cout << "(" << x->data << ")";
            cout << "[" << "kolor:";
            x->gibColor( x );
            cout << ", rodzic: " << x->parent->data << ", l.dziecko: ";
            if( x->leftChild == nullptr )
            {
                cout << "NIL";
            }
            else
                 cout << x->leftChild->data;
           
            cout << ", p. dziecko: ";
            if( x->rightChild == nullptr )
            {
                cout << "NIL" << "]" << endl;;
            }
            else
                 cout << x->rightChild->data << "]" << endl;
           
        }
        print( x->leftChild );
        print( x->rightChild );
       
    }
    void printTree()
    {
       
        if( root == nullptr )
        {
            cout << "Puste drzewo!" << endl;
           
        }
        else
             print( root );
       
    }
};
int randomInt()
{
    uniform_int_distribution < int > rozklad { 0, 11000000 };
    default_random_engine generator { 11 };
    function < int() > los { bind( rozklad, generator ) };
    int l = los();
    return l;
}
int main()
{
    RBTree < int >* d1 = new RBTree < int >();
    d1->addElement( 55 );
    d1->addElement( 69 );
    d1->addElement( 62 );
    d1->addElement( 71 );
    d1->addElement( 70 );
    d1->addElement( 14 );
    d1->addElement( 17 );
    d1->addElement( 3 );
    d1->addElement( 20 );
    d1->printTree();
}

#include <iostream>
#include <string>
#include <iomanip>
#include <ios>

using namespace std;

enum class Color { Black, Red };

template < typename T >
struct Node
{
    T data;
    Color color;
    Node < T > * parent, * left, * right;
   
    Node < T >( T data )
        : data
    { data }, color { Color::Red }, parent { nullptr }, left { nullptr }, right { nullptr } { }
};

template < typename T >
ostream & operator <<( ostream & os, const Node < T >& node )
{
    os << left << setw( 12 ) <<( node.color == Color::Red ? "Red"
        : "Black" );
    os << left << setw( 12 ) << node.data;
    os << left << setw( 12 ) <<( node.parent == nullptr ? "null"
        : to_string( node.parent->data ) );
    os << left << setw( 12 ) <<( node.left == nullptr ? "null"
        : to_string( node.left->data ) );
    os << left << setw( 12 ) <<( node.right == nullptr ? "null"
        : to_string( node.right->data ) ) << "\n";
   
    if( node.left != nullptr ) os << * node.left;
   
    if( node.right != nullptr ) os << * node.right;
   
    return os;
}

template < typename T >
class RBTree
{
   
public:
   
    void insertValue( T n )
    {
        auto node = new Node < T >( n );
        root = insertBST( root, node );
        fixInsertRBTree( node );
    }
   
    void printTree()
    {
        cout << left << setw( 12 ) << "Node color";
        cout << left << setw( 12 ) << "Node data";
        cout << left << setw( 12 ) << "Parent";
        cout << left << setw( 12 ) << "LChild";
        cout << left << setw( 12 ) << "RChild" << "\n";
        cout << "------------------------------------------------------\n";
        cout << * root;
    }
   
private:
   
    Color getColor( Node < T >* node )
    {
        return( node == nullptr ) ? Color::Black
            : node->color;
    }
   
    void setColor( Node < T >* node, Color color )
    {
        if( node == nullptr ) return;
       
        node->color = color;
    }
   
    Node < T >* insertBST( Node < T >* root, Node < T >* ptr )
    {
        if( root == nullptr ) return ptr;
       
        if( ptr->data < root->data )
        {
            root->left = insertBST( root->left, ptr );
            root->left->parent = root;
        }
        else if( ptr->data > root->data )
        {
            root->right = insertBST( root->right, ptr );
            root->right->parent = root;
        }
       
        return root;
    }
   
    void fixInsertRBTree( Node < T >* ptr )
    {
        Node < T >* parent { nullptr };
        Node < T >* grandparent { nullptr };
       
        while( ptr != root && getColor( ptr ) == Color::Red && getColor( ptr->parent ) == Color::Red )
        {
            parent = ptr->parent;
            grandparent = parent->parent;
            if( parent == grandparent->left )
            {
                Node < T >* uncle = grandparent->right;
                if( getColor( uncle ) == Color::Red )
                {
                    setColor( uncle, Color::Black );
                    setColor( parent, Color::Black );
                    setColor( grandparent, Color::Red );
                    ptr = grandparent;
                }
                else
                {
                    if( ptr == parent->right )
                    {
                        rotateLeft( parent );
                        ptr = parent;
                        parent = ptr->parent;
                    }
                    rotateRight( grandparent );
                    swap( parent->color, grandparent->color );
                    ptr = parent;
                }
            }
            else
            {
                Node < T >* uncle = grandparent->left;
                if( getColor( uncle ) == Color::Red )
                {
                    setColor( uncle, Color::Black );
                    setColor( parent, Color::Black );
                    setColor( grandparent, Color::Red );
                    ptr = grandparent;
                }
                else
                {
                    if( ptr == parent->left )
                    {
                        rotateRight( parent );
                        ptr = parent;
                        parent = ptr->parent;
                    }
                    rotateLeft( grandparent );
                    swap( parent->color, grandparent->color );
                    ptr = parent;
                }
            }
        }
        setColor( root, Color::Black );
    }
   
    void rotateLeft( Node < T >* ptr )
    {
        Node < T >* right_child = ptr->right;
        ptr->right = right_child->left;
       
        if( ptr->right != nullptr ) ptr->right->parent = ptr;
       
        right_child->parent = ptr->parent;
       
        if( ptr->parent == nullptr ) root = right_child;
        else if( ptr == ptr->parent->left ) ptr->parent->left = right_child;
        else ptr->parent->right = right_child;
       
        right_child->left = ptr;
        ptr->parent = right_child;
    }
   
    void rotateRight( Node < T >* ptr )
    {
        Node < T >* left_child = ptr->left;
        ptr->left = left_child->right;
       
        if( ptr->left != nullptr ) ptr->left->parent = ptr;
       
        left_child->parent = ptr->parent;
       
        if( ptr->parent == nullptr ) root = left_child;
        else if( ptr == ptr->parent->left ) ptr->parent->left = left_child;
        else ptr->parent->right = left_child;
       
        left_child->right = ptr;
        ptr->parent = left_child;
    }
   
    Node < T >* root { nullptr };
   
};

int main()
{
    RBTree < int > tree;
    for( int index = 0; index < 15; ++index )
    {
        tree.insertValue( rand() % 1000 );
    }
    tree.printTree();
}