TREE
Pengertian Struktur Data Tree
Tree adalah tipe Stuktur data yang sifatnya non-linear dan berbentuk hierarki.
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.
Struktur data tree, juga dikenal sebagai pohon, adalah struktur data yang digunakan untuk merepresentasikan hubungan hierarkis antara elemen-elemen data. Tree terdiri dari satu elemen khusus yang disebut root (akar) dan elemen-elemen lain yang disebut simpul (node/vertex).
Simpul-simpul ini terhubung satu sama lain dengan cara yang tidak saling berhubungan, membentuk subtree atau cabang.
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. Child node
Child node atau simpul anak adalah simpul turunan dari simpul di atasnya.
3. 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
4. Root
Root atau akar adalah simpul teratas dari sebuah tree.
5. Internal node
Internal node adalah istilah untuk menyebut simpul yang memiliki minimal satu child node.
6. 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.
7. Height of node
Height of node adalah jumlah edge dari sebuah node ke leaf node yang paling dalam.
8. Depth of node
Depth of node adalah banyaknya edge dari root ke sebuah node.
9. Height of tree
Height of tree dapat diartikan sebagai panjang jalur terpanjang dari simpul akar ke simpul daun dari seuah tree.
10. Degree of node
Jumlah cabang yang melekat pada simpul disebut Degree of node atau derajat simpul. Derajat simpul pada sebuah leaf node adalah 0.
Selain Degree of node, terdapat juga Degree of tree yaitu derajat maksimum simpul di antara semua simpul pada tree.
11. Subtree
Subtree adalah setiap simpul dari tree beserta turunannya.
Fungsi Stuktur Data Tree
Struktur data tree memiliki beberapa fungsi yang sangat berguna dalam pemrograman dan pengolahan data. Beberapa fungsi umum dari struktur data tree antara lain:
Representasi hierarki: Tree digunakan untuk merepresentasikan hubungan hierarkis antara elemen-elemen data. Contohnya, dalam struktur folder dan file pada sistem operasi, setiap folder dapat memiliki subfolder dan file yang terkait.
Pencarian dan pengurutan: Tree juga digunakan untuk melakukan pencarian dan pengurutan data dengan efisien. Contohnya, dalam binary search tree, data diurutkan sehingga operasi pencarian dapat dilakukan dengan kompleksitas waktu yang lebih rendah.
Pohon keputusan: Dalam kecerdasan buatan, tree digunakan untuk membangun model pohon keputusan yang dapat digunakan untuk mengambil keputusan berdasarkan serangkaian aturan dan kondisi.
Representasi struktur data lain: Tree juga digunakan untuk merepresentasikan struktur data lain seperti heap, trie, dan huffman coding.
Jenis-jenis Struktur Data Tree
Ada empat jenis utama pohon biner:
Pohon Biner Penuh - Setiap node induk memiliki dua atau tidak ada anak.
Pohon Biner Sempurna - Setiap node induk memiliki tepat dua node anak dan semua node eksternal (simpul daun) berada pada level yang sama.
Pohon Biner Lengkap - Dalam hal ini, setiap level harus terisi, dan semua elemen daun condong ke kiri.
Pohon Degenerasi - Pohon yang simpul induknya mempunyai satu anak, kiri atau kanan, disebut pohon degenerasi.
Pohon Biner Seimbang - Pohon biner yang perbedaan ketinggian antara simpul anak kiri dan kanan adalah 0 atau 1.
Contoh Program Struktur Data Tree
Berikut adalah contoh sederhana implementasi binary search tree menggunakan bahasa pemrograman Python:
class TreeNode:
def init(self, key):
self.left = None
self.right = None
self.val = key
def insert(root, key):
if root is None:
return TreeNode(key)
else:
if root.val < key:
root.right = insert(root.right, key)
else:
root.left = insert(root.left, key)
return root
def inorder_traversal(root):
if root:
inorder_traversal(root.left)
print(root.val)
inorder_traversal(root.right)
Contoh penggunaan
root = None
root = insert(root, 50)
insert(root, 30)
insert(root, 20)
insert(root, 40)
insert(root, 70)
insert(root, 60)
insert(root, 80)
print(“Hasil inorder traversal:”)
inorder_traversal(root)