RBtree

// RBTree.cpp : Defines the entry point for the console application.
//




// Drzewo RB

#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <string>

using namespace std;



struct node {
    node *up;
    node *left;
    node *right;
    int key;
    char color;
};

void loadFile(node *& root, node *&sentinel);


void printBT(string sp, string sn, node * root, node *sentinel);
node * minBST(node * root);
node * maxBST(node * root);
node * findBST(node * root, int value);
void inorder(node * root);
void saveFile(node *root);
void RBinsert(node *&root, int value, node *sentinel);
void RBfixup(node *&root, node *x);
node *createRB(node *sentinel,int value );
void deleteNode(node **root, int value);
void removeBST(node * & root, int value);
void Rrot(node *&root, node *&X);
void Lrot(node *&root, node *&X);

int _tmain(int argc, _TCHAR* argv[])
{

    node *root = new node;
    root = NULL;
    node *sentinel=new node;
    node *temp = new node;
    sentinel->color='B';
    sentinel->key=80085;




    int option, value;
    do {
        cout << "1. Add NOde" << endl;
        cout << "2. Load File" << endl;
        cout << "3. Store File" << endl;
        cout << "4. Minimum" << endl;
        cout << "5. Maximum" << endl;
        cout << "6. Find value" << endl;
        cout << "7. InOrder " << endl;
        cout << "10. Print Tree" << endl;
        cout << "\nPodaj opcje: ";
        cin >> option;


        switch (option) {
        case 1:
            cout << "Podaj liczbe: " << endl;
            cin >> value;
            RBinsert(root,  value,  sentinel);
            cout << "root " << root << " wartosc " << root->key;
            break;
        case 2:
            loadFile(root,sentinel);
            break;
        case 3:
            saveFile(root);
            break;
        case 4:
            cout << "Minimalny element to" << minBST(root)->key << endl;
            break;
        case 5:
            cout << "Maksymalny element to" << maxBST(root)->key << endl;
            break;
        case 6:
            cout << "Podaj liczbe: " << endl;
            cin >> value;
            temp = findBST(root, value);
            if (temp != NULL) {
                cout << "Znaleziony element  " << temp->key << " pod adresem " << temp << endl;
            }
            else cout << "Nie ma takiego elementu";
            break;
        case 7:
            inorder(root);
            break;
        case 8:
            cout << "Podaj liczbe: " << endl;
            cin >> value;
            removeBST(root, value);
            break;
        case 10:
             printBT(" "," " , root,sentinel);
             break;

        }

        cout << "\n\n";

    } while (option != 0);


    return 0;
}

void RBinsert(node *&root, int value, node *sentinel)
{
        if(root==NULL)
    {
        root=new node;
        root->key=value;
        root->up=sentinel;
        root->left=sentinel;
        root->right=sentinel;
    }
    else
    {
        node *temp=root;
        node *par =new node;
        while(temp!=root->up)
        {
            par=temp;
            if(value<temp->key)
                temp=temp->left;
            else
                temp=temp->right;
        }

        node *newPtr=new node;

        if(par->key<value)
        {
            par->right=newPtr;
        }
        else
        {
            par->left=newPtr;

        }
        newPtr->key=value;
        newPtr->left=root->up;
        newPtr->right=root->up;
        newPtr->up=par;
        newPtr->color='R';

       // RBfixup(root,newPtr);
    }
}


void RBfixup(node *&root, node *z)
{
    node *Y;
    while(z->up->color=='R'){
        if (z->up==z->up->up->left){
            Y=z->up->up->left;
            if(Y->color=='R'){
                z->up->color='B';
                Y->color='B';
                z->up->up->color='R';
                z=z->up->up;
            }
            else if(z==z->up->right ){
                z=z->up;
                Lrot(root,z);
                }
            z->up->color='B';
            z->up->up->color='R';
            Rrot(root,z->up->up);
        }else if(z->up==z->up->up->right){
            Y=z->up->up->right;
            if(Y->color=='R'){
                z->up->color='B';
                Y->color='B';
                z->up->up->color='R';
                z=z->up->up;
            }
            else if(z==z->up->left ){
                z=z->up;
                Rrot(root,z);
                }
            z->up->color='B';
            z->up->up->color='R';
            Lrot(root,z->up->up);
        }
    }

}
void loadFile(node *&root,node *&sentinel) {
    int idx;
    fstream plik;
    plik.open("RBdata.txt", ios::in);
    if (plik) {
        while (!plik.eof()) {
            plik >> idx;
            RBinsert(root,idx, sentinel);
        }
        cout << "Plik wczytany" << endl;
    }
    plik.close();
}

// rekurencyjny zapis do pliku IN ORDER
void saveFile(node *root) {
    ofstream plik;
    plik.open("result.txt", ios::out | ios::app);

    if (root->left)
        saveFile(root->left);

    plik << root->key << " ";

    if (root->right)
        saveFile(root->right);

    plik.close();
}

node * minBST(node * root) {
    while (root->left) {
        root = root->left;
    }
    return root;
}

node * maxBST(node * root) {
    while (root->right) {
        root = root->right;
    }
    return root;
}

node * findBST(node * root, int value)
{
    while (root) {
        if (value == root->key)
            return root;
        else if (value < root->key)
            root = root->left;
        else if (value > root->key)
            root = root->right;
    }
    return NULL;
}
 node *createRB(node *sentinel,int value ) {
     node *newNode = new node;
     newNode->up = sentinel;
     newNode->left = sentinel;
     newNode->right = sentinel;
     newNode->key = value;
     newNode->color='R';
     return newNode;
}

void printBT(string sp, string sn, node * root, node *sentinel)
{
    string s;
    string cr, cl, cp;
    cr = cl = cp = "  ";
    cr[0] = 218; cr[1] = 196;
    cl[0] = 192; cl[1] = 196;
    cp[0] = 179;

    if (root!=sentinel)
    {
        s = sp;
        if (sn == cr) s[s.length() - 2] = ' ';
        printBT(s + cp, cr, root->right,sentinel);

        s = s.substr(0, sp.length() - 2);
        cout << s << sn << root->key<<":"<< root->color<< endl;

        s = sp;
        if (sn == cl) s[s.length() - 2] = ' ';
        printBT(s + cp, cl, root->left,sentinel);
    }
}

void inorder(node * root) {
    if (root->left)
        inorder(root->left);
    cout << root->key << " ";
    if (root->right)
        inorder(root->right);

}

void deleteNode(node **root, int value) {
    node *A = findBST(*root,value);
    node *B, *C;
    if (A->right == NULL && A->left == NULL) {
        if (A== A->up->left) A->up->left = NULL;
        else A->up->right = NULL;
        delete A;
    }
    else if(!A->left != !A->right){

        if (A->left) B = A->left;
        else B = A->right;

        B->up = A->up;
        if (!A->up) *root = B;

        if (A == A->up->left) A->up->left = B;
        else A->up->right = B;
        delete A;
    }
    else {

        B = minBST(A->right);

        if (B->left) C = B->left;
        else C = B->right;

        B->up = C->up;
        if (!B->up) *root = C;

        if (B == B->up->left) B->up->left = C;
        else B->up->right = C;

        if (B != A) A->key = B->key;

        delete B;
    }
}

void removeBST(node * & root, int value)
{
    node *A = findBST(root, value);
    node * B, *C;

    if (A)
    {


        //Jesli A ma obu potomków to B= nastepnik A ( tu zawsze min od A->right)
        //jak ma jednego lub mniej to B=A

        if (A->left && A->right) B = minBST(A->right);
        else B = A;

        // C wskazuje syna B lub NULL
        if (B->left) C = B->left;
        else C = B->right;

        // Jeśli syn B istnieje, to zastąpi C w drzewie dowiąznie up
        if (C) C->up = B->up;

        // B zostaje zastąpione przez C w drzewie
        if (!B->up) root = C;
        else if (B == B->up->left) B->up->left = C;
            else  B->up->right = C;

        // Jeśli B jest następnikiem A, to kopiujemy dane
        if (B != A) A->key = B->key;

        delete B;

    }
}

void Lrot(node *&root, node *&X){
    node *Y = X->right;
    X->right = Y->left;

    if(Y->left) Y->left->up=X;
    Y->up = X->up;
    if(!X->up)  root = Y;
    else if (X==X->up->left) X->up->left= Y;
        else X->up->right=Y;
    Y->left = X;
    X->up = Y;
}

void Rrot(node *&root, node *&X){
    node *Y = X->left;
    X->left = Y->right;

    if(Y->right) Y->right->up=X;
    Y->up = X->up;
    if(!X->up)  root = Y;
    else if (X==X->up->right) X->up->right= Y;
        else X->up->left=Y;
    Y->right = X;
    X->up = Y;
}