Binary Tree: Algoritma, dan Implementasi pada Struktur Data

Table of Contents

Pengertian Binary Tree

Sebuah binary tree adalah struktur data pohon di mana setiap simpul (node) memiliki paling banyak dua anak (child). Anak-kiri disebut left child dan anak-kanan right child. Komponen inti binary tree meliputi:

Root: simpul paling atas dan titik awal traversals.
Node: elemen yang menyimpan data serta referensi ke anak.
Edge: hubungan (link) antar simpul.
Leaf: simpul tanpa anak, menandai ujung cabang.

Binary tree sering menjadi landasan bagi struktur yang lebih kompleks seperti binary search tree (BST), heap, pohon AVL, dan pohon B. Kelebihan utama adalah operasi pencarian, penyisipan, dan penghapusan yang dapat dilakukan dengan kompleksitas rata-rata O(log n) pada tree seimbang.

Karakteristik Utama

Beberapa karakteristik yang membedakan binary tree dari pohon umum:

Derajat maksimum setiap node adalah 2.
Keyakinan arah anak jelas: kiri dan kanan.
Kedalaman (depth) mengindikasikan jarak antara root dan node tertentu.
Tingkatan (level) memetakan node ke lapisan pohon: root di level 1, anak di level 2, dan seterusnya.
Tinggi (height) tree adalah kedalaman node terjauh dari root.

Dengan pemahaman karakteristik ini, kita dapat memprediksi kinerja operasi dan memilih implementasi yang tepat sesuai kebutuhan aplikasi.

Jenis-jenis Binary Tree

1. Full (Strict) Binary Tree

Full binary tree, atau strict binary tree, adalah pohon di mana setiap node memiliki 0 atau 2 anak. Struktur full binary tree memastikan setiap parent node terisi penuh dua cabang atau tidak sama sekali. Hal ini menghasilkan keseimbangan yang lebih baik jika dibandingkan skewed tree, meski tidak menjamin ketinggian minimal.

2. Complete Binary Tree

Complete binary tree diisi dari kiri ke kanan tanpa celah. Semua level kecuali yang terakhir terisi penuh, sedangkan level terakhir diisi mulai dari posisi paling kiri. Keuntungan complete binary tree adalah implementasi yang efisien menggunakan array, meminimalkan overhead pointer, serta memudahkan perhitungan lokasi anak (2*i dan 2*i+1).

3. Perfect Binary Tree dan Skewed Binary Tree

Perfect binary tree adalah full binary tree di mana semua leaf berada pada level yang sama, menghasilkan node count ideal: 2^h – 1, dengan h tinggi tree. Sementara skewed binary tree (left-skewed atau right-skewed) memiliki setiap node hanya satu anak. Struktur skewed menurunkan efisiensi operasi menjadi O(n) karena mirip linked list.

Operasi Dasar pada Binary Tree

Traversal: Preorder, Inorder, Postorder

Traversal mengunjungi setiap simpul sesuai urutan tertentu. Pada binary tree, terdapat tiga metode umum:

Preorder (Root, Left, Right): kunjungi root, lalu panggil preorder pada subtree kiri, kemudian subtree kanan. Berguna untuk menyalin pohon.
Inorder (Left, Root, Right): kunjungi subtree kiri, root, lalu subtree kanan. Pada BST, inorder traversal menghasilkan data terurut menaik.
Postorder (Left, Right, Root): kunjungi subtree kiri, kanan, kemudian root. Sering digunakan dalam penghapusan pohon karena anak dihapus sebelum parent.

Setiap metode memiliki kompleksitas O(n), mengunjungi semua node sekali. Pemilihan traversal tergantung tujuan, seperti pencetakan data, evaluasi ekspresi, atau kloning pohon.

Penyisipan (Insert) dan Penghapusan (Delete) Node

Pada binary search tree (BST), proses penyisipan memerlukan perbandingan nilai dengan node saat ini: jika lebih kecil, lanjut ke subtree kiri; jika lebih besar, ke subtree kanan. Setelah mencapai posisi null, simpul baru ditempatkan. Kompleksitas rata-rata O(log n), pada kasus terburuk O(n) jika tree tidak seimbang.

Penghapusan node pada BST memiliki tiga kasus:

Leaf node: cukup hapus langsung.
Node dengan satu anak: ganti node dengan anaknya.
Node dengan dua anak: cari penerus inorder (inorder successor) atau predecessor, salin nilainya, lalu hapus penerus tersebut.

Hapus perlu penanganan pointer agar tree tetap valid dan seimbang jika diperlukan.

Pencarian (Search) Node

Pencarian pada BST mirip penyisipan: bandingkan kunci dengan root, jika sama, selesai; jika lebih kecil, ke subtree kiri; jika lebih besar, subtree kanan. Kompleksitas rata-rata O(log n). Pada tree tidak terurut atau generic binary tree, pencarian memerlukan traversal lengkap (BFS atau DFS) dengan kompleksitas O(n).

Implementasi Binary Tree

Struktur data binary tree umumnya diimplementasikan menggunakan pointer (bahasa C/C++) atau referensi objek (Java, Python). Contoh implementasi bahasa C:

typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;

Node* createNode(int value) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = value;
    node->left = node->right = NULL;
    return node;
}

typedef struct Node {

int data;

struct Node *left;

struct Node *right;

} Node;

Node* createNode(int value) {

Node* node = (Node*)malloc(sizeof(Node));

node->data = value;

node->left = node->right = NULL;

return node;

}

Pada Java, kelas Node dan Tree memudahkan penerapan prinsip OOP:

public class Node {
    int data;
    Node left, right;
    public Node(int item) {
        data = item;
        left = right = null;
    }
}
public class BinaryTree {
    Node root;
    // Metode traversal, insert, delete ditambahkan di sini
}

public class Node {

int data;

Node left, right;

public Node(int item) {

data = item;

left = right = null;

}

public class BinaryTree {

Node root;

// Metode traversal, insert, delete ditambahkan di sini

}

Binary tree dan variannya banyak digunakan dalam skenario nyata:

Binary Search Tree (BST): implementasi struktur data dinamis dengan operasi O(log n).
Min/Max Heap: basis priority queue dengan operasi ekstrak dan sisip efisien.
Parse Tree dan Expression Tree: evaluasi ekspresi matematika atau logika.
Huffman Tree: algoritma kompresi data untuk pengodean variabel panjang.
Segment Tree dan Fenwick Tree: query rentang dan pembaruan data dalam array.

Studi Kasus: Penggunaan dalam Mesin Pencari

Mesin pencari skala besar menggunakan varian pohon seperti B-Tree dan Trie untuk menyimpan indeks kata dan metadata dokumen. Struktur ini memungkinkan pencarian kata kunci dengan kompleksitas O(m), m panjang kata, serta memfasilitasi saran otomatis (autocomplete).

Untuk menjaga performa, pertimbangkan:

Menggunakan self-balancing tree (AVL, Red-Black Tree) untuk memastikan ketinggian O(log n).
Memanfaatkan array representation untuk complete binary tree agar pointer tidak diperlukan.
Menerapkan teknik lazy deletion pada skenario update tinggi untuk menghindari operasi delete yang mahal.
Mengelola memory pool untuk alokasi node cepat dan mengurangi fragmentasi.

Kesimpulan

Binary tree adalah fondasi struktur data yang krusial dalam ilmu komputer. Dengan memahami jenis, operasi, serta implementasi, Anda dapat memilih model terbaik untuk aplikasi seperti database, kompresi data, dan algoritma graf. Langkah selanjutnya: mendalami self-balancing trees (AVL, Red-Black), pohon B-Tree, dan teknik caching node untuk performa optimal pada data berukuran besar.