AVL Tree
Learn AVL Tree (Advanced Data Structures, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
AVL Tree: A Self-Balancing Binary Search Tree A plain binary search tree can degrade into a linked list (insert 1, 2, 3, 4... in order and every search takes O(n)). An AVL tree prevents this: for every node the heights of its two subtrees differ by at most 1 . After each insert, walk back up; if a node's balance factor (left height - right height) reaches +2 or -2, fix it with a rotation . Four cases: LL and RR need one rotation, LR and RL need two. Search, insert and delete are all O(log n) .