ALGORITMA & STRUKTUR DATA BAB 10 : ADT AVL TREE

Laporan Praktikum Algoritma & Struktur Data Bab 10 Fakultas Ilmu Komputer Universitas Brawijaya 2017/2018

Soal :

     1.       Tambahkan method untuk melakukan pencarian dan penghapusan node pada pohon AVL

   2.     Tambahkan method untuk menampilkan node yang mungkin menghasilkan jumlah node paling minimal dengan nilai inputan level ditentukan oleh user.

Contoh input 11 :

            Masukkan level node: 1

Hasil output 1:

            Jumlah minimal node: 2

            Urutan nilai node yang mungkin: 2 1

Contoh input 2:

            Masukkan level node: 4

Hasil output 2:

            Jumlah minimal node: 12

            Urutan nilai node yang mungkin: 38 12 99 6 70 77 41 4 33 79 56 47

Contoh input 3:

            Masukkan level node: 5

Hasil output 3:

            Jumlah minimal node: 20

            Urutan nilai node yang mungkin: 82 36 43 3 50 27 86 15 57 58 61 64 56 96 63 23 84 93 81 6

Source code :
Soal no.1 & 2

package asdmodul4;

import static java.lang.Integer.max;
import java.util.Random;
import java.util.Scanner;

class nodeAVL {

    int data, tinggi;
    nodeAVL nodeKiri, nodeKanan;

    nodeAVL(int d) {
        data = d;
        tinggi = 1;
    }
}

public class Bab10AVL {

    nodeAVL akar;

    int getTinggi(nodeAVL N) {
        return (N != null) ? N.tinggi : 0;
    }

    // Fungsi untuk memutar node melalui y 
    // Lihat diagram diatas 
    nodeAVL putarKanan(nodeAVL y) {
        nodeAVL x = y.nodeKiri;
        nodeAVL 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 
    nodeAVL putarKiri(nodeAVL x) {
        nodeAVL y = x.nodeKanan;
        nodeAVL 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(nodeAVL N) {
        return (N != null) ? getTinggi(N.nodeKiri) - getTinggi(N.nodeKanan) : 0;
    }

    nodeAVL minimal(nodeAVL nd) {
        nodeAVL curr = nd;
        while (curr.nodeKiri != null) {
            curr = curr.nodeKiri;
        }
        return curr;
    }

    nodeAVL insert(nodeAVL node, int data) {

        /* 1.  Penambahan Node pada BST biasa */
        if (node == null) {
            return (new nodeAVL(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*/
        nodeAVL result = balance(node, data);

        // hasilkan pasangan node baru 
        return result;
    }

    nodeAVL delete(nodeAVL akar, int data) {
        if (akar == null) {
            return akar;
        }
        if (data < akar.data) {
            akar.nodeKiri = delete(akar.nodeKanan, data);
        } else if (data > akar.data) {
            akar.nodeKanan = delete(akar.nodeKanan, data);
        } else if ((akar.nodeKiri == null) || (akar.nodeKanan == null)) {
            nodeAVL tmp = null;
            if (tmp == akar.nodeKiri) {
                tmp = akar.nodeKanan;
            } else {
                tmp = akar.nodeKiri;
            }
            if (tmp == null) {
                tmp = akar;
                akar = null;
            } else {
                akar = tmp;
            }
        } else {
            nodeAVL tmp = minimal(akar.nodeKanan);
            akar.data = tmp.data;
            akar.nodeKanan = delete(akar.nodeKanan, tmp.data);
        }
        if (akar == null) {
            return akar;
        }
        akar.tinggi = max(getTinggi(akar.nodeKiri), getTinggi(akar.nodeKanan));
        int blnc = getBalance(akar);
        if (blnc > 1 && getBalance(akar.nodeKiri) >= 0) {
            return putarKanan(akar);
        }
        if (blnc > 1 && getBalance(akar.nodeKanan) < 0) {
            akar.nodeKiri = putarKiri(akar.nodeKiri);
            return putarKanan(akar);
        }
        if (blnc < -1 && getBalance(akar.nodeKanan) <= 0) {
            return putarKiri(akar);
        }
        if (blnc < -1 && getBalance(akar.nodeKanan) > 0) {
            akar.nodeKanan = putarKanan(akar.nodeKanan);
            return putarKiri(akar);
        }
        return akar;
    }

    boolean search(nodeAVL akar, int data) {
        nodeAVL loc = akar;
        while (loc != null) {
            if (loc.data == 0) {
                return true;
            } else if (loc.data > 0) {
                loc = loc.nodeKiri;
            } else {
                loc = loc.nodeKanan;
            }
        }
        return false;
    }

    nodeAVL balance(nodeAVL 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(nodeAVL node) {
        if (node != null) {
            inOrder(node.nodeKiri);
            System.out.print(node.data + " ");
            inOrder(node.nodeKanan);

        }
    }

    void preOrder(nodeAVL node) {
        if (node != null) {
            System.out.print(node.data + " ");
            preOrder(node.nodeKiri);
            preOrder(node.nodeKanan);
        }
    }

    static int miniNode(int tinggi) {
        return (int) (Math.round(((Math.sqrt(5) + 2) / Math.sqrt(5)) * Math.pow((1 + Math.sqrt(5)) / 2, tinggi) - 1));
    }

    public static void main(String[] args) {
        Bab10AVL tree = new Bab10AVL();
        Random rd = new Random();
        Scanner sausan = new Scanner(System.in);
        tree.akar = tree.insert(tree.akar, 200);
        tree.akar = tree.insert(tree.akar, 1);
        tree.akar = tree.insert(tree.akar, 150);
        tree.akar = tree.insert(tree.akar, 111154);
        tree.akar = tree.insert(tree.akar, 55);

        /* hasil dari AVL Tree program diatas adalah 
               150 
              /   \ 
             1    200 
              \     \ 
              55     11154 
         */
        System.out.println("Preorder");
        tree.preOrder(tree.akar);
        System.out.println("\nInorder");
        tree.inOrder(tree.akar);
        tree.akar = tree.delete(tree.akar, 150);
        System.out.println("\n=====Setelah 150 dihapus=====");
        System.out.println("Preorder");
        tree.preOrder(tree.akar);
        System.out.println("\nInorder");
        tree.inOrder(tree.akar);
        System.out.println("\n===========Cari 55===========");
        tree.search(tree.akar, 55);
        System.out.println("Preorder");
        tree.preOrder(tree.akar);
        System.out.println("\nInorder");
        tree.inOrder(tree.akar);
        System.out.println("\n======Jumlah Minimal Node======");
        System.out.println("Masukkan level node: ");
        int input = sausan.nextInt();
        System.out.println("Jumlah minimal node: ");
        System.out.println(miniNode(input));        
        int val = 0;
        System.out.println("Urutan nilai node yang mungkin:");
        for (int i = 1; i <= miniNode(input); i++) {
            val = rd.nextInt(100);            
            System.out.print(val + " ");            
            tree.insert(tree.akar, val);
        }
        
    }
}

Download the file here