Binary Search Tree — Struktur Data

Binary Search Tree (BST) adalah binary tree dengan aturan: nilai kiri < parent < nilai kanan. Aturan ini membuat pencarian sangat efisien — setiap langkah…

Binary search tree (BST) adalah binary tree dengan satu aturan: untuk setiap node, semua nilai di sisi kirinya lebih kecil, dan semua nilai di sisi kanannya lebih besar. Ingat aturan ini saja, karena semua kemampuan BST datang dari situ. Mirip main tebak angka: tiap jawaban "lebih kecil" atau "lebih besar" langsung membuang separuh kemungkinan.

🧪 Tebakan cepat: di sebuah BST, angka paling kecil ada di mana? Tebak dulu, jawabannya ada di bagian "Aturannya: kiri lebih kecil, kanan lebih besar".

Aturannya: kiri lebih kecil, kanan lebih besar

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BST {
  constructor() {
    this.root = null;
  }

  insert(value) {
    const node = new TreeNode(value);
    if (this.root === null) {
      this.root = node;
      return;
    }
    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (current.left === null) {
          current.left = node;
          return;
        }
        current = current.left;
      } else {
        if (current.right === null) {
          current.right = node;
          return;
        }
        current = current.right;
      }
    }
  }
}

const bst = new BST();
[8, 3, 10, 1, 6, 14, 4, 7].forEach((v) => bst.insert(v));

//         8
//       /   \
//      3     10
//     / \      \
//    1   6      14
//       / \
//      4   7

console.log(bst.root.value);            // 8
console.log(bst.root.left.value);       // 3
console.log(bst.root.left.right.value); // 6

Contoh, insert(7) di pohon yang sudah berisi 8, 3, 10, 1, 6, 14, 4:

Langkah Dibandingkan dengan Lalu
1 8 7 lebih kecil, ke kiri
2 3 7 lebih besar, ke kanan
3 6 7 lebih besar, ke kanan
4 kanan 6 masih null 7 ditaruh di kanan 6

Cek aturannya di pohon itu: semua yang di kiri 8 (3, 1, 6, 4, 7) lebih kecil dari 8, semua yang di kanan 8 (10, 14) lebih besar. Hal yang sama berlaku untuk tiap node. Akibatnya, angka paling kecil selalu di node paling kiri (1), dan paling besar di node paling kanan (14). Itu jawaban tebakan tadi.

Mencari: turun satu jalur saja

function search(node, value) {
  while (node !== null) {
    if (value === node.value) return node;
    if (value < node.value) {
      node = node.left;
    } else {
      node = node.right;
    }
  }
  return null;
}

console.log(search(bst.root, 6).value); // 6
console.log(search(bst.root, 5));       // null

Kode ini memakai bst dari bagian sebelumnya. Mencarinya sama dengan insert: bandingkan, lalu turun ke kiri atau ke kanan.

return di dalam loop cuma dipakai waktu nilainya ketemu. Jawaban "gak ketemu" baru boleh diberikan sesudah loop, saat node sudah jadi null.

Kenapa cepat, dan kapan jadi lambat

Tiap langkah turun satu level dan membuang satu sisi pohon. Di pohon yang seimbang, 1.000 data cukup sekitar 10 langkah, dan sejuta data sekitar 20 langkah. Itu O(log n): datanya dikali dua, langkahnya cuma bertambah satu.

Tapi bentuk pohon tergantung urutan insert. Kalau datanya masuk sudah urut, misalnya 1, 2, 3, 4, 5, 6, 7, tiap nilai baru selalu ke kanan, dan pohonnya jadi rantai lurus seperti linked list. Mencari 7 harus melewati 7 node: O(n), datanya dua kali lipat, waktunya dua kali lipat. BST di dunia nyata (AVL, Red-Black) menyeimbangkan dirinya sendiri supaya ini gak terjadi.

Urutan in-order: otomatis terurut

In-order adalah cara mengunjungi semua node: sisi kiri dulu, lalu node itu, lalu sisi kanan. Karena aturan BST, hasilnya selalu urut dari kecil ke besar:

function inOrder(node, hasil = []) {
  if (node === null) return hasil;
  inOrder(node.left, hasil);
  hasil.push(node.value);
  inOrder(node.right, hasil);
  return hasil;
}

console.log(inOrder(bst.root)); // [1, 3, 4, 6, 7, 8, 10, 14]

Urutan insert apa pun, selama aturannya dijaga, in-order sebuah BST selalu memberi nilai yang terurut.

⚠️ Jebakan yang sering ketemu

💡 BST atau hash map? Hash map menjawab "ada gak?" rata-rata dalam O(1), lebih cepat dari BST. Tapi isinya gak urut. BST yang seimbang tetap O(log n) dan menyimpan data dalam urutan, jadi cocok untuk "ambil nilai terkecil", "semua nilai antara 10 dan 50", atau daftar yang harus selalu terurut.

TL;DR: BST adalah binary tree dengan aturan: kiri lebih kecil, kanan lebih besar, di setiap node. Insert dan search sama-sama mulai dari root, bandingkan, lalu turun ke kiri atau ke kanan sampai ketemu, atau sampai null. Pencarian yang gagal baru dijawab sesudah loop. Pohon seimbang: O(log n), 1.000 data sekitar 10 langkah. Data yang masuk sudah urut bikin pohon jadi rantai: O(n). Angka terkecil ada di paling kiri, dan in-order (kiri, node, kanan) selalu memberi nilai yang terurut.

Yang akan kamu pelajari