Lucas' Blog

Bom galera.. vou postar para vcs o código de Arvore AVL que fiz hj… me baseei no código de arvore binária que eu jah tinha feito… seguem então os codigos

AVL.h

#include 
#include 
#ifndef AVL
#define	AVL

using namespace std;

namespace ED {

    template 
    class AVLTree {
    public:
        AVLTree();
        ~AVLTree();
        //metodos principais
        void insere(Tipo el);
        void percursoEmOrdem();
        void desaloca();
        int tamanho();
        int altura();

    private:
        class Celula {
        public:
            Tipo el;
            Celula *esq, *dir;
            char h;
            char b;
        };
        int height(Celula *x);
        void inorder_Walk(Celula *x);
        void removeCels(Celula *x);
        void balanceia(Celula *&x);
        void atualiza(Celula *&x);
        void rotateLeft(Celula *&x);
        void rotateRight(Celula *&x);
        void desaloca(Celula *x);
        void insere(Celula* &x, Tipo &el);
        Celula *T;
        unsigned int nelem, h;
    };

    //Construtor
    template 
    AVLTree::AVLTree() {
        T = new Celula;
        T->esq = NULL;
        T->dir = NULL;
        nelem = 0;
    }

    //Destrutor
    template 
    AVLTree::~AVLTree() {
        this->desaloca(T);
    }

    //Desaloca a arvore
    template 
    void AVLTree::desaloca() {
        desaloca(T);
    }

    //Desaloca a célula
    template 
    void AVLTree::desaloca(Celula *x) {
            if (x == NULL)
                return;
            else{
              desaloca(x->esq);
              desaloca(x->dir);
              delete x;
              atualiza(x);
              balanceia(x);
            }
    }

    //Balanceamento
    template 
    void AVLTree::balanceia(Celula *&x) {
         if (x->b == 2) {
            if (x->esq->b == -1) rotateLeft(x->esq);
               rotateRight(x);
         }
         else if (x->b == -2) {
              if (x->dir->b == 1) rotateRight(x->dir);
                 rotateLeft(x);
         }
     }

    //Atualização numero altura e balanceamento
    template 
    void AVLTree::atualiza(Celula *&x) {
         unsigned char hesq = x->esq? (x->esq->h) : 0;
         unsigned char hdir = x->dir? (x->dir->h) : 0;
         x->b = hesq - hdir;
         x->h = 1 + (hesq > hdir? hesq : hdir);
    }   

    //Rotação Direita
    template 
    void AVLTree::rotateRight(Celula *&x) {
         Celula *aux = x;
         x = x->esq;
         aux->esq = x->dir;
         x->dir = aux;
         atualiza(aux);
         atualiza(x);
    }

    //Rotação Esquerda
    template 
    void AVLTree::rotateLeft(Celula *&x) {
         Celula *aux = x;
         x = x->dir;
         aux->dir = x->esq;
         x->esq = aux;
         atualiza(aux);
         atualiza(x);
    }

    //Inserção
    template 
    void AVLTree::insere(Tipo el) {
      insere(T, el);
    }

    template 
    void AVLTree::insere(Celula* &x, Tipo &el) {
        if (!x) {
            x = new Celula();
            x->el = el;
            nelem++;
        } else {
            if (x->el >= el) insere(x->esq, el);
            else insere(x->dir, el);
            atualiza(x);
            balanceia(x);
        }
    }

    //Altura árvore
    template
    int AVLTree::altura() {
        return height(T);
    }

    //Altura célula
    template
    int AVLTree::height(Celula *x) {
        int esq, dir;
        if (x == NULL) return 0;
        esq = height(x->esq);
        dir = height(x->dir);
        if (esq > dir)
            return esq + 1;
        else
            return dir + 1;
    }

    //Número de elementos arvore
    template 
    int AVLTree::tamanho() {
        return (nelem);
    }

    //Remanescência BSTree ordenação
    template
    void AVLTree::inorder_Walk(Celula *x) {
        if (x == NULL) return;
        inorder_Walk(x->esq);
        cout << x->el << endl;
        inorder_Walk(x->dir);
    }

    template
    void AVLTree::percursoEmOrdem() {
        this->inorder_Walk(T);
    }

}

#endif

e o main.cpp (que foi o exercicio proposto pelo professor

#include 
#include 
#include "AVL.h"

#define T int

using namespace std;
using namespace ED;

int main(int argc, char** argv) {

    cout << "Arvore AVL."< *avl;
    avl = new AVLTree();

    for(int c=0; c<1023; c++){
      avl->insere(rand());
    }
    cout << "10"<< avl->altura() <desaloca();

    avl = new AVLTree();

    for(int c=0; c<32767; c++){
      avl->insere(rand());
    }
    cout << "15"<< avl->altura() <desaloca();

    avl = new AVLTree();

    for(int c=0; c<1048575; c++){
      avl->insere(rand());
    }
    cout << "20"<< avl->altura() <desaloca();

    avl = new AVLTree();

    for(int c=0; c<4194303; c++){
      avl->insere(rand());
    }
    cout << "25"<< avl->altura() <desaloca();

}