Binary Tree (Pohon Biner)
Terakhir diperbarui
Binary tree adalah struktur bertingkat yang setiap node-nya memiliki paling banyak dua anak, yang disebut anak kiri dan anak kanan. Node paling atas disebut root, node tanpa anak disebut leaf (daun), dan jumlah edge dari root ke leaf terdalam adalah tinggi pohon. Tidak seperti binary search tree, binary tree biasa tidak punya aturan urutan: yang penting hanya bentuknya. Tekan Putar di atas untuk melihat pohon terisi level demi level, lalu ditelusuri secara in-order (kiri, node, kanan).
Binary tree menjadi dasar banyak struktur lain: binary search tree, heap, expression tree, dan masih banyak lagi. Penelusuran (traversal) mengunjungi setiap node dalam urutan tertentu: in-order, pre-order, dan post-order adalah tiga penelusuran depth-first, masing-masing berguna untuk tugas yang berbeda.
Istilah
| Istilah | Arti |
|---|---|
| Root (akar) | Node paling atas, tanpa induk |
| Leaf (daun) | Node tanpa anak |
| Tinggi (height) | Jalur terpanjang dari root ke leaf (dalam edge) |
| Kedalaman (depth) | Jarak sebuah node dari root |
| Complete (lengkap) | Semua level penuh kecuali mungkin level terakhir, yang diisi dari kiri ke kanan |
Tiga penelusuran depth-first
| Penelusuran | Urutan | Kegunaan umum |
|---|---|---|
| In-order | Kiri, node, kanan | Output terurut dari BST |
| Pre-order | Node, kiri, kanan | Menyalin / menserialisasi pohon |
| Post-order | Kiri, kanan, node | Menghapus / mengevaluasi pohon |
Contoh penerapan
Penelusuran in-order pada pohon yang dibangun dari [4, 2, 6, 1, 3, 5] (diisi level demi level):
| Langkah | Di node | Aksi |
|---|---|---|
| 1 | 4 | Masuk secara rekursif ke subtree kiri 4 sebelum mengunjunginya |
| 2 | 2 | Masuk secara rekursif ke subtree kiri 2 sebelum mengunjunginya |
| 3 | 1 | Leaf, tanpa anak kiri: kunjungi 1, output [1] |
| 4 | 2 | Kiri selesai: kunjungi 2, output [1, 2], lalu masuk ke kanan |
| 5 | 3 | Leaf: kunjungi 3, output [1, 2, 3] |
| 6 | 4 | Subtree kiri selesai: kunjungi 4, output [1, 2, 3, 4], lalu masuk ke kanan |
| 7 | 5 | Anak kiri 6, sebuah leaf: kunjungi 5, output [1, 2, 3, 4, 5] |
| 8 | 6 | Kiri selesai, tanpa anak kanan: kunjungi 6, output [1, 2, 3, 4, 5, 6] |
Kapan memakai binary tree
| Pakai saat | Hindari saat |
|---|---|
| Kamu perlu memodelkan data yang memang bertingkat (sistem file, expression tree, DOM) | Datanya datar dan list atau array sudah cukup: pohon hanya menambah beban |
| Kamu ingin operasi berurutan dan bisa menjaga pohon tetap seimbang (BST atau pohon yang menyeimbangkan diri) | Kamu butuh pencarian rata-rata O(1) berdasarkan key: hash table mengalahkan pohon apa pun |
| Kamu perlu memproses data terstruktur secara in-order, pre-order, atau post-order | Node disisipkan dalam urutan terurut ke BST yang tidak seimbang: pohon itu merosot menjadi list O(n) |
| Range query atau iterasi berurutan penting, dan hash table tidak bisa memberikannya | Memori terbatas: setiap node membawa dua pointer anak ditambah datanya |
Kode Binary Tree
Implementasi Binary Tree yang rapi dan siap dijalankan dalam Python, JavaScript, Java, C++, C. Pilih bahasa, salin kodenya, atau buka langsung di Coddy Playground.
Kode Binary Tree dalam Python
Python
1from collections import deque2
3
4class Node:5 def __init__(self, value):6 self.value = value7 self.left = None8 self.right = None9
10
11def insert(root, value):12 # Level-order insert: fill the first empty child slot found13 if root is None:14 return Node(value)15 queue = deque([root])16 while queue:17 node = queue.popleft()18 if node.left is None:19 node.left = Node(value)20 return root21 queue.append(node.left)22 if node.right is None:23 node.right = Node(value)24 return root25 queue.append(node.right)26
27
28def inorder(node):29 if node is None:30 return []31 return inorder(node.left) + [node.value] + inorder(node.right)32
33
34root = None35for value in [1, 2, 3, 4, 5, 6, 7]:36 root = insert(root, value)37
38print("Root: ", root.value)39print("Inorder:", inorder(root))Kode Binary 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 BinaryTree {10 constructor() {11 this.root = null;12 }13
14 // Insert at the first free spot, top to bottom (level order)15 insert(value) {16 const node = new Node(value);17 if (!this.root) {18 this.root = node;19 return;20 }21 const queue = [this.root];22 while (queue.length > 0) {23 const current = queue.shift();24 if (!current.left) {25 current.left = node;26 return;27 }28 if (!current.right) {29 current.right = node;30 return;31 }32 queue.push(current.left, current.right);33 }34 }35
36 inorder(node = this.root, out = []) {37 if (!node) return out;38 this.inorder(node.left, out);39 out.push(node.value);40 this.inorder(node.right, out);41 return out;42 }43}44
45const tree = new BinaryTree();46for (const value of [1, 2, 3, 4, 5, 6, 7]) tree.insert(value);47console.log("Inorder traversal:", tree.inorder().join(" "));Kode Binary Tree dalam Java
Java
1import java.util.ArrayDeque;2import java.util.Queue;3
4public class Main {5 static class Node {6 int value;7 Node left, right;8 Node(int value) { this.value = value; }9 }10
11 static Node root;12
13 // Insert at the first free slot in level order (keeps the tree complete)14 static void insert(int value) {15 Node node = new Node(value);16 if (root == null) { root = node; return; }17 Queue<Node> queue = new ArrayDeque<>();18 queue.add(root);19 while (!queue.isEmpty()) {20 Node cur = queue.poll();21 if (cur.left == null) { cur.left = node; return; }22 if (cur.right == null) { cur.right = node; return; }23 queue.add(cur.left);24 queue.add(cur.right);25 }26 }27
28 // Inorder: left subtree, node, right subtree29 static void inorder(Node node, StringBuilder sb) {30 if (node == null) return;31 inorder(node.left, sb);32 sb.append(node.value).append(" ");33 inorder(node.right, sb);34 }35
36 public static void main(String[] args) {37 for (int v = 1; v <= 7; v++) insert(v);38 StringBuilder sb = new StringBuilder();39 inorder(root, sb);40 System.out.println("Root: " + root.value);41 System.out.println("Inorder: " + sb.toString().trim());42 }43}Kode Binary 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 root->right = insert(root->right, value);14 return root;15}16
17// In-order traversal: left subtree, node, right subtree18void inorder(const Node* node) {19 if (node == nullptr) return;20 inorder(node->left);21 std::cout << node->value << " ";22 inorder(node->right);23}24
25int countNodes(const Node* node) {26 if (node == nullptr) return 0;27 return 1 + countNodes(node->left) + countNodes(node->right);28}29
30int main() {31 Node* root = nullptr;32 for (int value : {8, 3, 10, 1, 6, 14, 4}) {33 root = insert(root, value);34 }35 std::cout << "In-order: ";36 inorder(root);37 std::cout << "\n";38 std::cout << "Node count: " << countNodes(root) << "\n";39 return 0;40}Kode Binary Tree dalam C
C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5 int value;6 struct Node* left;7 struct Node* right;8} Node;9
10Node* newNode(int value) {11 Node* n = malloc(sizeof(Node));12 n->value = value;13 n->left = n->right = NULL;14 return n;15}16
17Node* insert(Node* root, int value) {18 if (root == NULL) return newNode(value);19 if (value < root->value) root->left = insert(root->left, value);20 else root->right = insert(root->right, value);21 return root;22}23
24// In-order traversal: left subtree, node, right subtree25void inorder(const Node* node) {26 if (node == NULL) return;27 inorder(node->left);28 printf("%d ", node->value);29 inorder(node->right);30}31
32int countNodes(const Node* node) {33 if (node == NULL) return 0;34 return 1 + countNodes(node->left) + countNodes(node->right);35}36
37int main(void) {38 int values[] = {8, 3, 10, 1, 6, 14, 4};39 Node* root = NULL;40 for (int i = 0; i < 7; i++) root = insert(root, values[i]);41 printf("In-order: ");42 inorder(root);43 printf("\n");44 printf("Node count: %d\n", countNodes(root));45 return 0;46}FAQ Binary Tree
Apa perbedaan binary tree dan binary search tree?
Binary tree hanya membatasi setiap node agar memiliki paling banyak dua anak, tanpa urutan. Binary search tree menambahkan aturan bahwa semua yang ada di subtree kiri lebih kecil dan semua yang ada di subtree kanan lebih besar, dan aturan inilah yang membuat pencarian cepat.
Apa itu penelusuran in-order?
Penelusuran in-order mengunjungi subtree kiri, lalu node, lalu subtree kanan, secara rekursif. Pada binary search tree, penelusuran ini menghasilkan nilai dalam urutan naik, itulah sebabnya penelusuran ini paling sering dipakai sebagai contoh.
Apa itu complete binary tree?
Complete binary tree adalah pohon yang setiap levelnya terisi penuh kecuali mungkin level terakhir, yang diisi dari kiri ke kanan. Bentuk ini memungkinkan pohon disimpan secara ringkas di dalam array (tanpa perlu pointer anak), dan begitulah binary heap diimplementasikan.
Kapan sebaiknya memakai binary tree, bukan array atau hash table?
Pakai pohon saat datamu memang bertingkat atau saat kamu butuh operasi berurutan seperti range query dan iterasi terurut, yang tidak bisa diberikan hash table. Jika kamu hanya butuh pencarian key yang cepat tanpa urutan, akses rata-rata
O(1) milik hash table mengalahkan pohon, dan untuk data yang datar, array lebih sederhana dan lebih ramah cache.Apa perbedaan tinggi dan kedalaman pada binary tree?
Kedalaman diukur dari root turun ke node tertentu, yaitu jumlah edge pada jalur dari root ke node itu. Tinggi diukur dari sebuah node turun ke leaf terdalamnya, jadi tinggi seluruh pohon sama dengan kedalaman node terdalamnya. Pohon dengan satu node memiliki tinggi
0, dan satu-satunya node itu juga memiliki kedalaman 0.Mengapa binary tree yang tidak seimbang berkinerja sangat buruk?
Pencarian, penyisipan, dan penghapusan pada binary search tree berbiaya
O(h), dengan h adalah tinggi pohon. Saat key disisipkan dalam urutan terurut, pohon menjadi garis lurus, sehingga h tumbuh menjadi n dan setiap operasi merosot menjadi O(n), tidak lebih baik daripada linked list. Pohon yang menyeimbangkan diri seperti AVL tree atau red-black tree menjaga tinggi di O(log n) untuk mencegah hal ini.Sumber terkait
Visualisasi lainnya
