🌳 Pengertian Struktur Data Tree
Tree adalah struktur non-linier yang menyusun data secara hierarkis menggunakan simpul (nodes) yang saling terhubung lewat cabang (edges). Ada satu simpul utama yang disebut root, dan setiap simpul bisa memiliki anak (child), tapi hanya satu induk (parent) (bds.telkomuniversity.ac.id). Model seperti ini cocok menggambarkan hubungan satu-ke-banyak cabang.
⚙️ Jenis‑jenis Tree
-
General Tree
Setiap node bisa punya banyak anak. Tidak ada batasan jumlah cabang, cocok untuk struktur yang lebih fleksibel (trivusi.web.id). -
Binary Tree
Tiap node paling banyak memiliki dua anak: anak kiri dan anak kanan. Struktur yang sederhana tapi sangat berguna (trivusi.web.id). -
Binary Search Tree (BST)
Versi khusus Binary Tree dengan aturan:-
Anak kiri berisi nilai yang lebih kecil daripada induk.
-
Anak kanan berisi nilai lebih besar.
Aturan ini mempercepat operasi pencarian, penyisipan, dan penghapusan data (Wikipedia, bds.telkomuniversity.ac.id).
-
-
Balanced Tree
Tree yang dibuat agar tingginya di kiri dan kanan hampir sama (selisih paling banyak 1), sehingga operasi tetap cepat. AVL Tree dan Red‑Black Tree adalah contohnya (bds.telkomuniversity.ac.id).
✨ Istilah Penting dalam Tree
-
Root: simpul paling atas, tidak punya parent.
-
Parent / Child: induk dan anak; child berasal dari parent, dan satu child punya satu parent.
-
Leaf (Daun): simpul yang tidak punya anak.
-
Internal Node: simpul yang punya sedikitnya satu anak.
-
Subtree: pohon kecil yang mulai dari satu simpul dan seluruh keturunannya.
-
Edge: garis penghubung antar node—jika ada N node, biasanya ada N−1 edge.
-
Depth (Kedalaman): jumlah edge dari root menuju suatu node tertentu.
-
Height (Tinggi): panjang jalur terpanjang dari root ke leaf paling bawah.
-
Degree: jumlah anak pada suatu node; degree tree = nilai maksimum across semua node (Wikipedia).
🔄 Operasi Utama pada Tree
-
Traversal: cara mengunjungi semua simpul secara sistematis:
-
Preorder: root → kiri → kanan
-
Inorder: kiri → root → kanan
-
Postorder: kiri → kanan → root
-
Level‑order: dari atas ke bawah mengikuti tingkat level (bds.telkomuniversity.ac.id)
-
-
Pencarian (Search): mencari nilai tertentu di dalam tree paling efisien pada BST.
-
Penyisipan (Insert): menambahkan node baru, dengan memperhatikan aturan struktur yang digunakan (misalnya aturan BST).
-
Penghapusan (Delete): menghapus node tanpa merusak aturan tree.
-
Pengukuran spesifik: menentukan tinggi tree, kedalaman node, dan lain‑lain (Wikipedia).
💡 Aplikasi Struktur Data Tree
Tree banyak digunakan karena bisa merepresentasikan hierarki secara jelas. Contohnya:
-
Struktur folder / file di sistem komputer
-
Pohon keputusan (decision tree) di kecerdasan buatan
-
Parse tree dalam compiler bahasa pemrograman
-
Database indexing seperti di search engine
-
DOM di HTML/XML, autocompletion dengan Trie
-
Struktur organisasi, klasifikasi data, dan lainnya (bds.telkomuniversity.ac.id, bds.telkomuniversity.ac.id)
✅ Kelebihan & ⚠️ Kekurangan Tree
Kelebihan:
-
Menyimpan data berhirarki dengan efisien
-
Akses data cepat terutama jika struktur tree seimbang
-
Cocok untuk berbagai bentuk data yang berstruktur
Kekurangan:
-
Algoritma seperti penghapusan node atau menjaga keseimbangan bisa rumit
-
Memerlukan memori tambahan untuk referensi ke anak-anak
-
Jika tree tidak seimbang (misalnya semua node hanya di satu sisi), operasi pencarian bisa jadi lambat seperti O(n) (trivusi.web.id, dibimbing.id)
📌 Ringkasan Singkat
| Aspek | Penjelasan Singkat |
|---|---|
| Apa itu Tree? | Struktur hierarki dengan root dan node-node terhubung |
| Contoh Tree | Binary Tree, BST, Balanced Tree, Trie, N-ary tree |
| Istilah Umum | Root, parent, child, leaf, subtree, depth, height, degree |
| Operasi Dasar | Traversal, pencarian, penyisipan, penghapusan |
| Aplikasi | File system, kamus digital, AI, database, compiler, dll |
| Kelebihan | Efisien penyimpanan & pencarian data |
| Kekurangan | Implementasi rumit & bisa berat memori jika tidak seimbang |
🧩 Skenario Masalah: Pohon Keluarga Sederhana
🧑👩👧👦 Cerita:
Keluarga Andi memiliki struktur keluarga seperti ini:
-
Kakek bernama Pak Budi
-
Memiliki dua anak: Ibu Sari dan Om Deni
-
Ibu Sari punya dua anak: Andi dan Rina
-
Om Deni punya satu anak: Tono
-
-
Andi sedang belajar informatika dan ingin menyusun struktur pohon keluarga mereka menggunakan struktur data Tree. Ia ingin tahu siapa saja:
- Root dari pohon keluarganya?
- Siapa saja yang termasuk daun (leaf)?
- Bagaimana cara membaca nama-nama keluarga itu dengan metode preorder traversal?