praktikum

Praktikum Modul 8: Struktur Data Pohon Biner Terurut (Binary Search Tree)

Asisten Praktikum: Putra Fajar Suhardi

Praktikum Modul 8: Struktur Data Hierarkis Pohon Biner dan Binary Search Tree (BST)

Modul puncak praktikum Struktur Data yang mendalami struktur data pohon biner (Binary Tree), sifat terurut Binary Search Tree (BST), algoritma penelusuran simpul (tree traversal), dan operasi penghapusan simpul non-trivial.

1. Karakteristik Binary Search Tree

Pohon biner memiliki sifat teratur di mana untuk setiap simpul NN:

Nilai pada anak kiri <N.data<Nilai pada anak kanan \text{Nilai pada anak kiri } < N.\text{data} < \text{Nilai pada anak kanan }
  • Operasi Penyisipan: Menelusuri cabang kiri atau kanan secara rekursif hingga menemukan daun kosong.
  • Metode Traversal:
    • In-Order (Kiri, Akar, Kanan): Menghasilkan deret elemen terurut menaik (ascending sorted order).
    • Pre-Order (Akar, Kiri, Kanan): Digunakan untuk kloning dan serialisasi struktur pohon.
    • Post-Order (Kiri, Kanan, Akar): Digunakan untuk penghapusan pohon dari bawah ke atas (bottom-up deletion).

2. Algoritma Penghapusan Simpul BST Tiga Kasus

  1. Simpul daun (tanpa anak): Cukup putuskan penunjuk dari induk simpul.
  2. Simpul dengan satu anak: Tautkan anak tersebut langsung ke induk simpul yang dihapus.
  3. Simpul dengan dua anak: Gantikan nilai simpul dengan in-order successor (elemen terkecil di sub-pohon kanan) atau in-order predecessor (elemen terbesar di sub-pohon kiri), lalu hapus simpul duplikat tersebut.

3. Berkas Praktikum Terlampir

  • Laporan pra-praktikum: 240411100085_Modul08_PraPraktikum.pdf memuat penggambaran pohon biner manual dan tracing lintasan traversal.
  • Laporan resmi praktikum: 240411100085_Modul08_Praktikum.pdf memuat implementasi lengkap kelas TreeNode dan BST, fungsi penyeimbangan pohon, dan bukti kelulusan asistensi praktikum akhir.

Attachments

Back to Academics