Python DSALesson 101Preview gratis
AVL Trees
Lesson ini bagian dari Python · Semua level
Ringkasan
Pelajaran ini membahas AVL Tree, yaitu Binary Search Tree yang dijaga selalu seimbang dengan melakukan rotasi. Keseimbangan diukur dari balance factor, yaitu selisih tinggi subtree kiri dan subtree kanan sebuah node. Berkat keseimbangan ini, operasi insert, search, dan delete tetap berjalan O(log n) meskipun data masuk dalam urutan acak.
Poin kunci
- Balance factor = tinggi(subtree kiri) - tinggi(subtree kanan) dan harus selalu -1, 0, atau 1.
- Ketika sebuah node tidak seimbang, dilakukan rotasi tunggal (kiri atau kanan) atau rotasi ganda.
- Rotasi kanan dipakai saat subtree kiri terlalu tinggi, rotasi kiri dipakai saat subtree kanan terlalu tinggi.
- AVL Tree disebut self-balancing karena menyeimbangkan dirinya sendiri setiap kali struktur berubah.
- Harga dari keseimbangan ini adalah kode insert dan delete sedikit lebih rumit dibanding BST biasa.
Materi lengkap
Contoh kode dan kuis
Materi lengkap, contoh kode, dan kuis tersedia untuk pelanggan. 5 soal.