AVL trees and splay trees are two types of self-balancing binary search trees, each with its own trade-offs and use cases. Understanding their differences is crucial for making informed decisions about which data structure to use in various scenarios.

AVL Trees

Overview

AVL trees, named after inventors Adelson-Velsky and Landis, are a type of self-balancing binary search tree where the difference in heights between the left and right subtrees (known as the balance factor) of every node is at most 1. This strict balancing condition ensures that the tree maintains $O(\log n)$ time complexity for operations like insertion, deletion, and look-up.

Key Characteristics

• Balance Factor: For any node in an AVL tree, the balance factor should be -1, 0, or 1. This is recalculated and potentially corrected after every insert or delete operation.
• Rotations: To maintain balance, AVL trees use single or double rotations (right, left, left-right, and right-left).
• Height: AVL trees guarantee a height of at most $1.44 \log_2(n + 2) - 0.328$ for a tree with $n$ nodes.
• Strict Balance: Due to the strict balancing criteria, AVL trees offer optimized search operations at the cost of slightly more complex insertion and deletion operations.

Example

Consider inserting a series of nodes with values 10, 20, and 30 into an initially empty AVL tree:

1. Insert 10:
   • Tree consists of a single node, 10.
2. Insert 20:
   • Tree is still balanced. 10 is root, 20 is right child.
3. Insert 30:
   • Right-right case imbalance. Perform a left rotation on root (10).
   • New root is 20, with 10 as left child and 30 as right child.

• Splaying: Accessing a node performs rotations to bring it to the root. This recent-access pattern optimizes the tree for sequences with locality of reference.
• Amortized Complexity: Operations (insert, delete, search) have an amortized time complexity of $O(\log n)$, but individual operations can be as slow as $O(n)$ in the worst case.
• No Balance Factor: Unlike AVL trees, splay trees do not maintain a strict balance factor.
• Applications: Ideal for situations with frequent access to certain elements, capitalizing on temporal locality.
• Access 10: No change needed, 10 becomes the root if not already.
• Access 20: Splay 20 to the root via rotations.
• Access 30: Splay 30 to the root.