PohonMenengahFase D–FE1E5

Binary Search Tree (BST)

Binary Search Tree menyimpan nilai secara terurut: tiap node punya anak kiri yang lebih kecil dan anak kanan yang lebih besar. Menyisip atau mencari cukup menuruni satu jalur — ke kiri bila lebih kecil, ke kanan bila lebih besar — sehingga biayanya O(tinggi pohon). Penelusuran in-order menghasilkan data terurut.

Contoh kasus

Struktur indeks untuk pencarian cepat: kamus atau buku telepon digital yang menjaga data tetap terurut sambil tetap murah menambah entri baru.

Silabus

Pohon yang menyimpan data terurut: anak kiri lebih kecil, anak kanan lebih besar, sehingga cari dan sisip cukup menuruni satu jalur.

Tujuan Belajar

·Memahami aturan kiri-lebih-kecil, kanan-lebih-besar pada BST
·Menjelaskan cara mencari dan menyisip dengan menuruni satu jalur
·Menerapkan penelusuran in-order untuk membaca data terurut

Cara Kerja

·Mulai dari akar pohon
·Bila nilai dicari lebih kecil, turun ke anak kiri
·Bila lebih besar, turun ke anak kanan
·Berhenti saat nilai ketemu atau menemukan tempat kosong untuk sisip
·Penelusuran in-order menghasilkan semua data dalam urutan menaik

Prasyarat

·Pohon biner
·Rekursi

Contoh Nyata

·Indeks buku telepon digital yang tetap terurut saat entri ditambah
·Kamus digital yang cepat dicari sekaligus mudah disisipi kata baru

Kompleksitas O(tinggi pohon)