#4 Tree

Oke, kita masuk ke modul empat! Setelah kemarin kita main-main sama data yang lurus-lurus aja (linear) kayak Linked List, Stack, dan Queue, sekarang kita kenalan sama struktur data yang punya cabang: Tree.

Bayangin aja struktur folder di komputermu, atau silsilah keluarga. Ada satu folder/leluhur utama (disebut root), terus dia punya anak (child), anaknya punya anak lagi, dan seterusnya. Itulah konsep dasar Tree. Setiap item di dalam tree kita sebut node, dan node yang udah nggak punya anak lagi kita sebut leaf (daun).

Binary Search Tree (BST): Tree yang Teratur

Ada banyak jenis Tree, tapi yang paling sering jadi dasar adalah Binary Search Tree (BST). Kenapa? Karena dia sangat teratur. Aturannya simpel:

Untuk setiap node, semua data di cabang kiri-nya harus lebih kecil, dan semua data di cabang kanan-nya harus lebih besar.

Aturan ini bikin proses pencarian data jadi super cepat, mirip kayak Binary Search yang udah kita pelajari.

Cetakan Node untuk Tree

Node pada Tree sedikit beda. Selain nyimpen data, dia punya dua referensi: left buat anak kiri, dan right buat anak kanan.

1
class Node {
2
    int data;
3
    Node left, right;
4

5
    public Node(int data) {
6
        this.data = data;
7
        left = right = null;
8
    }
9
}

Implementasi Binary Search Tree

Sekarang kita bikin class buat Tree-nya. Kita mulai dengan root yang jadi titik awal.

1
class BinarySearchTree {
2
    Node root;
3

4
    // Method utama untuk memasukkan data
5
    public void insert(int data) {
6
        root = insertRec(root, data);
7
    }
8

9
    // Method rekursif untuk mencari posisi yang pas
10
    private Node insertRec(Node current, int data) {
11
        if (current == null) {
12
            return new Node(data); // Posisi kosong ditemukan, buat node baru
13
        }
14

15
        if (data < current.data) {
16
            current.left = insertRec(current.left, data);
17
        } else if (data > current.data) {
18
            current.right = insertRec(current.right, data);
19
        }
20

21
        return current;
22
    }
23

24
    // Method utama untuk mencari data
25
    public boolean find(int data) {
26
        return findRec(root, data);
27
    }
28

29
    // Method rekursif untuk menelusuri tree
30
    private boolean findRec(Node current, int data) {
31
        if (current == null) {
32
            return false; // Udah mentok, data nggak ada
33
        }
34

35
        if (data == current.data) {
36
            return true; // Ketemu!
37
        }
38

39
        return data < current.data
40
            ? findRec(current.left, data)  // Cari di kiri
41
            : findRec(current.right, data); // Cari di kanan
42
    }
43
}

Logikanya rekursif, artinya method-nya manggil dirinya sendiri buat turun ke cabang kiri atau kanan sampe ketemu posisi yang pas.

Tree Traversal: Jalan-Jalan di Dalam Tree

Kalau mau nampilin semua data di dalam Tree, gimana caranya? Ada tiga cara umum buat “jalan-jalan” (traversal) di Tree, dan ketiganya ini penting banget.

1. In-Order Traversal (Kiri - Akar - Kanan)

Cara ini bakal ngunjungin anak kiri, terus si node itu sendiri, baru ke anak kanan. Kalau kita lakuin di BST, hasilnya bakal jadi data yang terurut, lho! Keren kan?

1
public void printInOrder(Node node) {
2
    if (node != null) {
3
        printInOrder(node.left);
4
        System.out.print(node.data + " ");
5
        printInOrder(node.right);
6
    }
7
}

2. Pre-Order Traversal (Akar - Kiri - Kanan)

Kalau yang ini, kita catet dulu data node saat ini, baru lanjut ke anak kiri, terus ke anak kanan. Biasanya cara ini dipake buat nyalin (copy) sebuah Tree.

1
public void printPreOrder(Node node) {
2
    if (node != null) {
3
        System.out.print(node.data + " ");
4
        printPreOrder(node.left);
5
        printPreOrder(node.right);
6
    }
7
}

3. Post-Order Traversal (Kiri - Kanan - Akar)

Nah, kalau yang ini kebalikannya. Kita beresin dulu semua anak kiri, terus semua anak kanan, baru kita catet data node saat ini. Cara ini sering dipake buat proses ngehapus node dari Tree.

1
public void printPostOrder(Node node) {
2
    if (node != null) {
3
        printPostOrder(node.left);
4
        printPostOrder(node.right);
5
        System.out.print(node.data + " ");
6
    }
7
}

Penutup Modul 4

Tree ini emang kelihatan ribet di awal, tapi konsepnya kuat banget. Kemampuannya buat nyimpen data secara hierarkis sambil tetep efisien buat pencarian bikin Tree jadi salah satu struktur data paling penting.

Di modul terakhir, kita bakal bahas Graph, yaitu bentuk yang lebih umum dari Tree di mana aturannya lebih bebas. Sampai jumpa di sana!