What is an AVL tree and why is it balanced?

Prepare for the 241 Computer Science Certification Exam with comprehensive flashcards and multiple choice questions. Enhance knowledge with explanations and hints to excel in your test journey!

An AVL tree is a binary search tree that automatically keeps itself balanced. The key idea is that for every node, the heights of its left and right subtrees differ by at most one. This constraint prevents the tree from becoming too tall on any path, which would otherwise slow operations. Because of this balance, the tree’s height grows only logarithmically with the number of nodes, ensuring search, insert, and delete can be performed in O(log n) time. When insertions or deletions cause a node to become unbalanced (its subtrees differ by more than one in height), rotations (single or double) are used to restore the balance while preserving the binary search tree order. This structure isn’t about leaves being at the same depth (that would describe a perfectly balanced or complete tree) and it isn’t a heap; its defining feature is maintaining the balance constraint with rotations to keep the height small.