Pohon pencarian biner
Pohon pencarian biner seimbang berisi 1023 kunci menemukan kunci mana pun dalam paling banyak 10 perbandingan; kalau dibangun dari masukan terurut, kunci yang sama bisa memakan 1023.
Pencarian biner yang tertanam dalam bentuknya
Pencarian biner pada array terurut menemukan kunci dalam sekitar log₂ n pemeriksaan, tetapi menyisipkan ke array terurut menggeser nilai. Tabel hash menyisipkan dengan cepat, tetapi melupakan urutan: ia tidak bisa dengan mudah memberi tahu kunci terkecil atau kunci berikutnya sesudah 40. Pohon pencarian biner (binary search tree, BST) mengincar keduanya. Pohon ini terdiri atas node, seperti linked list, tetapi setiap node punya dua pointer, left dan right (kiri dan kanan). Node paling atas adalah akar (root); node tanpa anak adalah daun (leaf).
Satu aturan menjadikannya pohon pencarian: untuk setiap node, semua kunci di subpohon kirinya lebih kecil, dan semua kunci di subpohon kanannya lebih besar. Untuk mencari sebuah kunci, mulai dari akar lalu bandingkan. Sama berarti ketemu. Lebih kecil berarti ke kiri, lebih besar berarti ke kanan. Setiap perbandingan membuang satu subpohon utuh, sama seperti pencarian biner membuang separuh daftar. Mencari 60 di pohon 50, 30, 70, 20, 40, 60, 80 membandingkan dengan 50, lalu 70, lalu 60: 3 perbandingan.
Penyisipan mengikuti jalur yang sama. Pergi ke kiri atau kanan sampai pointer yang kamu butuhkan kosong, lalu gantungkan node baru di sana. Menyisipkan 45 membandingkan dengan 50 (ke kiri), 30 (ke kanan), dan 40 (ke kanan), dan 40 tidak punya anak kanan, jadi 45 menjadi anak kanannya. Menghapus node yang bukan daun butuh satu gagasan lagi: catatan MIT menukar item-nya dengan kunci berikutnya atau sebelumnya menurut urutan, lalu menghapus dari sana. Aturan hitung di laboratorium adalah satu perbandingan untuk setiap node di jalur.
Seret untuk memutar. Gulir atau cubit untuk memperbesar.
Tinggi adalah segalanya
Berapa perbandingan yang bisa dibutuhkan sebuah pencarian? Paling banyak satu per tingkat, jadi biayanya bergantung pada tinggi pohon, yaitu banyaknya sisi pada jalur terpanjang dari akar turun ke daun. Catatan MIT menyatakannya begini: operasi pohon berjalan dalam waktu O(h). Pohon 50, 30, 70, 20, 40, 60, 80 bertinggi 2, jadi tidak ada pencarian yang butuh lebih dari 3 perbandingan. Pohon seimbang sempurna berisi 1023 node bertinggi 9 dan butuh paling banyak 10.
Tetapi bentuknya bergantung pada urutan penyisipan. Sisipkan 10, 20, 30, 40, 50, 60, 70 dengan urutan terurut, maka setiap kunci lebih besar daripada semua kunci sebelumnya, jadi setiap node baru masuk di kanan node terakhir. Pohonnya menjadi rantai bertinggi 6, dan mencari 70 memakan 7 perbandingan: sebuah linked list dengan pointer tambahan. Dengan 1023 kunci terurut, pencarian terburuk memakan 1023 perbandingan, bukan 10.
Pohon seimbang memperbaiki ini dengan membentuk ulang dirinya setelah setiap penyisipan atau penghapusan. Skema pertama adalah pohon AVL, dari Georgy Adelson-Velsky dan Evgenii Landis pada tahun 1962, yang dibahas di kuliah 7 MIT. Pohon ini menjaga, di setiap node, tinggi kedua subpohonnya berselisih paling banyak 1, dan memperbaiki setiap pelanggaran dengan gerakan lokal kecil yang disebut rotasi. Itu menjaga tingginya tetap O(log n), sehingga mencari, menyisipkan, dan menghapus tetap O(log n) apa pun urutan datangnya kunci.
Kunci terurut tanpa biaya tambahan
BST menyimpan lebih dari sekadar keanggotaan. Kunjungi subpohon kiri, lalu node itu, lalu subpohon kanan, secara rekursif, maka kunci-kuncinya keluar dalam urutan terurut. Penelusuran in-order ini (MIT menyebutnya traversal order) adalah cara BST menjawab "kunci terkecil", "kunci terbesar", dan "kunci berikutnya sesudah 40", yaitu operasi urutan pada antarmuka Set MIT yang tidak bisa dilakukan tabel hash dengan cepat.
| Akar dan daun | Akar adalah node paling atas; daun tidak punya anak. |
| Sifat BST | Kunci subpohon kiri lebih kecil, kunci subpohon kanan lebih besar, di setiap node. |
| Tinggi | Banyaknya sisi pada jalur terpanjang dari akar ke daun. Pencarian memakan paling banyak tinggi + 1 perbandingan. |
| Pohon AVL | BST seimbang (1962): tinggi subpohon berselisih paling banyak 1, diperbaiki dengan rotasi. |
| Penelusuran in-order | Kiri, node, kanan: mendaftar kunci dalam urutan terurut. |
- Pernyataan mana yang merupakan sifat pohon pencarian biner?
- Setiap node punya tepat dua anak
- Kunci subpohon kiri lebih kecil dan kunci subpohon kanan lebih besar, di setiap node
- Kunci disimpan sesuai urutan penyisipan
- Akar adalah kunci terkecil
- Pohon dibangun dari 50, 30, 70, 20, 40, 60, 80. Berapa perbandingan untuk mencari 60?
- Pohon yang sama: mencari 45, yang tidak ada, memakan berapa perbandingan?
- Sisipkan 45 ke pohon itu. Di mana tempatnya?
- Anak kiri 50
- Anak kanan 40
- Anak kiri 60
- Anak kanan 30
- Berapa tinggi pohon 50, 30, 70, 20, 40, 60, 80?
- Sisipkan 10, 20, 30, 40, 50, 60, 70 dengan urutan itu. Berapa perbandingan untuk mencari 70?
- BST seimbang sempurna punya 1023 node (tinggi 9). Berapa perbandingan paling banyak yang bisa dibutuhkan sebuah pencarian?
- Susun kunci-kunci pohon 50, 30, 70, 20, 40 sesuai urutan kunjungan penelusuran in-order.
- Siapa yang mengusulkan skema pohon seimbang pertama, dan kapan?
- Adelson-Velsky dan Landis, 1962
- Luhn, 1953
- Bauer dan Samelson, 1957
- Knuth, 1998
- Pertanyaan mana yang bisa dijawab BST dengan cepat tetapi tidak oleh tabel hash biasa?
- Apakah 40 tersimpan?
- Apa kunci berikutnya sesudah 40?
- Ada berapa bucket?
- Berapa 40 mod 7?
- Pada BST, kunci yang lebih kecil ke kiri dan kunci yang lebih besar ke kanan di setiap node.
- Pencarian dan penyisipan mengikuti satu jalur: paling banyak tinggi + 1 perbandingan.
- Masukan terurut membentuk rantai (7 kunci, tinggi 6); pohon seimbang seperti AVL (1962) menjaga tinggi O(log n).
- Penelusuran in-order mendaftar kunci dalam urutan terurut.
Sumber kursus ini (11)
- MIT OpenCourseWare 6.006 Introduction to Algorithms, Spring 2020 (Demaine, Ku, Solomon)
- lecture notes 2 Data Structures (interface vs data structure, Sequence and Set interfaces, stack = insert_last/delete_last, queue = insert_last/delete_first, array, linked list, dynamic array, amortized Θ(1) append)
- 4 Hashing (chaining, pigeonhole collisions, chain length n/m)
- 6 Binary Trees Part 1 (height, traversal order, O(h) operations) and 7 Binary Trees Part 2: AVL (Adelson-Velsky and Landis, 1962) at ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/lecture-notes
- MDN Web Docs, Array.prototype.shift (shifts all values left by 1)
- Array.prototype.unshift, Map (insertion order, Map vs Object, spec requires sublinear average access) and Set (developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects)
- ECMAScript 2025 Language Specification (tc39.es/ecma262)
- 24.1 Map Objects and 24.2 Set Objects ("must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements")
- Array.prototype.shift steps (Repeat, while k < len: move element k to k - 1)
- D. E. Knuth, The Art of Computer Programming vol. 3 (2nd ed. 1998) section 6.4 History (H. P. Luhn, IBM internal memorandum January 1953, hashing with chaining; digit pairs added mod 10, 31415926 -> 4548) via gwern.net copy, and IEEE Spectrum, "Hans Peter Luhn and the Birth of the Hashing Algorithm" (2018)
- "A brief history of the stack", SIGCIS (sigcis.org/files/A brief history.pdf: Bauer and Samelson applied for the patent in 1957, US 3,047,228 granted July 31, 1962; IPL list processing by Newell, Simon and Shaw at RAND 1956) and Wikipedia, Information Processing Language (Newell, Shaw, Simon, RAND and Carnegie Institute of Technology, about 1956).
Diperiksa: 2026-10-18