Pengertian Struktur Data Tree
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.
Fungsi Struktur 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
Struktur data tree dapat diklasifikasikan menjadi empat jenis utama:
- General Tree: General tree adalah jenis tree yang tidak membatasi jumlah anak dari setiap simpul. Setiap simpul dalam general tree dapat memiliki jumlah anak yang berbeda-beda.
- Binary Tree: Binary tree adalah jenis tree yang setiap simpulnya memiliki paling banyak dua anak, yaitu anak kiri dan anak kanan. Binary tree sering digunakan dalam implementasi struktur data seperti binary search tree dan heap.
- Balanced Tree: Balanced tree adalah jenis tree yang diatur sedemikian rupa sehingga ketinggian subtree kiri dan subtree kanan dari setiap simpul tidak memiliki perbedaan yang signifikan. Contoh balanced tree adalah AVL tree dan Red-Black tree.
- Binary Search Tree: Binary search tree adalah jenis binary tree yang memiliki sifat tertentu, yaitu setiap simpul di sebelah kiri memiliki nilai yang lebih kecil daripada simpul tersebut, dan setiap simpul di sebelah kanan memiliki nilai yang lebih besar. Binary search tree digunakan terutama untuk operasi pencarian dan pengurutan data secara efisien.
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)