Posts

Showing posts from May, 2020

AVL Tree

Image
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