AVL Tree (Self-Balancing BST)
A self-balancing binary search tree where the heights of the two child subtrees of any node differ by at most one. Named after inventors Adelson-Velsky and Landis (1962), AVL trees guarantee O(log n) time for search, insert, and delete operations by maintaining balance through rotations. It was the first self-balancing binary search tree to be invented.
Visualization
Interactive visualization for AVL Tree (Self-Balancing BST)
Interactive visualization with step-by-step execution
Implementation
1class AVLNode {
2 val: number;
3 left: AVLNode | null = null;
4 right: AVLNode | null = null;
5 height: number = 1;
6
7 constructor(val: number) {
8 this.val = val;
9 }
10}
11
12class AVLTree {
13 root: AVLNode | null = null;
14
15 private getHeight(node: AVLNode | null): number {
16 return node ? node.height : 0;
17 }
18
19 private getBalance(node: AVLNode | null): number {
20 return node ? this.getHeight(node.left) - this.getHeight(node.right) : 0;
21 }
22
23 private updateHeight(node: AVLNode): void {
24 node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));
25 }
26
27 private rotateRight(y: AVLNode): AVLNode {
28 const x = y.left!;
29 const T2 = x.right;
30
31 x.right = y;
32 y.left = T2;
33
34 this.updateHeight(y);
35 this.updateHeight(x);
36
37 return x;
38 }
39
40 private rotateLeft(x: AVLNode): AVLNode {
41 const y = x.right!;
42 const T2 = y.left;
43
44 y.left = x;
45 x.right = T2;
46
47 this.updateHeight(x);
48 this.updateHeight(y);
49
50 return y;
51 }
52
53 insert(val: number): void {
54 this.root = this.insertNode(this.root, val);
55 }
56
57 private insertNode(node: AVLNode | null, val: number): AVLNode {
58 if (!node) return new AVLNode(val);
59
60 if (val < node.val) {
61 node.left = this.insertNode(node.left, val);
62 } else if (val > node.val) {
63 node.right = this.insertNode(node.right, val);
64 } else {
65 return node; // Duplicate values not allowed
66 }
67
68 this.updateHeight(node);
69 const balance = this.getBalance(node);
70
71 // Left-Left Case
72 if (balance > 1 && val < node.left!.val) {
73 return this.rotateRight(node);
74 }
75
76 // Right-Right Case
77 if (balance < -1 && val > node.right!.val) {
78 return this.rotateLeft(node);
79 }
80
81 // Left-Right Case
82 if (balance > 1 && val > node.left!.val) {
83 node.left = this.rotateLeft(node.left!);
84 return this.rotateRight(node);
85 }
86
87 // Right-Left Case
88 if (balance < -1 && val < node.right!.val) {
89 node.right = this.rotateRight(node.right!);
90 return this.rotateLeft(node);
91 }
92
93 return node;
94 }
95}Deep Dive
Theoretical Foundation
AVL tree maintains balance factor (height difference between left and right subtrees) of -1, 0, or 1 for every node. When this property is violated during insertion/deletion, the tree performs rotations (single or double) to restore balance. The height of an AVL tree with n nodes is always O(log n), guaranteeing efficient operations.
Complexity
Time
O(log n)
O(log n)
O(log n)
Space
O(n)
Applications
Industry Use
Database indexing (when reads >> writes)
In-memory databases
File system implementations
Graphics rendering (spatial partitioning)
Compiler symbol tables
Network routing tables
Auto-complete systems
Use Cases
Related Algorithms
Segment Tree (Range Query Tree)
Segment Tree is a binary tree data structure for storing intervals/segments that enables efficient range queries (sum, min, max, GCD) and updates in O(log n) time. Each node represents an interval, with leaves representing single elements. Essential for competitive programming, it solves problems like range sum queries with updates, which would be O(n) with arrays but becomes O(log n) with segment trees.
Fenwick Tree (Binary Indexed Tree - BIT)
A data structure that can efficiently update elements and calculate prefix sums in O(log n) time. Also known as Binary Indexed Tree (BIT), invented by Peter Fenwick in 1994. Fenwick trees are more space-efficient and simpler than segment trees for range sum queries, using only O(n) space compared to segment tree's O(4n).
Lowest Common Ancestor (LCA)
Lowest Common Ancestor (LCA) finds the deepest node that is an ancestor of two given nodes in a tree. This fundamental tree query operation has applications in computational biology (phylogenetic trees), version control systems (finding merge base), network routing, and range queries. Multiple algorithms exist: simple recursive O(n), binary lifting O(log n) per query after O(n log n) preprocessing, and Tarjan's offline algorithm for batch queries.
Morris Traversal (Threaded Binary Tree)
Morris Traversal is a brilliant tree traversal technique that achieves O(1) space complexity without using recursion or an explicit stack. Invented by Joseph H. Morris in 1979, it temporarily modifies the tree structure by creating 'threads' (temporary links) that allow the algorithm to traverse back to ancestors. After traversal, the original tree structure is restored. This makes it ideal for memory-constrained environments and demonstrates creative problem-solving in algorithm design.