SDiZO, lab5 Drzewo DSW + Splay

gistfile1.c

#include<iostream>
#include<time.h>
#include<math.h>
using namespace std;
struct tree{
    int key;
    tree *left, *right;
};
tree *root;
 
class Binary_tree{
    public:
        Binary_tree();
        void insert1(int);
        tree *insert2(tree *, tree *);
        void delete_tree(int);
        void inorder(tree *);
        void search(int key);
        
        tree * search2(int key);       
        void promote(int key);
        
        void walk(tree *);
        void rotate_right(tree *grand_father,tree *parent,tree *child);
        void rotate_left(tree *grand_father,tree *parent,tree *child);
        void make_intermediate_list(void); 
        void make_perfect_tree(long int N);
        void make_r_right(int key);
        void make_r_left(int key);
        
        static int ii;
};

Binary_tree bt;

int Binary_tree::ii = 1;

Binary_tree::Binary_tree()
{
    root = NULL;
}

tree * Binary_tree::insert2(tree *temp, tree *newnode)
{
    if(temp == NULL) {
        temp = newnode;
    } 
    else if(temp->key == newnode->key) {
        return temp;
    }
    else if(temp->key < newnode->key) {
        insert2(temp->right, newnode);
        if(temp->right == NULL) {            
             ii++;
            temp->right = newnode;
        }
    } else {
        insert2(temp->left, newnode);
        if(temp->left == NULL) {
            ii++;
            temp->left = newnode;
        }
    }    
    return temp;
}

void Binary_tree::search(int key)
{
    tree *temp = root, *parent;
    if(temp == NULL)
        cout<<"Drzewo puste"<<endl;
    else {
        while(temp != NULL) {
            if(temp->key == key) {
                cout << "Szukany element: " << temp->key << endl;
                return;
            }
            if(temp->key < key) {
                temp = temp->right;
            } else {
                temp = temp->left;
            }
        }
        cout << "Brak elementu\n";
    }
}

void Binary_tree::delete_tree(int key)
{
    tree *temp = root,*parent = root, *marker;
    if(temp == NULL)
        cout<<"Drzewo puste"<<endl;
    else {
        while(temp != NULL && temp->key != key) {
            parent = temp;
            if(temp->key < key) {
                temp = temp->right;
            } else {
                temp = temp->left;
            }
        }
    }
    
    marker = temp;
    
    if(temp == NULL)
        cout<<"Brak wezla";
    
    else if(temp == root) {
        if(temp->right == NULL && temp->left == NULL) {
            root = NULL;
        } else if(temp->left==NULL) {
            root = temp->right;
        } else if(temp->right == NULL) {
            root = temp->left;
        } else {
            tree *temp1;
            temp1 = temp->right;
            while(temp1->left != NULL) {
                temp = temp1;
                temp1 = temp1->left;
            } if(temp1 != temp->right) {
                temp->left = temp1->right;
                temp1->right = root->right;
            }
            temp1->left = root->left;
            root = temp1;
        }
    } else {
        if(temp->right == NULL && temp->left == NULL){
            if(parent->right == temp)
                parent->right = NULL;
            else
                parent->left = NULL;
        }
        else if(temp->left == NULL){
            if(parent->right == temp)
                parent->right = temp->right;
            else
                parent->left = temp->right;
        }
        else if(temp->right == NULL){
            if(parent->right == temp)
                parent->right = temp->left;
            else
                parent->left = temp->left;
        } else {
            tree *temp1;
            parent = temp;
            temp1 = temp->right;
            while(temp1->left != NULL){
                parent = temp1;
                temp1 = temp1->left;
            }
            if(temp1 != temp->right){
                temp->left = temp1->right;
                temp1->right = parent->right;
            }
            temp1->left = parent->left;
            parent = temp1;
        }
    }
    delete marker;
}

void Binary_tree::insert1(int n)
{
    tree *temp = root, *newnode;
    newnode = new tree;
    newnode->left = NULL;
    newnode->right = NULL;
    newnode->key = n;
    root = insert2(temp, newnode);
}

void Binary_tree::walk(tree * x)
{
  cout << x->key << " : Left-> ";
  if(x->left) 
      cout << x->left->key;
  else        
      cout << "NIL";
  cout << ", Right-> ";
  if(x->right) 
      cout << x->right->key;
  else         
      cout << "NIL";
  cout << endl;
  if(x->left)  
      walk(x->left);
  if(x->right) 
      walk(x->right);
}

void Binary_tree::inorder(tree *t)
{
    if(root == NULL) {
        cout << "Drzewo puste!\n";
    } else {
        if(t != NULL) {
            inorder(t->left);
            cout << t->key << " ";
            inorder(t->right);
        }
    }
}

void Binary_tree::rotate_right(tree* grand_father, tree* parent, tree* child)
{
    tree *temp;
    
    if(grand_father != NULL) {
        if(grand_father->right == parent)
            grand_father->right = child;
        else
            grand_father->left = child;
    } else {
        root = child;
    }
    temp = child->right;
    child->right = parent;
    parent->left = temp;
}

void Binary_tree::rotate_left(tree* grand_father, tree* parent, tree* child)
{
    tree *temp;
    
    if(grand_father != NULL) {
        if(grand_father->left == parent)
            grand_father->left = child;
        else
            grand_father->right = child;
    } else {
        root = child;
    }
    temp = child->left;
    child->left = parent;
    parent->right = temp;
}

tree * Binary_tree::search2(int key) // Wyszukiwanie rodzica
{
    tree *temp = root, *parent, *g_father;
    if(temp == NULL)
        cout<<"Drzewo puste"<<endl;
    
    if(temp->key == key)
        return NULL;
    
    else {
        while(temp != NULL) {
            if(temp->key == key) {
                return parent;
            }
            if(temp->key < key) {
                parent = temp;
                temp = temp->right;
            } else {
                parent = temp;
                temp = temp->left;
            }
        }
        return NULL;
        cout << "Brak elementu\n";
    }
}
////////////////////////////////////////////////////////////////
void Binary_tree::make_r_left(int key)
{
    tree *temp = root, *parent, *grand_father;
    
    parent = search2(key);
    if(parent != NULL)
                grand_father = search2(parent->key);
        else
            return;
    
    if(parent->key < key)
        rotate_left(grand_father, parent, parent->right);
    else
        cout << "Blad\n";
}

void Binary_tree::make_r_right(int key)
{
    tree *parent, *grand_father;
    
    parent = search2(key);
    if(parent != NULL)
                grand_father = search2(parent->key);
        else
            return;
    
    if(parent->key > key)
        rotate_right(grand_father, parent, parent->left);
    else
        cout << "Blad\n";
}
////////////////////////////////////////////////////////////////
void Binary_tree::promote(int key)
{
    tree *parent, *grand_father;
    
    while(1) {
        parent = search2(key);
        if(parent != NULL)
            grand_father = search2(parent->key);
        else
            break;

        if(parent->key < key) {
            rotate_left(grand_father, parent, parent->right);
        } else {
            rotate_right(grand_father, parent, parent->left);
        }            
    }
}

void Binary_tree::make_intermediate_list(void)
{
    tree *temp, *temp2, *grand_father;
    
    grand_father = NULL;
    temp = root;
    while(temp != NULL) {
        if(temp->left != NULL) {
            temp2 = temp->left;
            rotate_right(grand_father, temp, temp->left);
            temp = temp2;
        } else {
            grand_father = temp;
            temp = temp->right;
        }
    }
}

void Binary_tree::make_perfect_tree(long int N)
{
    long int i, m;
    tree *temp, *temp2, *grand_father;
    grand_father = NULL;
    temp = root;
    m = (long int)pow(2, (long int)(log(N)/log(2))) - 1;
    
    for(i = 0; i < (N - m); i++) {
        temp2 = temp->right;
        if(temp2 != NULL) {
            rotate_left(grand_father, temp, temp->right);
            grand_father = temp2;
            temp = temp2->right;
        }
    }
    
    while(m > 1) {
        m = m / 2;
        grand_father = NULL;
        temp = root;
        for(i = 0; i < m; i++) {
            temp2 = temp->right;
            rotate_left(grand_father, temp, temp->right);
            grand_father = temp2;
            temp = temp2->right;
        }
    }
}

void insert3(int n)
{    
    for(int i = 0; i < n; i = Binary_tree::ii) {
        int z = rand() % 200;
        bt.insert1(z);
    }
}

int main()
{
    srand(time(NULL));
    int choice, n, key, z;
    while(z){
        cout << "\n1. Dodaj jeden wezel \n2. Dodaj losowe \n3. Inorder "
                "\n4. Usun \n5. Pokaz strukture \n6. DSW \n7. Wyszukaj \n!8. Wyjscie \n\n9. Promocja \n10. Rotacja w lewo \n11. Rotacja w prawo \n";        
        cin >> choice;
        switch(choice){
            case 1:
                cout << "Dodaj element: ";
                cin >> n;
                bt.insert1(n);
                bt.promote(n);
                break;
            case 2:
                cout<<"Ile elementow: ";
                cin >> n;
                insert3(n);
                break;
            case 3:
                cout << endl;
                bt.inorder(root);
                break;
            case 4:
                cout<<endl;
                cout <<"Jaki element chcesz usunac?: ";
                cin >> n;
                bt.promote(n);
                bt.delete_tree(n);
                break;
            case 5:
                cout << endl;
                bt.walk(root);
                break;
            case 6:
                cout << endl;
                bt.make_intermediate_list();
                bt.make_perfect_tree(Binary_tree::ii);
                break;
                
            case 7:
                cout<<endl;
                cout <<"Jaki element chcesz znalezc?: ";
                cin >> n;
                bt.search(n);
                bt.promote(n);
                break;
                
            case 8:
                z = 0;
                break;
                
            case 9:
                cout << endl;
                cout <<"Jaki element chcesz promowac?: ";
                cin >> n;
                bt.promote(n);
                break;
                
            case 10:
                cout << endl;
                cout <<"Jaki element chcesz rotowac?: ";
                cin >> n;
                bt.make_r_left(n);
                break;
                
            case 11:
                cout << endl;
                cout <<"Jaki element chcesz rotowac?: ";
                cin >> n;
                bt.make_r_right(n);
                break;
        }
    }
}