Tree
Struktur tree digunakan untuk merepresentasikan hubungan hierarkis (one-to-many) secara grafis. Meskipun secara visual, tree ini tampak sebagai kumpulan node yang tersusun dari atas ke bawah, ia menggambarkan hubungan yang tidak linear antara node-node tersebut. Tree adalah contoh dari struktur data non-linier yang mampu merepresentasikan hubungan hierarki antara node-node di dalamnya.
Fungsi dan Kegunaan Tree
- Dalam kehidupan nyata, struktur data tree membantu dalam pengembangan sebuah game
- Membantu Pengindeksan pada database.
- Decision tree adalah Tools yang biasa digunakan dalam analisis Keputusan. Dalam decision tree juga dapat mempermudah untuk memahami sebuah data.
- Domain Name Server juga menggunakan Struktur data Tree
- Kasus penggunaan tree paling umum adalah situs jejaring social, seperti Facebook, Instagram dan lain lain.
Keunggulan Stuktur Data tree
- Memungkinkan subtree untu dipindahkan dengan usaha yang minim
- Mencerminkan hubungan data secara struktural
- Menawarkan operasi pencarian dan penyisipan yang efisien
- Tree baik digunakan untuk membuat hierarki data.
Binary Tree
Binary Tree (Pohon Biner) merupakan dasar yang penting untuk memahami berbagai algoritma dan struktur data yang lebih kompleks, seperti Binary Search Trees (BST), AVL Trees, dan lainnya. Dengan memahami konsep dasar dan karakteristik Binary Tree, termasuk traversal dan operasi-operasi dasarnya, kita akan memiliki fondasi yang kuat untuk mempelajari dan mengimplementasikan struktur data yang lebih maju.
Ciri khusus yang bisa dilihat dari Binary Tree adalah memiliki maksimal 2 anak. Ini berarti setiap node tidak akan memiliki lebih dari dua cabang. Binary Tree juga dapat didefinisikan sebagai berikut:
- Pohon Biner Kosong (jika tidak ada data).
- Pohon Biner yang terdiri dari sebuah node yang disebut node root, dan dua subtree (cabang pohon) yaitu subtree kiri dan subtree kanan, di mana keduanya sendiri juga merupakan pohon biner.
Berikut adalah beberapa istilah dasar yang penting dalam Pohon Biner:
- Node: Node adalah elemen dasar dalam pohon yang menyimpan data. Setiap node memiliki referensi yang menunjuk ke node anak (child) atau ditunjuk oleh node induk (parent).
- Root Node: Node teratas dalam pohon yang unik karena tidak memiliki node induk (parent).
- Subtree: Merupakan cabang dari pohon yang terdiri dari node keturunan dari suatu node.
- Node Parent: Node yang bertindak sebagai penghubung dengan dua node anak, dan memiliki referensi yang menunjuk ke node-node tersebut.
- Levels: Merupakan tingkatan dalam pohon. Node root berada pada level 0, dan level meningkat seiring dengan kedalaman node dari root.
- Traversal: Proses mengunjungi setiap node dalam pohon mengikuti pola tertentu.
- Key: Setiap node dalam Pohon Biner memiliki data yang disebut "key." Sifat penting dari "key" ini adalah bahwa mereka harus unik, artinya tidak ada dua node yang memiliki key yang sama.
Traversal
Traversal adalah proses mengunjungi setiap node dalam pohon dengan urutan tertentu. Ada tiga metode utama untuk melakukan traversal pada Pohon Biner:
- Pre-Order Traversal (Parent Node, Left Child, Right Child):
- Metode ini mengunjungi node induk terlebih dahulu, kemudian dilanjutkan dengan node anak kiri dan terakhir node anak kanan.
- Sangat cocok untuk evaluasi ekspresi matematika dalam bentuk pohon ekspresi, karena operator dievaluasi sebelum operand.
- In-Order Traversal (Left Child, Parent Node, Right Child):
- Metode ini mengunjungi node anak kiri terlebih dahulu, kemudian node induk, dan terakhir node anak kanan.
- Biasanya digunakan untuk mengurutkan elemen dalam Pohon Pencarian Biner (Binary Search Tree) dari yang terkecil hingga yang terbesar.
- Post-Order Traversal (Left Child, Right Child, Parent Node):
- Metode ini mengunjungi node anak kiri terlebih dahulu, kemudian node anak kanan, dan terakhir node induk.
- Sangat berguna untuk operasi yang memerlukan pemrosesan atau penghapusan node setelah semua anak-anaknya telah dikunjungi, seperti menghapus semua node dalam pohon secara rekursif.
Dengan memahami metode-metode traversal ini, kita dapat mengelola dan memanipulasi pohon biner dengan lebih efektif.
