AVL Tree

overview

Summary

An avl_tree is a balanced_binary_search_tree that keeps node height differences small. It maintains a balance_factor for each node, defined as left_height minus right_height, kept in {-1,0,1}. To restore balance after insert or delete, it uses rotations: single or double. Core operations search, insert, and delete run in O_log_n time. The invariant is strictly ordered keys with automatic rebalancing. Remember: track heights, compute balance, apply the correct rotation.