AVL Tree diciptakan oleh Adelson-Velskii dan Landis. AVL Tree merupakan Binary Search Tree yang memiliki selisih tinggi / level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree mempersingkat waktu pencarian dan menyederhanakan bentuk tree. Tree diatas merupakan AVL karena selisih subtree kiri dan subtree kanan memenuhi salah satu syaratnya yaitu sama dengan 1. Di bawah ini adalah tree yang bukan AVL karena selisih subtree kiri dan subtree kanan sama dengan 2, yang berarti tidak memenuhi syarat. INSERTION Untuk insertion AVL Tree terdapat 4 case: 1. Single Rotation Kasus 1 Left-Left Case akan diselesaikan dengan Right Rotate dan menjadi: 18 / \ 5 27 Kasus 2 Right-Right Case akan diselesaikan dengan Left Rotate dan menjadi: 45 / \ 30 75 2. Double Rotation Kasus 3 Right-Left Case akan diselesaikan dengan Right Rotate lalu Left Rotate menjadi: (1) Right Rotate 50 \ 63 \