TreesMenengahFase D–FE1E5

BINARY SEARCH TREE

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.

Example use case

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

Syllabus

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

Objectives

·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

How It Works

·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

Prerequisites

·Pohon biner
·Rekursi

Real-World Uses

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

Complexity O(tinggi pohon)