Binary tree adalah struktur data hierarkis: setiap node punya paling banyak dua anak (kiri dan kanan). Berbeda dari array dan linked list yang linear, tree memungkinkan representasi data bertingkat seperti pohon keluarga, struktur direktori, atau ekspresi matematika. Varian paling praktis adalah Binary Search Tree (BST): kiri selalu lebih kecil, kanan selalu lebih besar. BST memberi search, insert, delete rata-rata O(log n)—selama tree tetap seimbang. Pada chapter ini kita akan mengimplementasikan BST dengan operasi insert, search, dan tiga jenis traversal.

Konsep Binary Tree dan BST #

Setiap node binary tree punya tiga komponen:

  • data: nilai yang disimpan.
  • kiri: pointer ke anak kiri (boleh NULL).
  • kanan: pointer ke anak kanan (boleh NULL).

Node tanpa anak disebut leaf. Node paling atas disebut root. Kedalaman node adalah jumlah edge dari root ke node tersebut. Tinggi tree adalah kedalaman maksimum.

BST adalah binary tree dengan properti: untuk setiap node N, semua nilai di subtree kiri lebih kecil dari N.data, dan semua nilai di subtree kanan lebih besar. Properti ini memungkinkan pencarian seperti binary search: bandingkan dengan root, lalu pilih subtree kiri atau kanan.

Implementasi BST #

c 
#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int data;
    struct node *kiri;
    struct node *kanan;
} node;

static node *buat_node(int data) {
    node *n = malloc(sizeof(node));
    if (n == NULL) return NULL;
    n->data = data;
    n->kiri = NULL;
    n->kanan = NULL;
    return n;
}

/* Insert BST: kiri < root < kanan */
node *bst_insert(node *root, int data) {
    if (root == NULL) return buat_node(data);
    if (data < root->data)
        root->kiri = bst_insert(root->kiri, data);
    else if (data > root->data)
        root->kanan = bst_insert(root->kanan, data);
    /* bila sama, abaikan (no duplicates) */
    return root;
}

/* Search BST */
node *bst_search(node *root, int target) {
    while (root != NULL) {
        if (target == root->data) return root;
        if (target < root->data) root = root->kiri;
        else root = root->kanan;
    }
    return NULL;
}

/* In-order traversal: kiri, root, kanan (urut menaik) */
void bst_inorder(node *root) {
    if (root == NULL) return;
    bst_inorder(root->kiri);
    printf("%d ", root->data);
    bst_inorder(root->kanan);
}

/* Pre-order traversal: root, kiri, kanan */
void bst_preorder(node *root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    bst_preorder(root->kiri);
    bst_preorder(root->kanan);
}

/* Post-order traversal: kiri, kanan, root */
void bst_postorder(node *root) {
    if (root == NULL) return;
    bst_postorder(root->kiri);
    bst_postorder(root->kanan);
    printf("%d ", root->data);
}

/* Bebaskan seluruh tree (post-order) */
void bst_hapus_semua(node *root) {
    if (root == NULL) return;
    bst_hapus_semua(root->kiri);
    bst_hapus_semua(root->kanan);
    free(root);
}

int main(void) {
    node *root = NULL;
    int nilai[] = {50, 30, 70, 20, 40, 60, 80, 35, 45};
    int n = sizeof(nilai) / sizeof(nilai[0]);

    for (int i = 0; i < n; i++) {
        root = bst_insert(root, nilai[i]);
    }

    printf("In-order  : ");
    bst_inorder(root);
    printf("\n");

    printf("Pre-order : ");
    bst_preorder(root);
    printf("\n");

    printf("Post-order: ");
    bst_postorder(root);
    printf("\n");

    int cari[] = {40, 35, 99};
    for (int i = 0; i < 3; i++) {
        node *found = bst_search(root, cari[i]);
        printf("Cari %d: %s\n", cari[i],
               found != NULL ? "ditemukan" : "tidak ada");
    }

    bst_hapus_semua(root);
    return 0;
}

Output yang Dihasilkan:

text 
In-order  : 20 30 35 40 45 50 60 70 80 
Pre-order : 50 30 20 40 35 45 70 60 80 
Post-order: 20 35 45 40 30 60 80 70 50 
Cari 40: ditemukan
Cari 35: ditemukan
Cari 99: tidak ada

In-order traversal pada BST menghasilkan nilai terurut menaik—ini properti kunci BST. Pre-order berguna untuk salin tree (rekonstruksi struktur). Post-order berguna untuk hapus tree (child di-free sebelum parent).

Mari kita telaah baris-baris kode di atas:

  1. Baris 4-8 (struct node): struct self-referential dengan tiga field. Pointer kiri dan kanan bisa NULL bila tidak ada anak.
  2. Baris 10-16 (buat_node): alokasi node baru via malloc. Selalu cek NULL. Set pointer anak ke NULL agar tidak dangling saat traversal.
  3. Baris 19-27 (bst_insert rekursif): bila root == NULL, buat node baru. Bila data < root->data, insert rekursif ke subtree kiri. Bila data > root->data, insert rekursif ke subtree kanan. Bila sama, abaikan (tidak ada duplikat).
  4. Baris 30-38 (bst_search iteratif): loop while dengan komparasi sederhana. Pilih subtree kiri/kanan sesuai perbandingan. Kompleksitas O(h) di mana h adalah tinggi tree.
  5. Baris 41-46 (bst_inorder): rekursi ke kiri dulu, lalu cetak root->data, lalu rekursi ke kanan. Pola ini menghasilkan urutan menaik pada BST.
  6. Baris 49-54 (bst_preorder): cetak root->data dulu, lalu rekursi kiri dan kanan. Urutan ini menggambarkan struktur tree dari atas ke bawah.
  7. Baris 57-62 (bst_postorder): rekursi kiri, kanan, baru cetak root->data. Urutan ini berguna untuk hapus tree—child di-free lebih dulu sebelum parent.
  8. Baris 65-70 (bst_hapus_semua): post-order traversal lalu free. Wajib post-order agar root->kiri dan root->kanan masih bisa diakses sebelum free(root).

Bahaya BST Degenerate #

BST tidak menjamin keseimbangan. Bila insert dilakukan pada data terurut, BST degenerasi menjadi linked list—setiap node punya hanya satu anak. Tinggi tree menjadi n, dan operasi search/insert menjadi O(n) alih-alih O(log n).

c 
#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int data;
    struct node *kiri;
    struct node *kanan;
} node;

static node *buat_node(int data) {
    node *n = malloc(sizeof(node));
    if (n == NULL) return NULL;
    n->data = data;
    n->kiri = NULL;
    n->kanan = NULL;
    return n;
}

node *bst_insert(node *root, int data) {
    if (root == NULL) return buat_node(data);
    if (data < root->data)
        root->kiri = bst_insert(root->kiri, data);
    else if (data > root->data)
        root->kanan = bst_insert(root->kanan, data);
    return root;
}

/* Cari minimum (node terkiri) */
node *bst_min(node *root) {
    while (root != NULL && root->kiri != NULL) root = root->kiri;
    return root;
}

/* Cari maksimum (node terkanan) */
node *bst_max(node *root) {
    while (root != NULL && root->kanan != NULL) root = root->kanan;
    return root;
}

/* Hitung tinggi tree */
int bst_tinggi(node *root) {
    if (root == NULL) return 0;
    int h_kiri = bst_tinggi(root->kiri);
    int h_kanan = bst_tinggi(root->kanan);
    return 1 + (h_kiri > h_kanan ? h_kiri : h_kanan);
}

/* Hitung jumlah node */
size_t bst_count(node *root) {
    if (root == NULL) return 0;
    return 1 + bst_count(root->kiri) + bst_count(root->kanan);
}

void bst_hapus_semua(node *root) {
    if (root == NULL) return;
    bst_hapus_semua(root->kiri);
    bst_hapus_semua(root->kanan);
    free(root);
}

int main(void) {
    node *root = NULL;
    int nilai[] = {10, 20, 30, 40, 50, 60};
    int n = sizeof(nilai) / sizeof(nilai[0]);

    for (int i = 0; i < n; i++) {
        root = bst_insert(root, nilai[i]);
    }

    printf("BST degenerate (insert sorted):\n");
    printf("  Jumlah node: %zu\n", bst_count(root));
    printf("  Tinggi tree: %d\n", bst_tinggi(root));
    printf("  Min: %d\n", bst_min(root)->data);
    printf("  Max: %d\n", bst_max(root)->data);

    bst_hapus_semua(root);

    root = NULL;
    int nilai2[] = {40, 20, 60, 10, 30, 50, 70};
    n = sizeof(nilai2) / sizeof(nilai2[0]);
    for (int i = 0; i < n; i++) {
        root = bst_insert(root, nilai2[i]);
    }
    printf("\nBST seimbang (insert acak):\n");
    printf("  Jumlah node: %zu\n", bst_count(root));
    printf("  Tinggi tree: %d\n", bst_tinggi(root));
    printf("  Min: %d\n", bst_min(root)->data);
    printf("  Max: %d\n", bst_max(root)->data);

    bst_hapus_semua(root);
    return 0;
}

Output yang Dihasilkan:

text 
BST degenerate (insert sorted):
  Jumlah node: 6
  Tinggi tree: 6
  Min: 10
  Max: 60

BST seimbang (insert acak):
  Jumlah node: 7
  Tinggi tree: 3
  Min: 10
  Max: 70

Insert data terurut menghasilkan BST degenerate dengan tinggi 6 (sama dengan jumlah node)—ekuivalen dengan linked list. Insert data acak menghasilkan BST seimbang dengan tinggi 3—kompleksitas O(log n).

Kompleksitas BST #

OperasiRata-rata (seimbang)Worst case (degenerate)
SearchO(log n)O(n)
InsertO(log n)O(n)
DeleteO(log n)O(n)
TraversalO(n)O(n)
Min/MaxO(log n)O(n)
Ruang tambahanO(n)O(n)