Pengantar Terminologi Tree dalam Struktur Data
Dalam struktur data, tree merupakan salah satu konsep fundamental yang digunakan untuk merepresentasikan data secara hierarkis. Terminologi tree sering kali membingungkan bagi pemula, padahal memahami istilah-istilah dasarnya sangat penting untuk menguasai algoritma pohon, mulai dari binary tree hingga trie. Artikel ini membahas secara mendalam terminologi tree beserta contoh implementasinya, sehingga Anda dapat memahami setiap konsep dengan lebih jelas dan terstruktur.
Komponen Dasar Tree
1. Node: Elemen Penyusun Dasar
Setiap tree tersusun dari sejumlah node. Node adalah unit data yang berisi nilai (value) dan referensi ke node lain. Dalam implementasi umum, sebuah node menyimpan:
- data atau key, yaitu nilai yang dipegang node.
- pointer atau reference ke anak kiri (left child).
- pointer ke anak kanan (right child) pada binary tree atau daftar referensi untuk pohon bertipe umum.
2. Akar (Root): Titik Mulai Hierarki
Akar, atau root, adalah node paling atas dalam tree. Root menjadi titik akses utama saat melakukan operasi seperti traversal, penambahan, atau penghapusan node. Karakteristik root:
- Tidak memiliki parent.
- Jika root null, tree dianggap kosong.
- Satu tree hanya punya satu root.
3. Daun (Leaf): Node Tanpa Anak
Daun atau leaf adalah node yang tidak memiliki anak (child). Leaf merupakan ujung dari setiap cabang tree. Pengenalan daun penting dalam perhitungan jumlah node, atau saat menerapkan algoritma pencarian untuk menentukan kondisi berhenti.
4. Tinggi (Height) dan Kedalaman (Depth)
Kedalaman (depth) sebuah node adalah jumlah tepi (edge) dari root ke node tersebut. Sedangkan tinggi (height) tree didefinisikan sebagai kedalaman maksimum di antara semua node, atau jarak terpanjang dari root ke leaf. Konsep ini krusial dalam menganalisis kompleksitas waktu operasi seperti pencarian dan penyisipan.
Istilah Penting dalam Tree
Subtree: Cabang Kecil dari Pohon
Sebuah subtree adalah bagian dari tree yang terdiri dari sebuah node dan semua keturunannya. Setiap node dapat dianggap sebagai root dari subtree-nya sendiri. Pemahaman subtree membantu dalam algoritma divide and conquer pada pohon.
Sibling: Saudara Selevel
Sibling adalah dua node yang memiliki parent yang sama. Misalnya, pada binary tree, anak kiri dan anak kanan dari suatu node merupakan sibling. Konsep ini sering digunakan dalam traversal untuk memeriksa kondisi lateral antar node.
Degree: Derajat Node
Degree (atau derajat) sebuah node adalah jumlah anak yang dimilikinya. Pada binary tree, derajat maksimal adalah 2, sedangkan pada general tree derajat bisa lebih besar. Analisis derajat membantu memilih jenis pohon yang cocok untuk kasus tertentu.
Path dan Ancestor/Descendant
Path adalah urutan node dan edge yang menghubungkan dua node di dalam tree. Node A disebut ancestor dari node B jika A berada di jalur (path) dari root hingga B. Sebaliknya, B disebut descendant dari A. Istilah ini penting dalam operasi seperti Lowest Common Ancestor (LCA).
Implementasi dan Contoh Penerapan Tree
Binary Tree: Struktur Dua Anak
Binary tree adalah pohon di mana setiap node memiliki paling banyak dua anak: kiri dan kanan. Operasi dasar pada binary tree meliputi:
- Traversal (preorder, inorder, postorder).
- Penambahan node.
- Penghapusan node.
- Pencarian nilai.
Binary tree cocok untuk aplikasi seperti ekspresi matematika dan representasi keputusan (decision tree).
Binary Search Tree (BST): Pencarian Efisien
Binary Search Tree (BST) memperluas binary tree dengan aturan: nilai pada anak kiri lebih kecil daripada parent, dan nilai pada anak kanan lebih besar. Properti ini memungkinkan operasi pencarian, penambahan, dan penghapusan dijalankan dalam average time complexity O(log n). Contoh penerapan BST termasuk database indexing dan struktur file sistem.
Heap: Pohon Lengkap dengan Properti Khusus
Heap adalah pohon biner lengkap yang memenuhi properti heap: setiap parent lebih besar (max-heap) atau lebih kecil (min-heap) daripada anak-anaknya. Heap umum digunakan dalam implementasi priority queue dan algoritma sort seperti heapsort.
Trie: Pohon Prefix untuk String
Trie adalah pohon khusus yang merepresentasikan himpunan string dengan memanfaatkan prefix. Setiap level pohon menyimpan karakter berikutnya, sehingga pencarian kata atau autocomplete dapat dilakukan secara efisien. Trie banyak dipakai dalam aplikasi kamus digital, mesin pencari, dan aplikasi jaringan.
Kesimpulan
Memahami terminologi tree adalah langkah awal yang penting untuk menguasai berbagai algoritma pohon dan aplikasinya dalam struktur data. Mulai dari pengenalan node, root, leaf, hingga istilah seperti subtree, sibling, dan degree, setiap konsep memberikan landasan teoritis untuk implementasi binary tree, BST, heap, atau trie. Dengan pemahaman yang mendalam, Anda dapat memilih struktur pohon yang tepat sesuai kebutuhan performa dan kompleksitas aplikasi.