Petualangan Struktur Pohon

Edukasi Struktur Diskrit - Konsep dan Aplikasi Pohon dalam Ilmu Komputer

Materi Pembelajaran Pohon

Pelajari konsep dasar struktur pohon, terminologi lengkap, jenis-jenis pohon, dan aplikasinya dalam ilmu komputer.

Konsep Dasar Struktur Pohon

Pohon adalah struktur data non-linear yang terdiri dari simpul-simpul (nodes) yang terhubung oleh sisi (edges). Struktur ini menyerupai pohon terbalik dengan akar di atas dan daun di bawah.

Analogi: Struktur pohon mirip dengan struktur organisasi perusahaan, di mana CEO adalah root, manajer adalah internal nodes, dan staf adalah leaf nodes.

12 Terminologi Penting dalam Struktur Pohon

Root (Akar)

Simpul paling atas yang tidak memiliki parent. Merupakan titik awal dari seluruh struktur pohon.

Contoh: Dalam struktur folder komputer, drive C: adalah root.

Parent (Orangtua)

Simpul yang memiliki anak. Setiap simpul kecuali root memiliki tepat satu parent.

Contoh: Folder yang berisi subfolder adalah parent dari subfolder tersebut.

Child (Anak)

Simpul yang memiliki parent. Sebuah simpul dapat memiliki nol, satu, atau lebih child.

Contoh: Subfolder adalah child dari folder induknya.

Leaf (Daun)

Simpul tanpa anak (derajat keluar = 0). Juga disebut sebagai simpul terminal.

Contoh: File dalam struktur folder adalah leaf karena tidak memiliki subfolder.

Internal Node

Simpul yang memiliki setidaknya satu anak. Semua simpul kecuali leaf adalah internal node.

Contoh: Manager dalam perusahaan yang memiliki bawahan adalah internal node.

Depth (Kedalaman)

Jarak dari root ke simpul tertentu. Root memiliki depth = 0.

Contoh: Jika root adalah level 0, child-nya adalah level 1 (depth = 1).

Height (Tinggi)

Jarak maksimum dari root ke leaf terjauh. Tinggi pohon dengan satu node (root) adalah 0.

Contoh: Pohon dengan 3 level memiliki height = 2.

Degree (Derajat)

Jumlah anak yang dimiliki sebuah simpul. Leaf memiliki degree = 0.

Contoh: Node dengan 3 anak memiliki degree = 3.

Sibling (Saudara)

Simpul-simpul yang memiliki parent yang sama.

Contoh: Dua subfolder dalam folder yang sama adalah sibling.

Path (Jalur)

Urutan simpul yang menghubungkan dua simpul melalui sisi-sisi yang berurutan.

Contoh: Root → Parent → Child adalah sebuah path.

Level (Tingkat)

Generasi simpul dalam pohon. Root berada di level 0, anak-anaknya di level 1, dan seterusnya.

Contoh: Dalam struktur organisasi, direktur (level 0), manajer (level 1), staf (level 2).

Subtree (Subpohon)

Sebuah simpul beserta semua keturunannya membentuk subtree.

Contoh: Departemen dalam perusahaan adalah subtree dari struktur organisasi perusahaan.

Visualisasi Struktur Pohon Interaktif

Klik pada simpul untuk melihat penjelasan terminologi. Diagram menunjukkan struktur pohon dengan berbagai jenis simpul. Root berwarna cyan, parent berwarna magenta, child berwarna hijau, dan leaf berwarna kuning.

Klasifikasi Jenis-Jenis Pohon

Dalam ilmu komputer, terdapat berbagai jenis pohon yang diklasifikasikan berdasarkan sifat dan karakteristiknya. Setiap jenis memiliki aplikasi yang spesifik.

Binary Tree

Pohon di mana setiap simpul memiliki maksimal 2 anak (left child dan right child).

Contoh Visual: Digunakan dalam binary search trees untuk pencarian efisien.

Binary Search Tree (BST)

Binary tree dengan properti: semua simpul di subtree kiri lebih kecil dari root, dan semua simpul di subtree kanan lebih besar.

Contoh Visual: Implementasi dictionary atau phone book dengan pencarian O(log n).

AVL Tree

Self-balancing binary search tree dengan perbedaan tinggi subtree kiri dan kanan maksimal 1.

Contoh Visual: Database indexing untuk menjaga performa optimal.

Red-Black Tree

Self-balancing binary search tree dengan properti warna (merah/hitam) untuk menjaga keseimbangan.

Contoh Visual: Implementasi map dan set dalam C++ STL dan Java Collections.

B-Tree

Pohon seimbang dengan banyak anak, dirancang untuk sistem penyimpanan disk.

Contoh Visual: File systems (NTFS, ext4) dan database indexing (MySQL, PostgreSQL).

Heap

Binary tree lengkap yang memenuhi heap property (max-heap atau min-heap).

Contoh Visual: Priority queue, algoritma heap sort, dan algoritma Dijkstra.

Trie

Pohon pencarian untuk string, di mana setiap simpul merepresentasikan prefiks.

Contoh Visual: Autocomplete, spell checker, dan IP routing tables.

N-ary Tree

Pohon di mana setiap simpul dapat memiliki n anak (tidak terbatas 2 seperti binary tree).

Contoh Visual: Struktur folder sistem file, struktur organisasi perusahaan.

Perbandingan Visual Jenis-Jenis Pohon

Diagram menunjukkan perbandingan struktur berbagai jenis pohon: Binary Tree (kiri), B-Tree (tengah), dan Trie (kanan).

Aplikasi Struktur Pohon dalam Ilmu Komputer

Struktur pohon memiliki aplikasi yang luas dalam berbagai bidang ilmu komputer, dari sistem operasi hingga kecerdasan buatan.

Sistem File

Struktur direktori dan file dalam sistem operasi menggunakan pohon (N-ary tree).

Implementasi: Windows (NTFS), Linux (ext4), macOS (HFS+)

Database Indexing

B-Tree dan B+Tree digunakan untuk indexing dalam database untuk pencarian cepat.

Implementasi: MySQL, PostgreSQL, Oracle Database

Pencarian Data

Binary Search Tree (BST) dan AVL Tree untuk pencarian data dengan kompleksitas O(log n).

Implementasi: Dictionary, phone book, symbol tables

Sorting Algorithm

Heap Sort menggunakan struktur heap untuk sorting dengan kompleksitas O(n log n).

Implementasi: Heap sort algorithm, priority queues

Jaringan Komputer

Spanning Tree Protocol (STP) untuk mencegah loops dalam jaringan switch.

Implementasi: Ethernet networks, network bridges

Artificial Intelligence

Decision trees untuk klasifikasi dan regression dalam machine learning.

Implementasi: Decision tree algorithms, random forests

Compiler Design

Parse trees dan syntax trees untuk analisis sintaksis dalam compiler.

Implementasi: Abstract Syntax Trees (AST), parse trees

Game Development

Game trees untuk artificial intelligence dalam game (chess, tic-tac-toe).

Implementasi: Minimax algorithm, game AI

Visualisasi Aplikasi Pohon dalam Sistem File

Diagram menunjukkan struktur pohon sistem file dengan folder sebagai internal nodes dan file sebagai leaf nodes.

Quiz Evaluasi Pemahaman

Uji pemahaman Anda tentang struktur pohon dengan menjawab 5 pertanyaan berikut. Pilih jawaban yang paling tepat!

Skor: 0/100
Progress: 0/5
1
Apa yang dimaksud dengan "root" dalam struktur pohon?
A Simpul tanpa anak
B Simpul paling atas tanpa parent
C Simpul dengan derajat tertinggi
D Simpul dengan depth terbesar
2
Apa perbedaan antara "leaf" dan "internal node"?
A Leaf memiliki parent, internal node tidak
B Leaf selalu berada di level terendah
C Leaf tidak memiliki anak, internal node memiliki minimal satu anak
D Leaf adalah root, internal node adalah child
3
Dalam Binary Search Tree (BST), properti apa yang harus dipenuhi?
A Setiap simpul memiliki tepat 2 anak
B Tinggi subtree kiri dan kanan berbeda maksimal 1
C Setiap simpul memiliki warna merah atau hitam
D Semua simpul di subtree kiri lebih kecil dari root, dan semua simpul di subtree kanan lebih besar
4
Aplikasi struktur pohon MANAKAH yang menggunakan B-Tree?
A Database indexing
B Autocomplete text
C Game artificial intelligence
D Compiler syntax analysis
5
Apa yang dimaksud dengan "height" dari sebuah pohon?
A Jumlah total simpul dalam pohon
B Jarak maksimum dari root ke leaf terjauh
C Jumlah level dalam pohon
D Jumlah anak terbanyak yang dimiliki sebuah simpul