Interactive AVL Tree Visualization
The AVL Tree visualization I've created is a fully interactive tool that helps you understand how AVL trees work. Here's what you can do with it:
The AVL Tree visualization I've created is a fully interactive tool that helps you understand how AVL trees work. Here's what you can do with it:
- Insert nodes - Enter a value and click "Insert" to add a node to the tree
- Delete nodes - Enter a value and click "Delete" to remove a node
- Run a demo - Click "Run Demo" to see a sequence of insertions and deletions that demonstrate various rotations
- Reset the tree - Start over with a clean slate
The visualization shows:
- Each node with its value and balance factor (BF)
- Color-coded nodes (green for balanced, orange for nodes involved in rotations)
- Real-time animations of tree restructuring during rotations
The information tabs explain:
- Key properties of AVL trees
- How the four types of rotations work (Left, Right, Left-Right, Right-Left)
- A detailed operation log showing exactly what's happening during each step
This tool demonstrates the self-balancing nature of AVL trees and how they maintain O(log n) height through rotations whenever the balance factor of any node becomes greater than 1 or less than -1.
AVL Tree Visualization
An AVL tree is a self-balancing binary search tree where the height difference between left and right subtrees (balance factor) is at most 1 for all nodes.
Key Properties of AVL Trees:
- Self-balancing: The tree automatically maintains its balance after insertions and deletions.
- Balance Factor: For each node, the height difference between left and right subtree is at most 1.
- Height: For n nodes, the height is O(log n).
- Operations: Insert, delete, and search operations take O(log n) time.
In this visualization, each node shows its value and balance factor (small number below). Balance factors of +1, 0, or -1 are normal. When a node's balance factor becomes +2 or -2 after an operation, rotations are performed to restore balance.
Rotations in AVL Trees:
When a node becomes unbalanced (balance factor of +2 or -2), one of four rotations is performed:
- Left Rotation: When a right subtree becomes too heavy (balance factor of -2).
- Right Rotation: When a left subtree becomes too heavy (balance factor of +2).
- Left-Right Rotation: When a left subtree's right child causes imbalance.
- Right-Left Rotation: When a right subtree's left child causes imbalance.
Rotations are highlighted in orange in the visualization.