SDiZO, lab6 Drzewo AVL (usuwanie)

gistfile1.c

#include<iostream>
#include<time.h>
using namespace std;
struct avl_node
{
    avl_node *left, *right, *p;
    int key, bf;
};
 
class AVL
{
public:
    avl_node *root;
    AVL(){ root = NULL; }    
    avl_node    *rotationRR(avl_node *tmp);
    avl_node    *rotationRL(avl_node *tmp);
    avl_node    *rotationLL(avl_node *tmp);
    avl_node    *rotationLR(avl_node *tmp);
    bool        insert(avl_node *n);
    avl_node    *search(int key);
    void        walk(avl_node *x);
};

// ---------------- Rotacje ---------------- //

avl_node * AVL::rotationRR(avl_node* tmp)
{
    avl_node * tmp2 = tmp->right, * p = tmp->p;
    
    tmp->right = tmp2->left;
    if(tmp->right)
        tmp->right->p = tmp;
    tmp2->left = tmp;
    tmp2->p = p;
    tmp->p = tmp2;
    if(p) {
        if(p->left == tmp) {
            p->left = tmp2;
        } else {
            p->right = tmp2;
        }
    } else {
        root = tmp2;
    }
    
    if(tmp2->bf == -1) {
        tmp->bf = tmp2->bf = 0;
    } else {
        tmp->bf = -1;
        tmp2->bf = 1;
    }      
    return tmp2;
}

avl_node * AVL::rotationLL(avl_node* tmp)
{
    avl_node * tmp2 = tmp->left, * p = tmp->p;
    
    tmp->left = tmp2->right;
    if(tmp->left)
        tmp->left->p = tmp;
    tmp2->right = tmp;
    tmp2->p = p;
    tmp->p = tmp2;
    if(p) {
        if(p->left == tmp) {
            p->left = tmp2;
        } else {
            p->right = tmp2;
        }
    } else {
        root = tmp2;
    }
    
    if(tmp2->bf == 1) {
        tmp->bf = tmp2->bf = 0;
    } else {
        tmp->bf = -1;
        tmp2->bf = 1;
    }      
    return tmp2;
}

avl_node * AVL::rotationLR(avl_node* tmp)
{
    avl_node *tmp2 = tmp->left, *tmp3 = tmp2->right, *p = tmp->p;
    
    tmp2->right = tmp3->left;
    if(tmp2->right) {
        tmp2->right->p = tmp2;
    }
    tmp->left = tmp3->right;
    if(tmp->left) {
        tmp->left->p = tmp;
    }
    tmp3->right = tmp;
    tmp3->left = tmp2;
    tmp->p = tmp2->p = tmp3;
    tmp3->p = p;
    if(p) {
        if(p->left == tmp) {
            p->left = tmp3;
        } else {
            p->right = tmp3;
        }
    } else {
        root = tmp3;
    }
    
    tmp->bf = (tmp3->bf == 1) ? 1:0;
    tmp2->bf = (tmp3->bf == -1) ? -1:0;
    tmp3->bf = 0;
    
    return tmp3;
}

avl_node * AVL::rotationRL(avl_node* tmp)
{
    avl_node *tmp2 = tmp->right, *tmp3 = tmp2->left, *p = tmp->p;
    
    tmp2->left = tmp3->right;
    if(tmp2->left) {
        tmp2->left->p = tmp2;
    }
    tmp->right = tmp3->left;
    if(tmp->right) {
        tmp->right->p = tmp;
    }
    tmp3->left = tmp;
    tmp3->right = tmp2;
    tmp->p = tmp2->p = tmp3;
    tmp3->p = p;
    if(p) {
        if(p->left == tmp) {
            p->left = tmp3;
        } else {
            p->right = tmp3;
        }
    } else {
        root = tmp3;
    }
    
    tmp->bf = (tmp3->bf == -1) ? 1:0;
    tmp2->bf = (tmp3->bf == 1) ? -1:0;
    tmp3->bf = 0;
    
    return tmp3;
}

// ---------------- Wstawianie ---------------- //

bool AVL::insert(avl_node* n)
{
    avl_node *x = root, * tmp, *tmp2;    
    tmp = n->left = n->right = NULL;
    n->bf = 0;
    
    while(x) {
        if(x->key == n->key) {
            delete n;
            return false;
        }
        tmp = x;
        if(n->key < x->key) {
            x = x->left;
        } else {
            x = x->right;
        }
    }
    
    if(!(n->p = tmp)) {
        root = n;
        return true;
    }
    
    if(n->key < tmp->key) {
        tmp->left = n;
    } else {
        tmp->right = n;
    }
    
    if(tmp->bf) {
        tmp->bf = 0;
        return true;
    }
    
    tmp->bf = (tmp->left == n) ? 1 : -1;
    tmp2 = tmp->p;
    
    while(tmp2) {
        if(tmp2->bf) {
            break;
        }
        tmp2->bf = (tmp2->left == tmp) ? 1 : -1;
        tmp = tmp2;
        tmp2 = tmp2->p;
    }
    
    if(!tmp2) {
        return true;
    }
    
    if(tmp2->bf == 1) {
        if(tmp2->right == tmp) {
            tmp2->bf = 0;
            return true;
        }
        if(tmp->bf == -1) {
            rotationLR(tmp2);
        } else {
            rotationLL(tmp2);
        }
        return true;
    } else {
        if(tmp2->left == tmp) {
            tmp2->bf = 0;
            return true;
        }
        if(tmp->bf == 1) {
            rotationRL(tmp2);
        } else {
            rotationRR(tmp2);
            return true;
        }
    }
}

// ---------------- Szukanie ---------------- //

avl_node * AVL::search(int key)
{
    avl_node *x = root;
    
    while((x) && (x->key != key)) {
        x = (key < x->key) ? x->left : x->right;
    }
    return x;
}

// ---------------- Wyswietlanie ---------------- //

void AVL::walk(avl_node* x)
{
     cout << x->key << " : Left-> ";
    if(x->left){
        cout << x->left->key;
        cout << " ,BF " << x->left->bf;
    }
    else        
        cout << "NULL";

    cout << ", Right-> ";
    if(x->right) {
        cout << x->right->key;
        cout << " ,BF " << x->right->bf;
    }
    else         
        cout << "NULL";
    cout << endl;
    if(x->left)  
        walk(x->left);
    if(x->right) 
        walk(x->right);
}

// -- Funkcje globalne

void add(AVL *tmp, int n)
{
    avl_node *x;
    for(int i = 0; i < n; i++) {
        x = new avl_node;
        x->key = rand() % 100;
        tmp->insert(x);
    }
    tmp->walk(tmp->root);
}

void add2(AVL *tmp, int n)
{
    avl_node *x;
    x = new avl_node;
    x->key = n;
    tmp->insert(x);    
    tmp->walk(tmp->root);
}

void search(AVL *tmp, int key)
{
    if(tmp == NULL)
        cout<<"Drzewo puste"<<endl;
    else {
        if(tmp->search(key)) 
            cout << "Wezel: " << key << " jest w drzwie.\n";
      else      
          cout << "Brak podanego wezla\n";
    }
}

// ---------------- Main ---------------- //

int main()
{
    srand(time(NULL));
    AVL * tree = new AVL;
    int choice, n, key, z;
    while(z){
        cout << "\n1. Dodaj \n2. Dodaj losowe \n3. Wyswietl "
                "\n4. Usun \n5. Wyszukaj \n6. Wyjscie\n";        
        cin >> choice;
        switch(choice){
            case 1:
                cout << "Dodaj element: ";
                cin >> n;
                add2(tree, n);                
                break;
            case 2:
                cout<<"Ile elementow: ";
                cin >> n;
                add(tree, n);
                break;
            case 3:
                cout << endl;
                break;
            case 4:
                cout<<endl;
                cout <<"Jaki element chcesz usunac?: ";
                cin >> n;
                break;
                
            case 5:
                cout<<endl;
                cout <<"Jaki element chcesz znalezc?: ";
                cin >> n;
                search(tree, n);
                break;
                
            case 6:
                z = 0;
                break;
        }
    }
}