Binary Search Tree (BST)
Terakhir diperbarui
Binary search tree adalah pohon yang menyimpan nilainya dalam urutan terurut: untuk setiap node, semua nilai di subtree kirinya lebih kecil dan semua nilai di subtree kanannya lebih besar. Untuk menyisipkan atau mencari sebuah nilai, kamu mulai dari root lalu terus bergerak ke kiri atau ke kanan sesuai hasil perbandingan, sehingga setiap langkah membagi dua ruang pencarian. Tekan Putar di atas untuk melihat nilai ditempatkan lewat perbandingan dan sebuah pencarian menuruni pohon.
Pada pohon yang seimbang, operasi-operasi ini berjalan dalam waktu O(log n). Masalahnya: menyisipkan data yang sudah terurut membuat pohon merosot menjadi linked list dengan operasi O(n). Itulah alasan varian yang menyeimbangkan diri seperti AVL tree dan red-black tree ada.
Kompleksitas waktu dan ruang
| Operasi | Seimbang | Kasus terburuk (miring) |
|---|---|---|
| Pencarian | O(log n) | O(n) |
| Penyisipan | O(log n) | O(n) |
| Penghapusan | O(log n) | O(n) |
| Ruang | O(n) | O(n) |
Langkah demi langkah (penyisipan)
| Langkah | Apa yang terjadi |
|---|---|
| 1 | Jika pohon kosong, nilai baru menjadi root. |
| 2 | Jika tidak, mulai dari root. |
| 3 | Jika nilainya lebih kecil, pergi ke anak kiri; jika lebih besar, pergi ke kanan. |
| 4 | Ulangi sampai kamu mencapai tempat yang kosong. |
| 5 | Pasang nilai baru sebagai leaf di tempat itu. |
Contoh penerapan
Menyisipkan [5, 3, 8, 1, 4] ke pohon kosong, satu nilai demi satu nilai:
| Sisipkan | Jalur yang dilalui | Aksi |
|---|---|---|
5 | - | Pohon kosong, jadi 5 menjadi root. |
3 | 5 | 3 < 5, pergi ke kiri; tempatnya kosong, pasang 3 sebagai anak kiri 5. |
8 | 5 | 8 > 5, pergi ke kanan; tempatnya kosong, pasang 8 sebagai anak kanan 5. |
1 | 5 -> 3 | 1 < 5 pergi ke kiri, lalu 1 < 3 pergi ke kiri; pasang 1 sebagai anak kiri 3. |
4 | 5 -> 3 | 4 < 5 pergi ke kiri, lalu 4 > 3 pergi ke kanan; pasang 4 sebagai anak kanan 3. |
Kapan memakai binary search tree
| Pakai saat | Hindari saat |
|---|---|
| Kamu butuh urutan terurut sekaligus pencarian cepat, dan penyisipan datang dalam urutan acak. | Datamu datang dalam keadaan terurut: BST yang tidak seimbang merosot menjadi O(n) per operasi. |
| Kamu ingin penelusuran in-order menghasilkan nilai dalam urutan terurut tanpa usaha tambahan. | Kamu hanya butuh pengecekan keanggotaan tanpa urutan: hash table memberi pencarian rata-rata O(1). |
| Kamu butuh range query atau successor/predecessor dari sebuah key. | Kamu butuh batas O(log n) yang terjamin: pakai AVL tree atau red-black tree yang menyeimbangkan diri. |
| Datanya sering berubah dan array terurut yang statis akan mahal untuk diperbarui. | Datanya tetap dan hanya dibaca: array terurut dengan binary search lebih sederhana dan ramah cache. |
Kode Binary Search Tree
Implementasi Binary Search Tree yang rapi dan siap dijalankan dalam Python, JavaScript, Java, C++, C. Pilih bahasa, salin kodenya, atau buka langsung di Coddy Playground.
Kode Binary Search Tree dalam Python
Python
1class Node:2 def __init__(self, key):3 self.key = key4 self.left = None5 self.right = None6
7
8def insert(node, key):9 if node is None:10 return Node(key)11 if key < node.key:12 node.left = insert(node.left, key)13 elif key > node.key:14 node.right = insert(node.right, key)15 return node # duplicates are ignored16
17
18def search(node, key):19 if node is None:20 return False21 if key == node.key:22 return True23 if key < node.key:24 return search(node.left, key)25 return search(node.right, key)26
27
28def inorder(node):29 if node is None:30 return []31 return inorder(node.left) + [node.key] + inorder(node.right)32
33
34root = None35for key in [8, 3, 10, 1, 6, 14, 4, 7]:36 root = insert(root, key)37
38print("Inorder (sorted):", inorder(root))39print("search(6): ", search(root, 6))40print("search(5): ", search(root, 5))Kode Binary Search Tree dalam JavaScript
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.left = null;5 this.right = null;6 }7}8
9class BinarySearchTree {10 constructor() {11 this.root = null;12 }13
14 insert(value) {15 const attach = (node) => {16 if (!node) return new Node(value);17 if (value < node.value) node.left = attach(node.left);18 else node.right = attach(node.right);19 return node;20 };21 this.root = attach(this.root);22 }23
24 search(value) {25 let current = this.root;26 while (current) {27 if (value === current.value) return true;28 current = value < current.value ? current.left : current.right;29 }30 return false;31 }32
33 // Inorder traversal of a BST visits values in sorted order34 inorder(node = this.root, out = []) {35 if (!node) return out;36 this.inorder(node.left, out);37 out.push(node.value);38 this.inorder(node.right, out);39 return out;40 }41}42
43const bst = new BinarySearchTree();44for (const value of [8, 3, 10, 1, 6, 14, 4]) bst.insert(value);45console.log("Inorder:", bst.inorder().join(" "));46console.log("search(6):", bst.search(6));47console.log("search(7):", bst.search(7));Kode Binary Search Tree dalam Java
Java
1public class Main {2 static class Node {3 int key;4 Node left, right;5 Node(int key) { this.key = key; }6 }7
8 static Node insert(Node node, int key) {9 if (node == null) return new Node(key);10 // Smaller keys go left, larger keys go right11 if (key < node.key) node.left = insert(node.left, key);12 else if (key > node.key) node.right = insert(node.right, key);13 return node;14 }15
16 static boolean search(Node node, int key) {17 if (node == null) return false;18 if (key == node.key) return true;19 return key < node.key ? search(node.left, key) : search(node.right, key);20 }21
22 static void inorder(Node node, StringBuilder sb) {23 if (node == null) return;24 inorder(node.left, sb);25 sb.append(node.key).append(" ");26 inorder(node.right, sb);27 }28
29 public static void main(String[] args) {30 Node root = null;31 int[] keys = {8, 3, 10, 1, 6, 14, 4};32 for (int k : keys) root = insert(root, k);33
34 StringBuilder sb = new StringBuilder();35 inorder(root, sb);36 System.out.println("Inorder (sorted): " + sb.toString().trim());37 System.out.println("search 6: " + search(root, 6));38 System.out.println("search 7: " + search(root, 7));39 }40}Kode Binary Search Tree dalam C++
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* left = nullptr;6 Node* right = nullptr;7 explicit Node(int v) : value(v) {}8};9
10Node* insert(Node* root, int value) {11 if (root == nullptr) return new Node(value);12 if (value < root->value) root->left = insert(root->left, value);13 else if (value > root->value) root->right = insert(root->right, value);14 return root; // duplicates are ignored15}16
17bool contains(const Node* root, int value) {18 // Walk down: smaller goes left, larger goes right19 while (root != nullptr) {20 if (value == root->value) return true;21 root = value < root->value ? root->left : root->right;22 }23 return false;24}25
26void inorder(const Node* node) {27 if (node == nullptr) return;28 inorder(node->left);29 std::cout << node->value << " ";30 inorder(node->right);31}32
33int main() {34 Node* root = nullptr;35 for (int value : {50, 30, 70, 20, 40, 60, 80}) {36 root = insert(root, value);37 }38 std::cout << "Sorted: ";39 inorder(root);40 std::cout << "\n" << std::boolalpha;41 std::cout << "contains(40): " << contains(root, 40) << "\n";42 std::cout << "contains(45): " << contains(root, 45) << "\n";43 return 0;44}Kode Binary Search Tree dalam C
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct Node {6 int value;7 struct Node* left;8 struct Node* right;9} Node;10
11Node* newNode(int value) {12 Node* n = malloc(sizeof(Node));13 n->value = value;14 n->left = n->right = NULL;15 return n;16}17
18Node* insert(Node* root, int value) {19 if (root == NULL) return newNode(value);20 if (value < root->value) root->left = insert(root->left, value);21 else if (value > root->value) root->right = insert(root->right, value);22 return root; // duplicates are ignored23}24
25bool contains(const Node* root, int value) {26 // Walk down: smaller goes left, larger goes right27 while (root != NULL) {28 if (value == root->value) return true;29 root = value < root->value ? root->left : root->right;30 }31 return false;32}33
34void inorder(const Node* node) {35 if (node == NULL) return;36 inorder(node->left);37 printf("%d ", node->value);38 inorder(node->right);39}40
41int main(void) {42 int values[] = {50, 30, 70, 20, 40, 60, 80};43 Node* root = NULL;44 for (int i = 0; i < 7; i++) root = insert(root, values[i]);45 printf("Sorted: ");46 inorder(root);47 printf("\n");48 printf("contains(40): %s\n", contains(root, 40) ? "true" : "false");49 printf("contains(45): %s\n", contains(root, 45) ? "true" : "false");50 return 0;51}FAQ Binary Search Tree
Berapa kompleksitas waktu binary search tree?
Pencarian, penyisipan, dan penghapusan bernilai
O(log n) pada pohon yang seimbang, karena setiap perbandingan membuang separuh node yang tersisa. Pada kasus terburuk, yaitu pohon yang miring menjadi rantai akibat penyisipan data terurut, semuanya merosot menjadi O(n).Apa perbedaan binary tree dan binary search tree?
Binary tree adalah pohon apa pun yang setiap node-nya memiliki paling banyak dua anak, tanpa aturan urutan. Binary search tree menambahkan aturan tetap bahwa nilai di subtree kiri lebih kecil dan nilai di subtree kanan lebih besar daripada node itu, dan aturan inilah yang memungkinkan pencarian cepat.
Mengapa binary search tree bisa menjadi lambat?
Jika nilai disisipkan dalam urutan terurut (atau terurut terbalik), setiap node baru masuk ke sisi yang sama, sehingga terbentuk pohon tinggi dan miring yang berperilaku seperti linked list, yaitu
O(n) per operasi. Pohon yang menyeimbangkan diri (AVL, red-black) merotasi node untuk mencegah hal ini.Apa perbedaan binary search tree dan hash table?
Hash table memberi pencarian rata-rata
O(1), tetapi menyimpan key tanpa urutan tertentu, sehingga tidak bisa menjawab range query atau query successor. Binary search tree sedikit lebih lambat dengan O(log n), tetapi menjaga key tetap berurutan, sehingga kamu bisa menelusurinya secara terurut dan menemukan nilai terdekat. Pilih BST saat urutan penting dan hash table saat kamu hanya butuh pengecekan keanggotaan.Kapan sebaiknya memakai pohon yang menyeimbangkan diri, bukan BST biasa?
Pakai pohon yang menyeimbangkan diri (AVL, red-black) setiap kali kamu tidak bisa mengendalikan urutan penyisipan dan butuh performa
O(log n) yang terjamin. BST biasa cocok untuk belajar, untuk data kecil, atau saat key datang dalam urutan acak, tetapi tidak memberi perlindungan terhadap kasus terburuk yang miring.Apakah penelusuran in-order pada BST menghasilkan nilai terurut?
Ya. Mengunjungi subtree kiri, lalu node, lalu subtree kanan menghasilkan key dalam urutan naik, dan ini langsung mengikuti aturan BST. Kesalahan yang umum adalah mengharapkan hal yang sama dari binary tree biasa: tanpa aturan urutan, penelusuran in-order tidak menghasilkan urutan yang bermakna.
Sumber terkait
Visualisasi lainnya
