AVL Tree
AVL Tree AVL adalah balanced binary search tree dimana ia memiliki perbedaan jumlah node pada subtree kiri dan subtree kanannya maksimal 1 (atau dapat dikatakan antara tingginya sama atau selisih satu). Contoh Gambar AVL Tree Node AVL Tree, karena balance factor tertingginya 2, sedangkan syarat AVL adalah selisihnya maksimal 1 Cara menentukan Height dan Balance Factor :Note : Height : – Jika node (root) tidak memiliki subtree heightnya = 0 – Jika node adalah leaf, height = 1 – Jika internal node, maka height = height tertinggi dari anak + 1 Balance Factor : -selisih height antara anak kiri dan kanan, jika tidak memiliki anak, dianggap 0. Penambahan node di AVL Tree Untuk menjaga tree tetap imbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru → root. Node pertama yang memiliki |balance factor| > 1 diseimbangkan. Proses penyeimbangan dilakukan dengan: Single rotation dan Double rotation Single Rotation Single rotatio