Apa itu Pohon AVL?

Setiap node dalam AVL Tree mencatat tinggi-nya sendiri: jumlah sisi pada jalur terpanjang hingga ke leaf. Leaf memiliki tinggi 1, sedangkan subtree kosong dihitung memiliki tinggi 0. Dari tinggi kedua anak sebuah node, kamu dapat menghitung faktor keseimbangannya: height(left) - height(right).

Sebuah node seimbang jika faktor keseimbangannya adalah -1, 0, atau 1. Aturan AVL Tree sederhana: setiap node harus selalu seimbang. Setiap kali penyisipan atau penghapusan membuat faktor keseimbangan sebuah node menjadi 2 atau -2, tree melakukan rotasi: penataan ulang lokal beberapa pointer yang memulihkan keseimbangan dalam waktu konstan tanpa merusak urutan search tree.

Ada empat kasus rotasi (kiri-kiri, kanan-kanan, kiri-kanan, kanan-kiri), tetapi semuanya terdiri dari dua dasar: satu rotasi kiri dan satu rotasi kanan. Kamu akan membuat keduanya dari awal dalam beberapa pelajaran berikutnya.