🌴Praktikum 1

Implementasi Binary Search Tree menggunakan Linked List

Deskripsi

Pada percobaan ini akan diimplementasikan Binary Search Tree dengan operasi dasar, dengan menggunakan array (praktikum 2) dan linked list (praktikum 1). Sebelumnya, akan dibuat class Node, dan Class BinaryTree. Perhatikan class diagram berikut,

Class Diagram Node

Class Diagram BinaryTree

Langkah Percobaan

• Buatlah class Node, BinaryTree dan BinaryTreeMain.

• Di dalam class Node, tambahkan atribut data, left dan right, serta konstruktor default dan berparameter.

public class Node {
    int data;
    Node left, right;

    public Node() {}
    
    public Node(int item) {
        data = item;
        left = right = null;
    }
}

• Di dalam class BinaryTree, tambahkan atribut root.

public class BinaryTree {
    Node root;

• Tambahkan konstruktor default dan method isEmpty() di dalam class BinaryTree.

public BinaryTree() {
    root = null;
}

public boolean isEmpty() {
    return root == null;
}

• Tambahkan method add() di dalam class BinaryTree. Di bawah ini proses penambahan node tidak dilakukan secara rekursif, agar lebih mudah dilihat alur proses penambahan node dalam tree. Jika dilakukan dengan proses rekursif, penulisan kode akan lebih efisien.

public void add(int data) {
    if(isEmpty()) {
        root = new Node(data);
    } else {
        Node current = root;
        while(true) {
            if(data < current.data) {
                if(current.left != null) {
                    current = current.left;
                } else {
                    current.left = new Node(data);
                    break;
                }
            } else if(data > current.data) {
                if(current.right != null) {
                    current = current.right;
                } else {
                    current.right = new Node(data);
                    break;
                }
            } else {
                break;
            }
        }
    }
}

• Tambahkan method find().

public boolean find(int data) {
    boolean found = false;
    Node current = root;
    while(current != null) {
        if(current.data == data) {
            found = true;
            break;
        } else if(current.data > data) {
            current = current.left;
        } else {
            current = current.right;
        }
    }
    return found;
}

• Tambahkan method traversePreOrder(), traverseInOrder() dan traversePostOrder(). Method traverse digunakan untuk mengunjungi dan menampilkan node-node dalam tree, baik dalam mode pre-order, in-order maupun post-order.

public void traversePreOrder(Node node) {
    if(node != null) {
        System.out.print(" " + node.data);
        traversePreOrder(node.left);
        traversePreOrder(node.right);
    }
}

public void traversePostOrder(Node node) {
    if(node != null) {
        traversePostOrder(node.left);
        traversePostOrder(node.right);
        System.out.print(" " + node.data);
    }
}

public void traverseInOrder(Node node) {
    if(node != null) {
        traverseInOrder(node.left);
        System.out.print(" " + node.data);
        traverseInOrder(node.right);
    }
}

• Tambahkan method getSuccessor(). Method ini akan digunakan ketika proses penghapusan node yang memiliki 2 child.

public Node getSuccessor(Node del) {
    Node successor = del.right;
    Node successorParent = del;
    while(successor.left != null) {
        successorParent = successor;
        successor = successor.left;
    }
    if(successor != del.right) {
        successorParent.left = successor.right;
        successor.right = del.right;
    }
    return successor;
}

• Tambahkan method delete(). Di dalam method delete tambahkan pengecekan apakah tree kosong, dan jika tidak cari posisi node yang akan di hapus. Kemudian tambahkan proses penghapusan terhadap node current yang telah ditemukan.

public void delete(int data) {
    // Pengecekan tree
    if(isEmpty()) {
        System.out.println("Tree masih kosong!");
        return;
    }
    Node parent = root;
    Node current = root;
    boolean isLeftChild = false;
    while(current != null) {
        if(current.data == data) {
            break;
        } else if(current.data > data) {
            parent = current;
            current = current.left;
            isLeftChild = true;
        } else {
            parent = current;
            current = current.right;
            isLeftChild = false;
        }
    }

    // Proses penghapusan
    if(current==null) {
        System.out.println("Data tidak ditemukan!");
        return;
    } else {
        // Jika tidak ada child
        if(current.left==null && current.right==null) {
            if(current==root) {
                root = null;
            } else {
                if(isLeftChild) {
                    parent.left = null;
                } else {
                    parent.right = null;
                }
            }
        } else if(current.left==null) { // Jika tidak ada child kiri
            if(current==root) {
                root = current.right;
            } else {
                if(isLeftChild) {
                    parent.left = current.right;
                } else {
                    parent.right = current.right;
                }
            }
        } else if(current.right==null) { // Jika tidak ada child kanan
            if(current==root) {
                root = current.left;
            } else {
                if(isLeftChild) {
                    parent.left = current.left;
                } else {
                    parent.right = current.left;
                }
            }
        } else { // Jika memiliki 2 child
            Node successor = getSuccessor(current);
            if(current==root) {
                root = successor;
            } else {
                if(isLeftChild) {
                    parent.left = successor;
                } else {
                    parent.right = successor;
                }
            }
            successor.left = current.left;
        }
    }
}

• Buka class BinaryTreeMain dan tambahkan method main().

public class BinaryTreeMain {
    public static void main(String[] args) {
        BinaryTree bt = new BinaryTree();
        bt.add(6);
        bt.add(4);
        bt.add(8);
        bt.add(3);
        bt.add(5);
        bt.add(7);
        bt.add(9);
        bt.add(10);
        bt.add(15);

        bt.traversePreOrder(bt.root);
        System.out.println();
        bt.traverseInOrder(bt.root);
        System.out.println();
        bt.traversePostOrder(bt.root);
        System.out.println();
        System.out.println(bt.find(5));
        bt.delete(8);
        bt.traversePreOrder(bt.root);
        System.out.println();
    }
}

• Compile dan jalankan class BinaryTreeMain untuk mendapatkan simulasi jalannya program tree yang telah dibuat.

• Amati hasil running tersebut.

Pertanyaan

1. Mengapa dalam binary search tree proses pencarian data bisa lebih efektif dilakukan dibanding binary tree biasa?

2. Apa fungsi atribut left dan right pada class Node?

3. Simak pertanyaan berikut,

   1. Apa kegunaan dari atribut root di dalam class BinaryTree?

   2. Ketika objek tree pertama kali dibuat, apa nilai dari root?

4. Ketika tree masih kosong, dan akan ditambahkan sebuah node baru, proses apa yang akan terjadi?

5. Perhatikan method add(), di dalamnya terdapat baris program seperti di bawah ini. Jelaskan secara detil untuk apa baris program tersebut?

if(data < current.data) {
    if(current.left != null) {
        current = current.left;
    } else {
        current.left = new Node(data);
        break;
    }
}