Tree Data Structure

1. Tree Data Structure

Tree data structure merupakan struktur data yang bersifat non-linear yang menggambarkan bentuk dari hierarki antara elemen dengan elemen. Tree biasanya berisi root dan node - node yang berada di bawah root.

Tree structure data biasanya digunakan untuk merepresentasikan data dengan hierarki seperti struktur direktori pada sistem operasi atau representasi sintaksis dalam bahasa pemrograman. Tree structure juga dapat digunakan untuk menyelesaikan masalah terkait dengan pencarian, pengurutan, dan filtering. Beberapa contoh aplikasi tree structure adalah dalam pembuatan struktur database, pengimplementasian algoritma seperti binary search tree, AVL tree. Berikut adalah komponen utama dalam tree data structure:

1.    Node (simpul): Merupakan elemen dasar dalam tree yang menyimpan nilai atau informasi tertentu.

2.    Edge (cabang): Merupakan koneksi antara dua simpul dalam tree.

3.    Root node (simpul akar): Merupakan simpul teratas dalam tree yang tidak memiliki parent.

4.    Child node (simpul anak): Merupakan simpul yang terhubung langsung dengan simpul parent.

5.    Parent node (simpul induk): Merupakan simpul yang terhubung langsung dengan simpul anak.

Pada dasarnya, tree data structure ini memiliki berbagai macam jenis dengan karakteristik masing - masing, diantaranya:

1.    Binary Tree

Pada binary tree setiap simpul di dalam binary tree memiliki maksimal dua anak simpul, yaitu right child dan left child. Pengaplikasian dari binary tree biasanya digunakan untuk binary search tree.

2.    Binary Search Tree

Binary search tree memiliki sifat bahwa nilai dari semua left child harus lebih kecil daripada nilai dari right child dan parentnya. Binary search tree digunakan untuk mempercepat pencarian data.

3.    AVL Tree

AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.

2. Tree Traversal

Pada tree structure data terdapat tiga metode traversal yang biasanya digunakan, yaitu:

1.    Pre-order traversal

Pada pre-order traversal, dimulai dari simpul root lalu melakukan perpindahan ke subtree B, setelah selesai melakukan pre-order traversal di subtree B, dilanjutkan melakukan pre-order traversal di subtree C. lebih jelasnya path yang dilalui oleh pre-order traversal ialah A > B > D > E > C > F > G atau Urutan traversal pre-order adalah root - anak kiri - anak kanan.

2.    In-order traversal

Pada in-order traversal, dimulai dari melakukan in-order traversal left subtree lalu melakukan perpindahan ke root, kemudian melakukan in-order traversal di right subtree. hasil dari in-order traversal ini ialah D > B > E > A > F > C > G atau Urutan traversal in-order adalah anak kiri - root - anak kanan. in-order traversal akan menghasilkan elemen-elemen dalam urutan terurut menaik.

3.    Post-order traversal

Pada post-order traversal, dimulai dari melakukan post-order traversal left subtree lalu melakukan perpindahan post-order traversal ke right subtree, kemudian melakukan perpindahan ke root. hasil dari in-order traversal ini ialah D > E > B > F > G > C > A atau Urutan traversal post-order adalah anak kiri - anak kanan - root. post-order traversal sering digunakan dalam operasi pembebasan memori karena simpul daun dikunjungi terlebih dahulu

3. Spanning Tree

Spanning tree merupakan sebuah graph tak berarah yang menghubungkan semua simpul dalam graph tanpa membentuk sebuah siklus. Lebih jelasnya spanning tree adalah sebuah graph yang mempertahankan semua simpul dalam graph asli, akan tetapi tetap menghilangkan beberapa sisi untuk menghindari pembentukan siklus.

Pada contoh diatas dapat dilihat bahwa spanning tree tetap mempertahankan bentuk simpulnya serta menghilangkan beberapa sisi sehingga tidak terciptanya sebuah siklus dalam spanning tree.