Binary Search Tree

 

Materi BST

PPT BST

Pengertian Binary Search Tree

Binary Search Tree (BST) adalah struktur data berbentuk tree (pohon) yang digunakan untuk menyimpan data secara terurut sehingga proses pencarian, penyisipan, dan penghapusan data dapat dilakukan dengan lebih efisien.

BST merupakan pengembangan dari struktur data Binary Tree. Setiap node pada BST memiliki maksimal dua anak:

• Left Child (anak kiri)
• Right Child (anak kanan)

Aturan utama pada BST:

1. Semua nilai pada subtree kiri lebih kecil dari node induk.
2. Semua nilai pada subtree kanan lebih besar dari node induk.
3. Setiap subtree juga merupakan BST.

Struktur Dasar BST

Contoh BST:

50

/ \

30 70

/ \ / \

20 40 60 80

Penjelasan:

• Node 50 adalah root.
• Node 30 berada di kiri karena lebih kecil dari 50.
• Node 70 berada di kanan karena lebih besar dari 50.
• Node 20 lebih kecil dari 30.
• Node 80 lebih besar dari 70.

Referensi

Materi Tree

https://cstaleem.com/basic-tree-terminologies-in-data-structure

https://www.programiz.com/dsa/trees

https://drive.google.com/file/d/142wsjzK1ANXB83TWq4tmGtRFdUwHfv1u/view

https://github.com/Algoritma-dan-Pemrograman-ITS/StrukturData/wiki

Pengumpulan Tugas

Form Monitoring Tugas

Hasil Monitoring

Absensi

https://youtu.be/KC2YdOs_rpk

B Tree dan BST

 

https://docs.google.com/document/d/1mXUQcHwqTPW-l90gu63eKKloryERqmxC/edit?usp=drive_link&ouid=112365073285716859334&rtpof=true&sd=true

https://docs.google.com/document/d/1D72whLUJQTa-vEx-WwM6jc0p8uFXrnpC/edit?usp=drive_link&ouid=112365073285716859334&rtpof=true&sd=true

Penggunaan Tree

 

Deskripsi Studi Kasus

Panduan Implementasi

Studi Kasus 1 — Sistem Folder Komputer 

Buatlah aplikasi simulasi sistem folder komputer menggunakan struktur data Tree.

Aplikasi harus mampu:

• Membuat folder baru
• Menghapus folder
• Menampilkan struktur direktori
• Mencari folder tertentu
• Menghitung jumlah folder
• Menampilkan path lengkap suatu folder

Ketentuan

• Gunakan struktur Tree non-binary (General Tree)
• Setiap node merepresentasikan folder
• Implementasikan traversal:
  • Preorder
  • Postorder
• Gunakan bahasa C++
• Tampilkan hasil dalam bentuk hierarki seperti sistem operasi

https://youtu.be/m9mXJMrtox0

Referensi

Materi Tree

https://cstaleem.com/basic-tree-terminologies-in-data-structure

https://www.programiz.com/dsa/trees

https://drive.google.com/file/d/142wsjzK1ANXB83TWq4tmGtRFdUwHfv1u/view

Pengumpulan Tugas

Form Monitoring Tugas

Hasil Monitoring

Absensi

Tree

 

https://drive.google.com/file/d/13GMgO5gLfefrapHkG2eFvZa9gOfQ2-fh/view?usp=drive_link

Definisi Tree

Tree (pohon) adalah struktur data non-linear yang berbentuk hierarki dan terdiri dari kumpulan elemen yang disebut node (simpul). Setiap node dalam tree dihubungkan oleh garis yang disebut edge (sisi), yang bisa bersifat terarah (directed) maupun tidak terarah (undirected).

Pada ilustrasi:

• Lingkaran = Node
• Garis penghubung = Edge

Mengapa Tree Dibutuhkan dalam Struktur Data?

Struktur data seperti:

• Array
• Linked List
• Stack
• Queue

merupakan struktur data linear, di mana data disimpan secara berurutan.

Kelemahan Struktur Linear:

• Operasi seperti insert dan delete semakin lambat ketika data besar
• Kompleksitas waktu meningkat (kurang efisien untuk data besar)

Keunggulan Tree:

• Struktur non-linear → lebih fleksibel
• Proses:
  • Penyimpanan data lebih efisien
  • Akses data lebih cepat
  • Manipulasi data lebih optimal
• Mendukung teknik traversal (penelusuran) seperti:
• Preorder
• Inorder
• Postorder

Latihan

https://drive.google.com/file/d/1P9AXcgq4NMbseGggYl2tL5RtV7IQxgQ8/view?usp=drive_link

Pengumpulan Tugas

Form Monitoring Tugas

Hasil Monitoring

Absensi