Drzewo Czerwono-Czarne 1.0

//ALGO2 IS1 211A LAB03
//Jakub Ogryzek
//oj44443@zut.edu.pl
#include "pch.h"
#include <iostream>
#include <ctime>
#include <random>

using namespace std;

template <typename T>
class Node {
public:
    T data;
    Node *left;
    Node *right;
    Node *parent;
    //0 to czerwony, 1 to czarny;
    bool color;
    Node()
    {
        //left = nullptr;
        //right = nullptr;
        //parent = nullptr;
        //color = 1;
    }
};

template <typename T>
class Tree {
public:
    Node<T> *root;
    int counter;
    Tree()
    {
        counter = 0;
        root = nullptr;
    }
    bool Insert(const T&data)
    {
        if (root == nullptr)
        {
            root = new Node<T>;
            root->data = data;
            counter += 1;
        }
        else
        {
            Node<T> *current;
            current = root;
            while (current != nullptr)
            {
                if (data < current->data)
                {
                    //w lewo
                    if (current->left == nullptr)
                    {
                        current->left = new Node<T>;
                        current->left->data = data;
                        current->left->parent = current;
                        counter += 1;
                        current = current->left;
                        return 1;
                    }
                    else
                    {
                        current = current->left;
                    }
                }
                if (data > current->data)
                {
                    //w prawo
                    if (current->right == nullptr)
                    {
                        current->right = new Node<T>;
                        current->right->data = data;
                        current->right->parent = current;
                        counter += 1;
                        current = current->right;
                        return 1;
                    }
                    else
                    {
                        current = current->right;
                    }
                }
                if (data == current->data)
                {
                    //element sie powtarza
                    return 0;
                }
            }
        }
    }
    bool AddNewElement(const T&data)
    {
        //0 to czerwony, 1 to czarny;
        int flag = Insert(data);
        if (flag == 0)
            return 0;
        Node<T>*x = ReturnFunction(data);
        x->color = 0;
        while (x != root && x->parent->color == 0)
        {
            if (x->parent == x->parent->parent->left)
            {
                Node<T>*y = x->parent->parent->right;
                if (y != nullptr && y->color == 0)
                {
                    x->parent->color = 1;
                    y->color = 1;
                    x->parent->parent->color = 0;
                    x = x->parent->parent;
                }
                else
                {
                    if (x == x->parent->right)
                    {
                        RotateLeft(x);
                        //x = x->parent;
                    }
                    x->color = 1; //x->parent->color = 1;
                    x->parent->color = 0; //x->parent->parent->color = 0;
                    RotateRight(x); //RotateRight(x->parent);
                }
            }
            else
            {
                Node<T>*y = x->parent->parent->left;
                if (y!=nullptr && y->color == 0)
                {
                    x->parent->color = 1;
                    y->color = 1;
                    x->parent->parent->color = 0;
                    x = x->parent->parent;
                }
                else
                {
                    if (x == x->parent->left)
                    {
                        RotateRight(x);
                        //x = x->parent;
                    }
                    x->color = 1; //x->parent->color = 1;
                    x->parent->color = 0; // x->parent->parent->color = 0;
                    RotateLeft(x); //RotateLeft(x->parent);
                }
            }
        }
        root->color = 1;
        return 1;
    }
    Node<T> *ReturnFunction(const T&key)
    {
        Node<T> *current;
        current = root;
        if (current->data == key)
        {
            return current;
        }
        else
        {
            while (current != nullptr)
            {
                if (current->data > key)
                {
                    //w lewo
                    //current = current->left;
                    if (current->left != nullptr)
                    {
                        if (current->left->data == key)
                        {
                            return current->left;
                        }
                    }
                }
                if (current->data > key)
                    current = current->left;
                if (current->data < key)
                {
                    //w prawo
                    //current = current->right;
                    if (current->right != nullptr)
                    {
                        if (current->right->data == key)
                        {
                            return current->right;
                        }
                    }
                }
                if (current->data < key)
                    current = current->right;
            }
        }
        return NULL;
    }
    Node<T> *SearchElement(const T&key)
    {
        Node<T> *current;
        current = root;
        if (current->data == key)
        {
            cout << "Znaleziono wezel o podanym kluczu (" << current->data << ")" << endl;
            return current;
        }
        else
        {
            while (current != nullptr)
            {
                if (current->data > key)
                {
                    //w lewo
                    //current = current->left;
                    if (current->left != nullptr)
                    {
                        if (current->left->data == key)
                        {
                            cout << "Znaleziono wezel o podanym kluczu (" << current->left->data << ")" << endl;
                            return current->left;
                        }
                    }
                }
                if (current->data > key)
                    current = current->left;
                if (current->data < key)
                {
                    //w prawo
                    //current = current->right;
                    if (current->right != nullptr)
                    {
                        if (current->right->data == key)
                        {
                            cout << "Znaleziono wezel o podanym kluczu (" << current->right->data << ")" << endl;
                            return current->right;
                        }
                    }
                }
                if (current->data < key)
                    current = current->right;
            }
        }
        cout << "Nie znaleziono wezla o podanym kluczu (" << key << ")" << endl;
        return NULL;
    }
    void PreOrderRek(Node<T> *current)
    {
        cout << current->data << ", ";
        if (current->left != nullptr)
            PreOrderRek(current->left);
        if (current->right != nullptr)
            PreOrderRek(current->right);
    }
    void PreOrder()
    {
        Node<T> *current;
        current = root;
        cout << "Przejscie Pre-Order:" << endl;
        PreOrderRek(current);
        cout << endl;
    }
    void InOrderRek(Node<T> *current)
    {
        if (current->left != nullptr)
            InOrderRek(current->left);
        cout << current->data << ", ";
        if (current->right != nullptr)
            InOrderRek(current->right);
    }
    void InOrder()
    {
        Node<T> *current;
        current = root;
        cout << "Przejscie In-Order:" << endl;
        InOrderRek(current);
        cout << endl;
    }
    void ToStringRek(Node<T> *current)
    {
        ToStringFunction(current);
        if (current->left != nullptr)
            ToStringRek(current->left);
        if (current->right != nullptr)
            ToStringRek(current->right);
    }
    void ToStringFunction(Node<T> *current)
    {
        cout << "(" << current->data << ") [";
        if (current->color == 1)
            cout << "black";
        if (current->color == 0)
            cout << "red";
        if (current->parent == nullptr)
            cout << ", parent: NULL, left: ";
        else
            cout << ", parent: " << current->parent->data << ", left: ";
        if (current->left == nullptr)
            cout << "NULL, right: ";
        else
            cout << current->left->data << ", right: ";
        if (current->right == nullptr)
            cout << "NULL]";
        else
            cout << current->right->data << "]";
        cout << endl;
    }
    int HeightRek(Node <T> *current)
    {
        if (current == nullptr)
            return 0;
        int height_left = HeightRek(current->left);
        int height_right = HeightRek(current->right);
        if (height_left < height_right)
            return height_right + 1;
        else
            return height_left + 1;
    }
    void Height()
    {
        Node<T> *current;
        current = root;
        int tree_height = HeightRek(current);
        cout << "Wysokosc drzewa wynosi: " << tree_height << endl;
    }
    void ToString()
    {
        cout << "red black tree:" << endl;
        cout << "size: " << counter << endl;
        Node<T> *current;
        current = root;
        ToStringRek(current);
    }
    void DeleteTree(Node <T> *root)
    {
        if (root->left != nullptr)
            DeleteTree(root->left);
        if (root->right != nullptr)
            DeleteTree(root->right);
        delete root;
    }
    void RotateLeft(Node<T> *Y)
    {
        Node<T> *X = Y->parent;
        if (X->right == Y)
        {
            X->right = Y->left;
            if (Y->left != nullptr)
                Y->left->parent = X;
            if (X->parent != nullptr) {
                Y->parent = X->parent;
                if (X == X->parent->right)
                    X->parent->right = Y;
                else
                    X->parent->left = Y;
            }
            else
                Y->parent = nullptr;
            Y->left = X;
            X->parent = Y;
            if (X == root)
                root = Y;
        }
        else
            cout << "Wezel Y nie jest prawym dzieckiem wezla X" << endl;
    }
    void RotateRight(Node<T>*X)
    {
        Node<T> *Y = X->parent;
        if (Y->left == X)
        {
            Y->left = X->right;
            if (X->right != nullptr)
                X->right->parent = Y;
            if (Y->parent != nullptr) {
                X->parent = Y->parent;
                if (Y == Y->parent->left)
                    Y->parent->left = X;
                else
                    Y->parent->right = X;
            }
            else
                X->parent = nullptr;
            X->right = Y;
            Y->parent = X;
            if (Y == root)
                root = X;
        }
        else
            cout << "Wezel X nie jest lewym dzieckiem wezla Y" << endl;
    }
};

struct Struktura
{
    int pole1;
    char pole2;
    Struktura()
    {
        const int MAX_ORDER = 8;
        const int n = pow(10, MAX_ORDER);
        std::random_device rd;
        std::default_random_engine generator(rd());
        std::uniform_int_distribution<long long> zakres(0, n);
        pole1 = zakres(generator);
        pole2 = rand() % ('z' - 'a' + 1) + 'a';
    }
    Struktura(int a, char b)
    {
        pole1 = a;
        pole2 = b;
    }
    bool operator ==(const Struktura&n) const
    {
        return pole1 == n.pole1;
    }
    bool operator >(const Struktura&n) const
    {
        return pole1 > n.pole1;
    }
    bool operator <(const Struktura&n) const
    {
        return pole1 < n.pole1;
    }
};

ostream& operator <<(ostream&stream, const Struktura&m)
{
    return (stream << m.pole1 << m.pole2);
}

int main()
{
    srand(time(NULL));
    const int MAX_ORDER = 7;
    Tree<Struktura>*rbt = new Tree<Struktura>();
    //for (int o = 1; o <= MAX_ORDER; o++)
    //{
    const int n = pow(10, 1);
    //Dodawanie do drzewa
    clock_t t1 = clock();
    for (int i = 0; i < n; i++)
    {
        int flag = 0;
        while(flag==0)
        flag=rbt->AddNewElement(Struktura{});
    }
    clock_t t2 = clock();
    rbt->ToString();
    cout << "Czas wykonania operacji dodawania " << n << " elementow to: " << (double)(t2 - t1) / CLOCKS_PER_SEC << " sekundy" << endl;
    rbt->Height();
    rbt->InOrder();
    //Usuwanie drzewa
    rbt->DeleteTree(rbt->root);
    system("pause");
    //}

    /*Tree<int> *tree = new Tree<int>();
    tree->AddNewElement(55);
    tree->AddNewElement(69);
    tree->AddNewElement(62);
    tree->AddNewElement(57);
    tree->AddNewElement(35);
    tree->AddNewElement(83);
    tree->AddNewElement(72);
    tree->AddNewElement(74);
    tree->ToString();
    tree->Height();
    tree->InOrder();
    tree->SearchElement(55);
    tree->SearchElement(100);
    system("pause");*/
}