AVL TREE

AVL Tree ditemukan oleh Adelson-Velskii dan Landis. AVL Tree merupakan salah satu jenis BST (binary Search Tree). BST digunakan dengan tujuan untuk mempercepat pencarian data. Apabila BST yg terbentuk cukup seimbang (mendekati complete binary tree) maka waktu pencarian data tidak lebih dari log2n langkah. AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan. Insert Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu : anggap T adalah node yang harus diseimbangkan kembali – Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left) – Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right) – Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left) – Kasus 4 : node terda...