Membuat Program Dasar Trees Dalam Kehidupan Sehari-Hari

pada tanggal

Sebelum masuk ke materi pembahasan kita harus mengetahui apa itu Trees

Trees (Pohon)

Tree adalah struktur data yang sangat fleksibel dan efisien untuk merepresentasikan dan memanipulasi data yang memiliki hubungan hierarkis. Dengan memahami konsep dasar dan implementasi tree, kita dapat mengaplikasikan struktur ini dalam berbagai bidang komputasi untuk menyelesaikan masalah secara lebih efektif.

Karakteristik Pohon (Trees)

1. Akar (Root):
  • Node paling atas dalam pohon.
  • Tidak memiliki orang tua (parent).
  • Setiap pohon hanya memiliki satu node akar.
      2. Node:
      • Elemen atau titik dalam pohon yang menyimpan data.
      • Setiap node dapat memiliki anak (children).
        3. Tepi (Edge):
        • Hubungan antara dua node.
        • Setiap edge menghubungkan node induk (parent) dengan node anak (child).
          4. Level (Tingkat):
          • Tingkat kedalaman sebuah node dalam pohon.
          • Root berada di level 0, anak-anaknya di level 1, dan seterusnya.
            5. Daun (Leaf):
            • Node yang tidak memiliki anak.
            • Node paling bawah dalam hierarki.
              6. Subpohon (Subtree):
              • Bagian dari pohon yang terdiri dari sebuah node dan semua turunannya.
              • Setiap node dalam pohon dapat dianggap sebagai akar dari subpohon.
                7. Tinggi Pohon (Height):
                • Panjang jalur terpanjang dari akar ke daun terjauh.
                • Dapat juga diartikan sebagai jumlah level dalam pohon.
                  8. Orang Tua (Parent):
                  • Node yang memiliki anak.
                  • Node yang terhubung ke node lain pada level di bawahnya.
                    9. Anak (Child):
                    • Node yang memiliki orang tua.
                    • Node yang terhubung ke node lain pada level di atasnya.
                      10. Saudara (Sibling):
                      • Node yang memiliki orang tua yang sama.
                      11. Kedalaman (Depth):
                      • Panjang jalur dari akar ke node tertentu.
                      • Setara dengan level dari node tersebut.
                      Jenis-Jenis Trees
                      1. Binary Tree (Pohon Biner)
                      • Penjelasan: Setiap node memiliki paling banyak dua anak (left dan right).
                      • Aplikasi: Digunakan dalam representasi ekspresi aritmatika, parsing, dan banyak algoritma dasar lainnya.
                      2. Binary Search Tree (BST)
                      • Penjelasan: Pohon biner di mana setiap node memenuhi properti: nilai di anak kiri lebih kecil dari nilai di node, dan nilai di anak kanan lebih besar.
                      • Aplikasi: Digunakan untuk operasi pencarian, penyisipan, dan penghapusan yang efisien.
                      3. AVL Tree
                      • Penjelasan: Binary Search Tree yang seimbang secara tinggi, di mana perbedaan tinggi antara subtree kiri dan kanan tidak lebih dari satu untuk setiap node.
                      • Aplikasi: Digunakan untuk memastikan operasi pencarian, penyisipan, dan penghapusan tetap efisien dengan menjaga keseimbangan pohon.
                      4. Red-Black Tree
                      • Penjelasan: Binary Search Tree dengan aturan pewarnaan (node merah atau hitam) yang menjaga keseimbangan pohon.
                      • Aplikasi: Digunakan dalam banyak implementasi map dan set dalam pustaka standar, seperti di Java dan C++.
                      5. B-Tree
                      • Penjelasan: Pohon yang dioptimalkan untuk sistem penyimpanan yang membaca dan menulis data dalam blok besar, seperti disk.
                      • Aplikasi: Digunakan dalam sistem basis data dan sistem file untuk menjaga keseimbangan dan efisiensi akses data.
                      Contoh Program Sederhana Trees Dalam Kehidupan Sehari-Hari 

                      Kode di atas adalah implementasi dari sebuah pohon biner dan beberapa metode untuk melakukan penelusuran (traversal) pada pohon tersebut. Berikut penjelasannya:

                      1. Kelas Node

                      • Node : Kelas ini mendefinisikan node dalam pohon biner. Setiap node memiliki atribut data, left, dan right.
                      • Data: Menyimpan data untuk node.
                      • Left: Menunjuk ke anak kiri node.
                      • Right: Menunjuk ke anak kanan node.

                      2. Fungsi Traversal

                      • Inorder_traversal*: Fungsi ini melakukan penelusuran inorder pada pohon.
                      • Dalam penelusuran inorder, pertama kita mengunjungi subtree kiri, kemudian root, dan terakhir subtree kanan.
                      • Panggilan rekursif pada subtree kiri (inorder_traversal(root.left)), kemudian mencetak data root (print(root.data, end=" ")), dan terakhir panggilan rekursif pada subtree kanan (inorder_traversal(root.right)).
                      • Preorder_traversal*: Fungsi ini melakukan penelusuran preorder pada pohon.
                      • Dalam penelusuran preorder, pertama kita mengunjungi root, kemudian subtree kiri, dan terakhir subtree kanan.
                      • Mencetak data root (print(root.data, end=" ")), kemudian panggilan rekursif pada subtree kiri (preorder_traversal(root.left)), dan terakhir panggilan rekursif pada subtree kanan (preorder_traversal(root.right)).
                      • postorder_traversal*: Fungsi ini melakukan penelusuran postorder pada pohon.
                      • Dalam penelusuran postorder, pertama kita mengunjungi subtree kiri, kemudian subtree kanan, dan terakhir root.
                      •  Panggilan rekursif pada subtree kiri (postorder_traversal(root.left)), kemudian panggilan rekursif pada subtree kanan (postorder_traversal(root.right)), dan terakhir mencetak data root (print(root.data, end=" ")).

                      3. Pembuatan Pohon

                      • Membuat pohon biner dengan root "Kakek".
                      • Root memiliki anak kiri "Ayah" dan anak kanan "Paman".
                      • Anak kiri "Ayah" memiliki dua anak: "Anak1" dan "Anak2".
                      • Anak kanan "Paman" memiliki satu anak: "Sepupu".

                      4. Pencetakan Traversal

                      • Inorder traversal*: Dicetak dalam urutan "Anak1 Ayah Anak2 Kakek Paman Sepupu".
                      • Preorder traversal*: Dicetak dalam urutan "Kakek Ayah Anak1 Anak2 Paman Sepupu".
                      • Postorder traversal*: Dicetak dalam urutan "Anak1 Anak2 Ayah Sepupu Paman Kakek".

                      Traversals tersebut digunakan untuk melihat urutan elemen dalam pohon biner dengan cara yang berbeda-beda sesuai kebutuhan. Dan Hasil outputnya seperti gambar dibawah ini.







































                      Komentar

                      Posting Komentar