AVL Tree Operations
Traverse
100%
Ctrl + scroll to zoom
AVL Tree
Watch AVL tree rotations maintain balance after every insertion and deletion.
Time O(log n) · Space O(n)
Implementation
from enum import Enum
class AvlNode:
"""A node in the AVL tree with height tracking."""
__slots__ = ("val", "left", "right", "height")
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.height = 1
def __str__(self):
return str(self.val)
def __repr__(self):
return str(self.val)
class AvlTree:
"""
Self-balancing AVL tree implementation.
Maintains the AVL invariant: |balance_factor| <= 1 for all nodes.
Provides operations for adding, searching, deleting nodes,
finding successors, and traversing the tree.
"""
def __init__(self):
"""Initialize an empty AVL tree."""
self.root = None
def __contains__(self, val):
"""Allow 'val in tree' syntax."""
return self.search(val) is not None
# -------------------------------------------------------------------------
# Height and Balance Factor Helpers
# -------------------------------------------------------------------------
def _height(self, node: AvlNode) -> int:
"""Return height of node (0 for None)."""
return node.height if node else 0
def _update_height(self, node: AvlNode) -> None:
"""Update node's height based on children."""
node.height = 1 + max(self._height(node.left), self._height(node.right))
def _balance_factor(self, node: AvlNode) -> int:
"""Return balance factor: left_height - right_height."""
return self._height(node.left) - self._height(node.right) if node else 0
# -------------------------------------------------------------------------
# AVL Rotations
# -------------------------------------------------------------------------
# Rotations preserve BST ordering while rebalancing the tree.
#
# Left Rotation: Right Rotation:
# x y y x
# / \ => / \ / \ => / \
# A y x C x C A y
# / \ / \ / \ / \
# B C A B A B B C
#
# CRITICAL: Height updates must be bottom-up (child before parent)
# to avoid stale height values causing incorrect balance factors.
# -------------------------------------------------------------------------
def _rotate_left(self, x: AvlNode) -> AvlNode:
"""Perform left rotation on node x, return new root."""
if not x or not x.right:
return x
y = x.right
x.right = y.left
y.left = x
self._update_height(x) # Child first (now lower in tree)
self._update_height(y) # Then parent
return y
def _rotate_right(self, y: AvlNode) -> AvlNode:
"""Perform right rotation on node y, return new root."""
if not y or not y.left:
return y
x = y.left
y.left = x.right
x.right = y
self._update_height(y) # Child first (now lower in tree)
self._update_height(x) # Then parent
return x
def _rebalance(self, node: AvlNode) -> AvlNode:
"""Rebalance node if needed and return the (potentially new) root."""
self._update_height(node)
balance = self._balance_factor(node)
# Left-heavy
if balance > 1:
if self._balance_factor(node.left) < 0:
# Left-Right case: rotate left child left, then node right
node.left = self._rotate_left(node.left)
return self._rotate_right(node)
# Right-heavy
if balance < -1:
if self._balance_factor(node.right) > 0:
# Right-Left case: rotate right child right, then node left
node.right = self._rotate_right(node.right)
return self._rotate_left(node)
return node
# -------------------------------------------------------------------------
# Public Operations
# -------------------------------------------------------------------------
def add(self, val) -> None:
"""Add a value to the tree. Raises KeyError if duplicate."""
def _add_recursive(node: AvlNode, val) -> AvlNode:
if not node:
return AvlNode(val)
if val < node.val:
node.left = _add_recursive(node.left, val)
elif val > node.val:
node.right = _add_recursive(node.right, val)
else:
raise KeyError("Node with this value already in tree.")
return self._rebalance(node)
self.root = _add_recursive(self.root, val)
def find_successor(self, node: AvlNode) -> AvlNode | None:
"""
Find the in-order successor of a node.
If node has right subtree: successor is leftmost in right subtree.
Otherwise: successor is first ancestor where node is in left subtree.
"""
if node.right:
leftmost = node.right
while leftmost.left:
leftmost = leftmost.left
return leftmost
# Walk from root, tracking last left turn
successor = None
current = self.root
while current and current.val != node.val:
if node.val < current.val:
successor = current
current = current.left
else:
current = current.right
return successor
def delete(self, val) -> None:
"""Delete a value from the tree. No-op if value not found."""
def _delete_recursive(node: AvlNode, val) -> AvlNode | None:
if not node:
return None
if val < node.val:
node.left = _delete_recursive(node.left, val)
elif val > node.val:
node.right = _delete_recursive(node.right, val)
else:
# Found node to delete
if node.left and node.right:
# Two children: replace with successor
successor = self.find_successor(node)
node.val = successor.val
node.right = _delete_recursive(node.right, successor.val)
elif node.left:
return node.left
elif node.right:
return node.right
else:
return None
return self._rebalance(node)
self.root = _delete_recursive(self.root, val)
def search(self, val) -> AvlNode | None:
"""Search for a value. Returns the node if found, None otherwise."""
node = self.root
while node:
if val == node.val:
return node
node = node.left if val < node.val else node.right
return None
# -------------------------------------------------------------------------
# Traversal Methods
# -------------------------------------------------------------------------
class TraverseOrder(Enum):
"""Enumeration of tree traversal orders."""
preorder = 1
inorder = 2
postorder = 3
def traverse(self, order: TraverseOrder) -> list:
"""Traverse the tree in the specified order. Returns list of values."""
result = []
def _preorder(node: AvlNode):
if not node:
return
result.append(node.val)
_preorder(node.left)
_preorder(node.right)
def _inorder(node: AvlNode):
if not node:
return
_inorder(node.left)
result.append(node.val)
_inorder(node.right)
def _postorder(node: AvlNode):
if not node:
return
_postorder(node.left)
_postorder(node.right)
result.append(node.val)
traversals = {
AvlTree.TraverseOrder.preorder: _preorder,
AvlTree.TraverseOrder.inorder: _inorder,
AvlTree.TraverseOrder.postorder: _postorder,
}
if order not in traversals:
raise TypeError("Invalid traverse order passed.")
traversals[order](self.root)
return result
def inorder_traversal(self) -> list:
"""Return values in sorted (in-order) sequence."""
return self.traverse(AvlTree.TraverseOrder.inorder)
def levels_traversal(self) -> dict[int, list]:
"""Return values grouped by level (breadth-first). Level 0 is root."""
if not self.root:
return {}
levels = {}
queue = [(self.root, 0)]
for node, level in queue:
if level not in levels:
levels[level] = []
levels[level].append(node.val)
if node.left:
queue.append((node.left, level + 1))
if node.right:
queue.append((node.right, level + 1))
return levels
def min_depth(self) -> int:
"""Return minimum depth (shortest path from root to a leaf). -1 if empty."""
if not self.root:
return -1
min_lvl = -1
def _dfs(node: AvlNode, depth: int):
nonlocal min_lvl
if not node:
return
if not node.left and not node.right:
if min_lvl == -1 or depth < min_lvl:
min_lvl = depth
_dfs(node.left, depth + 1)
_dfs(node.right, depth + 1)
_dfs(self.root, 0)
return min_lvl
def max_depth(self) -> int:
"""Return maximum depth (longest path from root to a leaf). 0 for single node."""
if not self.root:
return -1
max_lvl = 0
def _dfs(node: AvlNode, depth: int):
nonlocal max_lvl
if not node:
return
if depth > max_lvl:
max_lvl = depth
_dfs(node.left, depth + 1)
_dfs(node.right, depth + 1)
_dfs(self.root, 0)
return max_lvl
# Example usage:
if __name__ == "__main__":
tree = AvlTree()
# Insert values
for val in [10, 20, 30, 40, 50, 25]:
tree.add(val)
# Traverse in different orders
print("Inorder: ", tree.traverse(AvlTree.TraverseOrder.inorder)) # [10, 20, 25, 30, 40, 50]
print("Preorder: ", tree.traverse(AvlTree.TraverseOrder.preorder))
print("Postorder:", tree.traverse(AvlTree.TraverseOrder.postorder))
print("By levels:", tree.levels_traversal())
# Search
print("Search 25:", tree.search(25)) # AvlNode with val=25
print("25 in tree:", 25 in tree) # True
# Delete
tree.delete(40)
tree.delete(30)
print("After deletions:", tree.inorder_traversal())
About AVL Tree
How AVL Tree Works
An AVL tree is a self-balancing binary search tree where the heights of the two child subtrees of any node differ by at most one. When this balance is violated, rotations restore it. This guarantees O(log n) worst-case time for all operations.
After each insertion or deletion, check the balance factor (left height minus right height) of each ancestor. If any node becomes unbalanced (factor > 1 or < -1), apply one of four rotations: left, right, left-right, or right-left to restore balance.
Complexity
- Time
- O(log n)
- Space
- O(n)
When to Use AVL Tree
- Databases and file systems requiring guaranteed lookup times
- Memory-constrained systems where worst-case performance matters
- Applications where frequent lookups dominate insertions