Dalam istilah ilmu komputer, struktur data adalah cara menyimpan dan mengatur data secara terstruktur pada sistem komputer atau pangkalan data (database) sehingga lebih mudah diakses. Secara teknis, data dalam bentuk angka, huruf, simbol, dan lainnya ini diletakkan dalam kolom-kolom dan susunan tertentu. Contoh struktur data dapat dilihat pada berkas-berkas spreadsheet, database, pengolah kata, compressed image, dan compressed file dengan teknik tertentu yang memanfaatkan struktur data. Urutan dalam menyusun elemen data akan sangat menentukan apakah elemen data yang hendak diakses dapat diproses dalam waktu yang lebih singkat dan mudah atau tidak.
Elemen data yang disusun secara berurutan dimana setiap elemen saling berdekatan antara satu elemen dengan elemen lain disebut sebagai struktur data linier. Contohnya seperti array, linked list, stack, dan queue.
Selain struktur data linier, ada juga struktur data nonlinier, yaitu merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Struktur data Non-linear dapat dibangun sebagai kumpulan acak set item data digabungkan dengan menggunakan pointer khusus (tag), salah satunya adalah tree.
Pengertian Struktur Data Tree
Tree/pohon merupakan struktur data yang tidak linear/non linear yang digunakan terutama untuk merepresentasikan hubungan data yang bersifat hierarkis antara elemen-elemennya.
Mengapa tree disebut sebagai struktur data non-linier? Alasannya karena data pada tree tidak disimpan secara berurutan. Sebaliknya, data diatur pada beberapa level yang disebut struktur hierarkis. Karena itu, tree dianggap sebagai struktur data non-linear.
Hierarki pada struktur tree dapat diibaratkan seperti sebuah pohon keluarga di mana terdapat hubungan antara orang tua dan anak. Titik yang lebih atas disebut simpul induk sedangkan simpul di bawahnya adalah simpul anak.
Struktur data tree terdiri atas kumpulan simpul atau node dimana tiap-tiap simpul dari tree digunakan untuk menyimpan nilai dan sebuah list rujukan ke simpul lain yang disebut simpul anak atau child node.
Tiap-tiap simpul dari tree akan dihubungkan oleh sebuah garis hubung yang dalam istilah teknis disebut edge. Biasanya diimplementasikan menggunakan pointer.
Simpul pada tree bisa memiliki beberapa simpul anak (child node). Namun, jalan menuju sebuah child node hanya bisa dicapai melalui maksimal 1 node. Apabila sebuah node atau simpul tidak memiliki child node sama sekali maka dinamakan leaf node.
Struktur data ini adalah metode khusus untuk mengatur dan menyimpan data di komputer agar dapat digunakan secara lebih efektif.
Jenis tree yang paling umum digunakan adalah Binary Tree, dimana sebuah tree memiliki maksimal 2 child node.
Istilah-istilah pada Tree
Layaknya sebuah pohon yang memiliki akar, cabang, dan daun yang terhubung satu sama lain, pada struktur data tree terdapat beberapa istilah penting yang mirip seperti istilah di dunia nyata, antara lain:
1. Node
Node atau simpul adalah entitas pada struktur data tree yang mengandung sebuah nilai dan pointer yang menunjuk simpul di bawahnya (child node).
2. Predesesor
Node yang berada diatas node tertentu. Contoh dalam gambar di atas : B adalah predesesor dari D dan E.
3. Succesor
Node yang berada dibawah node tertentu. Contoh dalam gambar di atas : D dan E adalah succesor dari B.
4. Ancestor
Seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama. Contoh dalam gambar di atas : A dan B adalah ancestor dari E.
5. Descendant
Seluruh node yang terletak setelah node tertentu dan terletak pada jalur yang sama. Contoh dalam gambar di atas : B dan E adalah descendant dari A.
6. Parent
Predesesor satu level di atas satu node. Contoh dalam gambar di atas : B adalah parent dari E.
7. Child
Succesor satu level di bawah satu node. Contoh dalam gambar di atas : E adalah child dari B.
8. Sibling
Node yang memiliki parent yang sama dengan satu node. Contoh dalam gambar di atas : D dan E adalah sibling.
9. Subtree
Bagian dari tree yang berupa suatu node beserta descendant-nya. Contoh dalam gambar di atas : C, F, G.
10. Size
Banyaknya node dalam suatu tree. Contoh dalam gambar di atas : Sizenya adalah 8.
11. Height
Banyaknya tingkat/level pada suatu tree. Contoh dalam gambar di atas : 4 (level 0, level 1, level 2, dan level 3).
12. Leaf Node
Leaf node atau simpul daun adalah simpul yang tidak memiliki child node dan merupakan node yang paling bawah dalam struktur data tree. Simpul ini biasa disebut juga sebagai external node.
13. Root
Root atau akar adalah simpul teratas dari sebuah tree atau node yang tidak memiliki predesesor.
14. Degree (Derajat)
Banyaknya child yang dimiliki oleh suatu node.
15. Internal node
Internal node adalah istilah untuk menyebut simpul yang memiliki minimal satu child node.
16. Edge
Edge merujuk pada garis yang menghubungkan antara dua buah simpul dalam tree. Jika sebuah tree memiliki N node maka tree tersebut akan memiliki (N-1) edge. Hanya ada satu jalur dari setiap simpul ke simpul lainnya.
Karakteristik Tree
Adapun karakteristik dari struktur data tree adalah sebagai berikut:
- Penjelahan data (traversing) pada tree dilakukan oleh algoritma Depth First Search dan Breadth First Search
- Tidak ada loop dan circuit
- Tidak memiliki self-loop
- Disusun dalam model hierarki
Sifat Utama Tree
Sifat utama dari struktur data tree adalah sebagai berikut:
- Jika Pohon mempunyai simpul sebanyak n, maka banyaknya ruas atau edge adalah (n-1).
- Mempunyai simpul khusus yang disebut Root, jika simpul tersebut memiliki derajat keluar >= 0, dan derajat masuk = 0.
- Mempunyai simpul yang disebut sebagai Daun/Leaf, jika simpul tersebut berderajat keluar = 0, dan berderajat masuk = 1.
- Setiap Simpul mempunyai Tingkatan/Level yang dimulai dari Root yang Levelnya = 1 sampai dengan Level ke-n pada daun paling bawah. Simpul yang mempunyai Level sama disebut Bersaudara atau Brother atau Stribling.
- Pohon mempunyai Ketinggian atau Kedalaman atau Height, yang merupakan Level tertinggi.
- Pohon mempunyai Weight atau Berat atau Bobot, yang banyaknya daun (leaf) pada Pohon.
- Banyaknya Simpul Maksimum sampai Level N adalah : 2(n) – 1
- Banyaknya Simpul untuk setiap Level I adalah :
N
Σ 2(I–1)
I=1 - Hutan (Forest) adalah kumpulan Pohon yang tidak saling berhubungan.
Jenis-jenis Tree
Struktur data tree dapat diklasifikasikan ke dalam 4 jenis, yaitu: General tree, Binary tree, Balanced tree, dan Binary search tree.
1. General tree
Struktur data tree yang tidak memiliki batasan jumlah node pada hierarki tree disebut General tree. Setiap simpul atau node bebas memiliki berapapun child node. Tree jenis adalah superset dari semua jenis tree.
2. Binary tree
Binary tree adalah jenis tree yang simpulnya hanya dapat memiliki paling banyak 2 simpul anak (child node). Kedua simpul tersebut biasa disebut simpul kiri (left node) dan simpul kanan (right node). Tree tipe ini lebih populer daripada jenis lainnya.
3. Balanced tree
Apabila tinggi dari subtree sebelah kiri dan subtree sebelah kanan sama atau kalaupun berbeda hanya berbeda 1, maka disebut sebagai balanced tree.
4. Binary search tree
Sesuai dengan namanya, Binary search tree digunakan untuk berbagai algoritma pencarian dan pengurutan. Contohnya seperti AVL tree dan Red-black tree. Struktur data tree jenis ini memiliki nilai pada simpul sebelah kiri lebih kecil daripada induknya. Sedangkan nilai simpul sebelah kanan lebih besar dari induknya.
Fungsi dan Kegunaan Tree
Berikut adalah fungsi dan kegunaan dari struktur data tree
- Dalam kehidupan nyata, struktur data tree membantu dalam pengembangan game.
- Membantu pengindeksan pada database.
- Decision Tree adalah tools yang biasanya digunakan dalam analisis keputusan. Metode ini memiliki struktur seperti diagram alur yang membantu untuk memahami data.
- Domain Name Server juga menggunakan struktur data tree.
- Kasus penggunaan tree yang paling umum adalah situs jejaring sosial, seperti Facebook, Instagram, Twitter, dll.
Keunggulan Strukur Data Tree
Berikut adalah beberapa keunggulan atau kelebihan dari tree:
- Memungkinan subtree untuk dipindahkan dengan usaha yang minim.
- Mencerminkan hubungan data secara struktural.
- Menawarkan operasi pencarian dan penyisipan yang efisien.
- Tree sangat baik digunakan untuk membuat hierarki data.
Penutup
Demikianlah penjelasan lengkap mengenai struktur data tree. Semoga bermanfaat.
Referensi:
