Pengantar

binary search tree menjaga nilai tetap terurut: subtree kiri setiap node menyimpan nilai yang lebih kecil, sedangkan subtree kanannya menyimpan nilai yang lebih besar. Urutan ini membuat pencarian berlangsung cepat, tetapi hanya jika tree tetap cukup seimbang. Jika kamu memasukkan nilai dalam urutan terurut ke binary search tree biasa, strukturnya akan berubah menjadi garis lurus, sehingga setiap pencarian menjadi pemindaian linear yang lambat.

AVL Tree mengatasi hal ini dengan menjaga keseimbangannya secara otomatis. Setelah setiap penyisipan atau penghapusan, tree memeriksa apakah ada node yang menjadi tidak seimbang. Jika ada, tree melakukan perbaikan lokal kecil yang disebut rotasi untuk memulihkan keseimbangan. Apa pun cara kamu membangunnya, AVL Tree tidak akan berubah menjadi garis lurus.

Dalam kursus ini, kamu akan membangun AVL Tree dari awal dalam bahasa pilihanmu: node dengan tinggi yang dilacak, pemeriksaan keseimbangan, empat kasus rotasi, serta penyisipan dan penghapusan yang menjaga keseimbangan secara otomatis. Kemudian, kamu akan menggunakan class yang sudah selesai untuk menyelesaikan serangkaian tantangan latihan.