AVL.hpp

#include "Node.hpp"
#include <queue>
#include <algorithm>

enum Order { preorder = 1, inorder = 2, postorder = 3, level_by_level = 4 };
Order to_order(unsigned int order){
    return static_cast<Order>(order);
}

template<class T>
class AVL{
private:
    Node<T> *root;
    unsigned int size;
    void print(Node<T> *node, int level){
        if(!node) return;

        print(node -> right, level+1);

        for(int i = 0; i < level; i++) std::cout << " - ";
        std::cout << node -> data << ' ' << node -> height << std::endl;
        /* std::cout << node -> data << ' ' << node -> left << ' ' << node -> right << std::endl; */

        print(node -> left, level+1);
    }
    void delete_node(Node<T> *node){
        if(!node) return;
        delete_node(node -> left);
        delete_node(node -> right);
        delete node;
    }
    void left_rotate(Node<T> **node){
        Node<T> *A_ptr = *node;
        Node<T> *B_ptr = (*node) -> right;

        *node = B_ptr;
        A_ptr -> right = B_ptr -> left;
        B_ptr -> left = A_ptr;

        A_ptr -> height = 1 + std::max(
                (A_ptr -> left? A_ptr -> left -> height: 0),
                (A_ptr -> right? A_ptr -> right -> height: 0)
                );
        B_ptr -> height = 1 + std::max(
                (B_ptr -> left? B_ptr -> left -> height: 0),
                (B_ptr -> right? B_ptr -> right -> height: 0)
                );
    }
    void right_rotate(Node<T> **node){
        Node<T> *A_ptr = *node;
        Node<T> *B_ptr = (*node) -> left;

        *node = B_ptr;
        A_ptr -> left = B_ptr -> right;
        B_ptr -> right = A_ptr;

        A_ptr -> height = 1 + std::max(
                (A_ptr -> left? A_ptr -> left -> height: 0),
                (A_ptr -> right? A_ptr -> right -> height: 0)
                );
        B_ptr -> height = 1 + std::max(
                (B_ptr -> left? B_ptr -> left -> height: 0),
                (B_ptr -> right? B_ptr -> right -> height: 0)
                );
    }
    void insert(Node<T> **node, const T& data){
        if(!(*node)){
            *node = new Node<T>(data);
            return;
        }

        if(data < (*node) -> data) insert(&((*node) -> left), data);
        else insert(&((*node) -> right), data);

        (*node) -> height = 1 + std::max(
                ((*node) -> left? (*node) -> left -> height: 0),
                ((*node) -> right? (*node) -> right -> height: 0)
                );

        int bf =  ((*node) -> left? (*node) -> left -> height: 0)
                - ((*node) -> right? (*node) -> right -> height: 0);

        // si esta cargado a la izquierda y se agrego a la izquierda del hijo izquierdo
        if(1 < bf){
            if((*node) -> left -> data <= data)
                left_rotate(&(*node) -> left);
            right_rotate(node);
        }

        if(bf < -1){
            if(data < (*node) -> right -> data)
                right_rotate(&(*node) -> right);
            left_rotate(node);
        }
    }
    void remove(Node<T> **node, const T &data){
        if(!(*node))
            return;
        else if(data < (*node) -> data) remove(&((*node) -> left), data);
        else if((*node) -> data < data) remove(&((*node) -> right), data);
        else{
            if((*node) -> left || (*node) -> right){
                Node<T> *to_delete;
                if((*node) -> right){
                    Node<T> **temp = node;
                    node = &((*node) -> right);

                    while((*node) -> left)
                        node = &((*node) -> left);

                    std::swap((*node) -> data, (*temp) -> data);

                    to_delete = *node;
                    *node = (*node) -> right;
                } else {
                    to_delete = *node;
                    *node = (*node) -> left;
                }
                delete to_delete;
            } else{
                delete *node;
                *node = nullptr;
            }
            size--;
            if(!(*node)) return;
        }

        (*node) -> height = 1 + std::max(
                ((*node) -> left? (*node) -> left -> height: 0),
                ((*node) -> right? (*node) -> right -> height: 0)
                );

        int bf =  ((*node) -> left? (*node) -> left -> height: 0)
                - ((*node) -> right? (*node) -> right -> height: 0);

        // si esta cargado a la izquierda y se agrego a la izquierda del hijo izquierdo
        if(1 < bf){
            int bf_left =  ((*node) -> left -> left?  (*node) -> left -> left  -> height: 0)
                         - ((*node) -> left -> right? (*node) -> left -> right -> height: 0);
            if(bf_left < 0)
                left_rotate(&(*node) -> left);
            right_rotate(node);
        }

        if(bf < -1){
            int bf_right =  ((*node) -> right -> left?  (*node) -> right -> left  -> height : 0)
                          - ((*node) -> right -> right? (*node) -> right -> right -> height: 0);
            if(0 < bf_right)
                right_rotate(&(*node) -> right);
            left_rotate(node);
        }
    }
public:
    AVL(): root(nullptr), size(0){}
    ~AVL(){ delete_node(root); }
    void print(){
        std::cout << std::endl;
        std::cout << "Size: " << size << std::endl;
        std::cout << std::endl;
        print(root, 0);
    }
    void insert(const T& data){
        insert(&root, data);
        size++;
    }
    void remove(const T& data){
        remove(&root, data);
    }
    bool find(const T& data) const {
        Node<T> *node = root;

        while(node && node -> data != data)
            node = (data < node -> data ? node -> left: node -> right);

        return node;
    }
};