package PraktikumBab10;

public class AVLTree {
    Node akar;
    int getTinggi(Node N) {
        return (N != null) ? N.tinggi : 0;
    }
    // Fungsi untuk memutar node melalui y
    // Lihat diagram diatas
    Node putarKanan(Node y) {
        Node x = y.nodeKiri;
        Node T2 = x.nodeKanan;
        // Melakukan putaran
        x.nodeKanan = y;
        y.nodeKiri = T2;
        // Update tinggi
        y.tinggi = Math.max(getTinggi(y.nodeKiri), getTinggi(y.nodeKanan)) + 1;
        x.tinggi = Math.max(getTinggi(x.nodeKiri), getTinggi(x.nodeKanan)) + 1;
        // hasilkan pasangan node baru
        return x;
    }
    // Fungsi untuk memutar node melalui x
    // Lihat diagram diatas
    Node putarKiri(Node x) {
        Node y = x.nodeKanan;
        Node T2 = y.nodeKiri;
        // Melakukan putaran
        y.nodeKiri = x;
        x.nodeKanan = T2;
        // Update tinggi
        x.tinggi = Math.max(getTinggi(x.nodeKiri), getTinggi(x.nodeKanan)) + 1;
        y.tinggi = Math.max(getTinggi(y.nodeKiri), getTinggi(y.nodeKanan)) + 1;
        // hasilkan pasangan node baru
        return y;
    }
    // Dapatkan nilai seimbang dari node N
    int getBalance(Node N) {
        return (N!=null) ? getTinggi(N.nodeKiri) - getTinggi(N.nodeKanan) : 0;
    }
    Node insert(Node node, int data) {
        /* 1. Penambahan Node pada BST biasa */
        if (node == null) {
            return (new Node(data));
        }
        if (data < node.data) {
            node.nodeKiri = insert(node.nodeKiri, data);
        } else if (data > node.data) {
            node.nodeKanan = insert(node.nodeKanan, data);
        } else // Duplicate datas not allowed
        {
            return node;
        }
        /* 2. Update tinggi pada ancestor node */
        node.tinggi = 1 + Math.max(getTinggi(node.nodeKiri), getTinggi(node.nodeKanan));
        /* 3. Melakukan keseimbangan pada melalui nilai
        ancestor untuk mengecek apakah node tidak
        seimbang*/
        Node result = balance(node, data);
        // hasilkan pasangan node baru
        return result;
    }
    Node balance(Node node, int data) {
        int balance = getBalance(node);
        // Apabila kondisi tidak seimbang maka terjadi rotasi
        // Kondisi putar kanan
        if (balance > 1 && data < node.nodeKiri.data) {
            return putarKanan(node);
        }
        // Kondisi putar kiri
        else if (balance < -1 && data > node.nodeKanan.data) {
            return putarKiri(node);
        }
        // Kondisi putar kiri kanan
        else if (balance > 1 && data > node.nodeKiri.data) {
            node.nodeKiri = putarKiri(node.nodeKiri);
            return putarKanan(node);
        }
        // Kondisi putar kanan kiri
        else if (balance < -1 && data < node.nodeKanan.data) {
            node.nodeKanan = putarKanan(node.nodeKanan);
            return putarKiri(node);
        }
        // Kondisi tidak berubah sama sekali
        else {
            return node;
        }
    }
    void inOrder(Node node) {
        if (node != null) {
            inOrder(node.nodeKiri);
            System.out.print(node.data + " ");
            inOrder(node.nodeKanan);
        }
    }
    void preOrder(Node node) {
        if (node != null) {
            System.out.print(node.data + " ");
            preOrder(node.nodeKiri);
            preOrder(node.nodeKanan);
        }
    }

    public boolean pencarian(Node node, int data){
        if(node != null){
            if(node.data == data){
                return true;
            }else{
                /*if(node.nodeKiri != null){
                    return pencarian(node.nodeKiri, data);
                }

                if(node.nodeKanan != null){
                    return pencarian(node.nodeKanan, data);
                }*/
                return pencarian(node.nodeKiri, data) || pencarian(node.nodeKanan, data);
            }
        }else{
            return false;
        }
    }

    public void pencarian(int data){
        /*return pencarian(akar, data);*/
        if(pencarian(akar, data))
            System.out.println("Data " + data + " ditemukan");
        else
            System.out.println("Data " + data + " tidak ditemukan");
    }

    Node minValueNode(Node node) {
        Node current = node;

        while (current.nodeKiri != null)
            current = current.nodeKiri;

        return current;
    }

    public int max(int x, int y){
        return (x > y)? x : y;
    }

    public Node remove(Node node, int data){
        if(node != null){
            if(data < node.data){
                node.nodeKiri = remove(node.nodeKiri, data);
            }else if(data > node.data){
                node.nodeKanan = remove(node.nodeKanan, data);
            }else{
                if(node.nodeKiri == null || node.nodeKanan == null){
                    Node temp = node.nodeKiri == null? node.nodeKanan : node.nodeKiri;

                    if(temp == null){
                        temp = node;
                        node = null;
                    }else{
                        node = temp;
                    }
                }else {
                    Node temp = minValueNode(node.nodeKanan);

                    node.data = temp.data;

                    node.nodeKanan = remove(node.nodeKanan, temp.data);
                }
            }

            if(node == null)
                return node;

            node.tinggi = max(getTinggi(node.nodeKiri), getTinggi(node.nodeKanan)) + 1;

            if(getBalance(node) > 1 && getBalance(node.nodeKiri) >= 0){
                return putarKanan(node);
            }

            if(getBalance(node) > 1 && getBalance(node.nodeKiri) < 0){
                node.nodeKiri = putarKiri(node.nodeKiri);
                return putarKanan(node);
            }

            if(getBalance(node) < -1 && getBalance(node.nodeKanan) <= 0){
                return putarKiri(node);
            }

            if(getBalance(node) < -1 && getBalance(node.nodeKanan) > 0){
                node.nodeKanan = putarKanan(node.nodeKanan);
                return putarKiri(node);
            }
        }

        return node;
    }

    public int nodeLevel(int n){
        if(n == 0)
            return 1;
        else if(n == 1)
            return 2;
        else if(n == 2)
            return 4;
        else
            return 1 + nodeLevel(n-1) + nodeLevel(n-2);
    }
}