Drzewo

//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>;
            //0 to czerwony, 1 to czarny;
            root->color = 1;
            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 = current->left;
                        //current->data = data;
                        current->left->data = data;
                        current->left->parent = current;
                        //if (current->left->parent->color == 1)
                            //current->left->color = 0;
                        counter += 1;
                        current = current->left;
                        return 1;
                        //return current;
                        //break;
                    }
                    else
                    {
                        current = current->left;
                    }
                }
                if (data > current->data)
                {
                    //w prawo
                    if (current->right == nullptr)
                    {
                        current->right = new Node<T>;
                        //current = current->right;
                        //current->data = data;
                        current->right->data = data;
                        current->right->parent = current;
                        //if (current->right->parent->color == 1)
                            //current->right->color = 0;
                        counter += 1;
                        current = current->right;
                        return 1;
                        //return current;
                        //break;
                    }
                    else
                    {
                        current = current->right;
                    }
                }
                if (data == current->data)
                {
                    //break;
                    //return nullptr;
                    return 0;
                }
            }
        }
    }
    void AddNewElement(const T&data)
    {
        //0 to czerwony, 1 to czarny;
        /*Node<T>*temp=nullptr;
        while(temp==nullptr)
        temp=Insert(data);*/
        int flag = 0;
        while (flag==0)
        flag=Insert(data);
        Node<T>*temp = ReturnFunction(data);
        temp->color = 0;
        while (temp != root && temp->parent->color == 0)
        {
            if (temp->parent == temp->parent->parent->left)
            {
                Node<T>*stryj = temp->parent->parent->right; //stryj temp'a
                //POPRAWIĆ
                //if (stryj == nullptr)
                //{
                    //RotateRight(temp, temp->parent);
                //}
                //else
                if (stryj->color == 0)
                {
                    temp->parent->color = 1;
                    stryj->color = 1;
                    temp->parent->parent->color = 0;
                    temp = temp->parent->parent; //wedrowka o 2 poziomy wyzej
                }
                else //stryj jest czarny
                {
                    if (temp == temp->parent->right) //temp jest prawym potomkiem
                    {
                        RotateLeft(temp->parent, temp);
                        temp = temp->parent;
                    }
                    temp->parent->color = 1;
                    temp->parent->parent = 0;
                    RotateRight(temp, temp->parent);
                }
            }
            else //ojciec x jest prawym potomkiem dziadka
            {
                Node<T>*stryj = temp->parent->parent->left; //stryj temp'a
                //POPRAWIĆ
                //if (stryj == nullptr)
                //{
                    //RotateLeft(temp->parent, temp);
                //}
                //else
                if (stryj->color == 0)
                {
                    temp->parent->color = 1;
                    stryj->color = 1;
                    temp->parent->parent->color = 0;
                    temp = temp->parent->parent; //wedrowka o 2 poziomy wyzej
                }
                else //stryj jest czarny
                {
                    if (temp == temp->parent->left) //temp jest lewym potomkiem
                    {
                        RotateRight(temp, temp->parent);
                        temp = temp->parent;
                    }
                    temp->parent->color = 1;
                    temp->parent->parent->color = 0;
                    RotateLeft(temp->parent, temp);
                }
            }
        }
        root->color = 1; //korzen zawsze jest czarny
    }
    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 TymSobieSprawdzam()
    {
        Node<T> *temp;
        temp = root;
        cout << "Drzewo:" << endl;
        cout << "       " << temp->data << endl;
        cout << "   " << temp->left->data << "      " << temp->right->data << endl;
        cout << temp->left->left->data << "     " << temp->left->right->data << " " << temp->right->left->data << "     " << temp->right->right->data << endl;
    }
    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>*X, Node<T> *Y)
    {
        /*if (X->right == Y)
        {
            if (X->parent != nullptr)
            {
                Y->parent = X->parent;
                X->parent = Y;
            }
            else
            {
                Y->parent = nullptr;
                X->parent = Y;
            }
            if (X == root)
                root = Y;
            if (Y->left != nullptr)
            {
                X->right = Y->left;
                Y->left = X;
            }
            else
            {
                X->right = nullptr;
                Y->left = X;
            }
        }
        else
            cout << "Wezel Y nie jest prawym dzieckiem wezla X" << endl;*/
        if (Y->left != nullptr)
            X->right = Y->left;
        else
            X->right = nullptr;
        if (Y->left != nullptr)
            Y->left->parent = X;
        Y->left = X;
        X->parent = Y;
        if (X == root)
            root = Y;
    }
    void RotateRight(Node<T>*X, Node<T> *Y)
    {
        /*if (Y->left == X)
        {
            if (Y == root)
                root = X;
            if (Y->parent != nullptr)
            {
                X->parent = Y->parent;
                Y->parent = X;
            }
            else
            {
                X->parent = nullptr;
                Y->parent = X;
            }
            if (Y == root)
                root = X;
            if (X->right != nullptr)
            {
                Y->left = X->right;
                X->right = Y;
            }
            else
            {
                Y->left = nullptr;
                X->right = Y;
            }
        }
        else
            cout << "Wezel X nie jest lewym dzieckiem wezla Y" << endl;*/
        if (X->right != nullptr)
            Y->left = X->right;
        else
            Y->left = nullptr;
        if (X->right != nullptr)
            X->right->parent = Y;
        X->right = Y;
        Y->parent = X;
        if (Y == root)
            root = X;
    }
};

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; //Flaga powtarzajacego sie elementu 0-powtarza sie, wiec element nie zostal dodany 1-nie powtarza sie, wiec zostal dodany
            //while(flag==0)
            //flag=rbt->AddNewElement(Struktura{});
            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;
        //Usuwanie drzewa
        rbt->DeleteTree(rbt->root);
        system("pause");
    //}*/



    Tree<int> *tree = new Tree<int>();
    //tree->AddNewElement(4);
    //tree->AddNewElement(2);
    //tree->AddNewElement(6);
    //tree->AddNewElement(1);
    //tree->AddNewElement(3);
    //tree->AddNewElement(5);
    //tree->AddNewElement(7);

    tree->AddNewElement(6);
    tree->AddNewElement(7);
    tree->AddNewElement(8);

    //tree->TymSobieSprawdzam();
    //Node<int> *Sprawdzenie = tree->SearchElement(7);
    //cout << endl;
    //tree->ToString();
    //tree->PreOrder();
    //tree->InOrder();
    system("pause");
    //tree->Height();
}