Explanation
- The **AA Tree** is a self-balancing binary search tree (BST). It’s a variation of the Red-Black Tree but with a simpler set of rules. The primary difference lies in how the tree is balanced, and it ensures that operations like insertion, deletion, and searching remain efficient.
-
-
Steps:
- The balance condition is enforced with a single balance factor for each node (the “level”), which simplifies the balancing process.
- Level Rule: The left child of a node must have the same level or one more level than its parent.
- Rotation Rule: The tree uses rotations (like right or left) to ensure the balance after insertion or deletion.
-
Time Complexity
- Insertion: O(log n)
- Deletion: O(log n)
- Search: O(log n)