45:"/_next/static/chunks/33yus346z0l_n.js" 46:"/_next/static/chunks/2j22cxchii_xx.js" 47:"/_next/static/chunks/0iv56yrji_20j.js" 48:"/_next/static/chunks/32izpn90gvm22.js" 49:"/_next/static/chunks/3j8bi-zu9bqs4.js" 4a:"/_next/static/chunks/1z-pox7hqp2x3.js" 4b:"/_next/static/chunks/20w4eaqlekefm.js" 4c:"/_next/static/chunks/1tn-0fivsxsv1.js" 4d:"/_next/static/chunks/09nq57stwzkgf.js" 4e:"/_next/static/chunks/3m1xjj5kw5fie.js" 4f:"/_next/static/chunks/0gafyzg9j9yqj.js" 50:"/_next/static/chunks/3k2gyg36fnag_.js" 51:"/_next/static/chunks/3bgoyiso1rhn7.js" 52:"/_next/static/chunks/3cstd6xzfli_o.js" 53:"/_next/static/chunks/253gnmj0-cj17.js" 54:"/_next/static/chunks/0hlb44ca7-4a2.js" 55:"/_next/static/chunks/20329i6m_04t6.js" 56:"/_next/static/chunks/40mq7ggq-ozo4.js" 57:"/_next/static/chunks/082jo-0ajazgr.js" 58:"/_next/static/chunks/2ozcrjb_hh74t.js" 59:"/_next/static/chunks/01a-3hvnqu8wl.js" 5a:"/_next/static/chunks/05i8en-x14ibi.js" 5b:"/_next/static/chunks/3m0r7x0jt5wm7.js" 5c:"/_next/static/chunks/2k8pepwc4pxns.js" 5d:"/_next/static/chunks/0wa9m1-tphf9u.js" 5e:"/_next/static/chunks/30jdm3dwz834g.js" 5f:"/_next/static/chunks/0k9bl6dipnsvu.js" 60:"/_next/static/chunks/18ggtgz2yf759.js" 61:"/_next/static/chunks/0i3-eynrkvqi7.js" 62:I[593304,["$2a","$2b","$2c","$2d","$2e","$2f","$45","$46","$47","$48","$49","$4a","$4b","$4c","$4d","$4e","$4f","$50","$51","$52","$53","$54","$55","$56","$57","$58","$59","$5a","$5b","$5c","$5d","$5e","$5f","$60","$61"],"OwnedHydration"] 63:T53f,class AVLNode: """ A node in an AVL tree. Each node stores: - key: The value used for BST ordering - left, right: Pointers to child nodes - height: Height of the subtree rooted at this node Note: We store height rather than balance factor because: 1. Height is needed to compute balance factor anyway 2. Height updates are straightforward during rotations 3. Balance factor can be derived: bf = left.height - right.height """ def __init__(self, key): self.key = key self.left = None # Left child self.right = None # Right child self.height = 0 # Height of this node (leaf = 0) def get_height(node): """Return height of a node, handling None as -1.""" if node is None: return -1 return node.height def update_height(self): """Recalculate height based on children's heights.""" left_height = AVLNode.get_height(self.left) right_height = AVLNode.get_height(self.right) self.height = 1 + max(left_height, right_height) def balance_factor(self): """Calculate balance factor: left height - right height.""" left_height = AVLNode.get_height(self.left) right_height = AVLNode.get_height(self.right) return left_height - right_height64:T489,class AVLNode { key: T; left: AVLNode | null; right: AVLNode | null; height: number; // Height of subtree rooted at this node constructor(key: T) { this.key = key; this.left = null; this.right = null; this.height = 0; // Leaf nodes have height 0 } /** * Get height of a node, treating null as height -1 * This convention simplifies balance factor calculations */ static getHeight(node: AVLNode | null): number { return node === null ? -1 : node.height; } /** * Update this node's height based on children * Must be called after any structural change to children */ updateHeight(): void { const leftHeight = AVLNode.getHeight(this.left); const rightHeight = AVLNode.getHeight(this.right); this.height = 1 + Math.max(leftHeight, rightHeight); } /** * Calculate balance factor: left height - right height * Valid AVL: balance factor ∈ {-1, 0, +1} */ balanceFactor(): number { return AVLNode.getHeight(this.left) - AVLNode.getHeight(this.right); } }65:T489,public class AVLNode> { K key; AVLNode left; AVLNode right; int height; // Height of subtree rooted at this node public AVLNode(K key) { this.key = key; this.left = null; this.right = null; this.height = 0; // Leaf nodes have height 0 } /** * Get height of a node, treating null as height -1 * This convention simplifies balance factor calculations */ public static > int getHeight(AVLNode node) { return node == null ? -1 : node.height; } /** * Update this node's height based on children * Must be called after any structural change to children */ public void updateHeight() { int leftHeight = getHeight(this.left); int rightHeight = getHeight(this.right); this.height = 1 + Math.max(leftHeight, rightHeight); } /** * Calculate balance factor: left height - right height * Valid AVL: balance factor ∈ {-1, 0, +1} */ public int balanceFactor() { return getHeight(this.left) - getHeight(this.right); } }43:["$","$L62",null,{"owner":"anonymous","state":{"mutations":[],"queries":[{"dehydratedAt":1792294845139,"state":{"data":{"json":{"id":"seed_362da0b8406bcb78c5b3c4bc7abd0d84","slug":"avl-trees-rotations-balancing","category":"Data Structures & Algorithms","topic":"AVL Trees — Rotations & Balancing","title":"AVL Trees — Rotations & Balancing","description":"Master AVL trees, the first self-balancing binary search tree ever invented. Understand their elegant balance invariant, learn how rotations restore balance after insertions and deletions, and analyze the guaranteed O(log n) performance for all operations.","difficulty":"INTERMEDIATE","estimatedMinutes":90,"pages":[{"id":"seed_b7ecc1c766fd1cc66a959e9805ddd7b4","title":"What is an AVL Tree","order":0,"content":[{"id":"opening-hook","title":"The Quest for Balance","content":[{"data":{"content":"In 1962, two Soviet mathematicians—**Georgy Adelson-Velsky** and **Evgenii Landis**—published a groundbreaking paper that would forever change how we think about binary search trees. They had solved a problem that had haunted computer scientists since the invention of BSTs: the dreaded **degenerate tree**.\n\nTheir solution, named after their initials (AVL), was the world's first **self-balancing binary search tree**. It introduced a deceptively simple invariant: at every node, the heights of the left and right subtrees can differ by at most one. This single constraint, combined with an elegant mechanism for restoration, guarantees that an AVL tree with *n* elements never exceeds a height of approximately 1.44 log₂(n)—ensuring O(log n) operations no matter what order elements are inserted."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will:\n\n• Understand the precise definition of an AVL tree and what distinguishes it from a regular BST\n• Know the historical significance of AVL trees in computer science\n• Grasp the height-balance invariant and why it guarantees logarithmic operations\n• Recognize AVL trees visually and understand their structural properties\n• Appreciate why the 'balance factor ∈ {-1, 0, +1}' constraint is both necessary and sufficient for efficient operations","variant":"info"},"type":"callout"}]},{"id":"problem-avl-solves","title":"The Problem AVL Trees Solve","content":[{"data":{"content":"Before diving into AVL trees, let's crystallize the problem they were designed to solve. Recall from our study of Binary Search Trees that:\n\n**The BST property guarantees that search, insertion, and deletion all take O(h) time**, where *h* is the height of the tree.\n\nIn an ideal world—a perfectly balanced tree—this height is O(log n). But in the worst case—a completely degenerate tree—the height degrades to O(n), reducing our elegant search tree to a glorified linked list."},"type":"text"},{"data":{"rows":[["Perfectly Balanced","O(log n)","O(log n)","O(log n)","O(log n)"],["Randomly Built","O(log n) expected","O(log n) expected","O(log n) expected","O(log n) expected"],["Sorted Insertion","O(n)","O(n)","O(n)","O(n)"],["Reverse-Sorted","O(n)","O(n)","O(n)","O(n)"]],"caption":"BST Performance: Best vs. Worst Case","headers":["Scenario","Tree Height","Search Time","Insert Time","Delete Time"]},"type":"table"},{"data":{"content":"**The fundamental insight:** We cannot control the order in which data arrives. Users might register in alphabetical order. Transactions might have incrementing IDs. Sensor readings might arrive in timestamp order. Any assumption about 'random' insertion is dangerous in production systems.\n\n**What we need is a tree that *automatically* maintains balance**, adjusting its structure after each modification to ensure the height never exceeds O(log n). This is precisely what AVL trees provide."},"type":"text"},{"data":{"icon":"AlertCircle","title":"The Cost of Worst-Case Degradation","content":"Consider a database index built on a standard BST. If 1 million records are inserted in sorted order:\n\n• Standard BST: Height = 1,000,000 → Each search takes ~1 million comparisons\n• AVL Tree: Height ≈ 29 → Each search takes ~29 comparisons\n\nThat's a 34,000× difference in performance. At 1μs per comparison, a search in the degenerate BST takes 1 second; in the AVL tree, it takes 29 microseconds.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":1},{"id":"avl-definition","title":"Formal Definition of an AVL Tree","content":[{"data":{"content":"An AVL tree is a binary search tree that satisfies an additional structural constraint called the **AVL property** or **height-balance property**. Let's build this definition precisely."},"type":"text"},{"data":{"icon":"Info","title":"Definition: Height of a Node","content":"The **height** of a node in a binary tree is the length of the longest path from that node to a leaf. By convention:\n\n• A null pointer (empty subtree) has height **-1**\n• A leaf node has height **0**\n• An internal node has height = 1 + max(height of left child, height of right child)","variant":"note"},"type":"callout"},{"data":{"content":"**Definition: Balance Factor**\n\nFor any node *v* in a binary tree, the **balance factor** is defined as:\n\n```\nbalanceFactor(v) = height(v.left) - height(v.right)\n```\n\nThe balance factor tells us how 'lopsided' a node is:\n- **Negative balance factor**: The right subtree is taller\n- **Zero balance factor**: Both subtrees have equal height\n- **Positive balance factor**: The left subtree is taller"},"type":"text"},{"data":{"icon":"CheckCircle","title":"The AVL Property (Height-Balance Invariant)","content":"A binary search tree is an **AVL tree** if and only if:\n\n**For every node v in the tree: balanceFactor(v) ∈ {-1, 0, +1}**\n\nIn words: at every node, the heights of the left and right subtrees differ by at most 1. This invariant must hold at ALL nodes, not just the root.","variant":"success"},"type":"callout"},{"data":{"content":"**Why 'at most one' and not 'exactly equal'?**\n\nYou might wonder why we allow a height difference of 1 rather than requiring perfect balance. The answer is both practical and mathematical:\n\n1. **Perfect balance isn't always possible.** A tree with 6 nodes cannot have equal-height subtrees at every node. Attempting perfect balance would require padding with dummy nodes.\n\n2. **Balance factor of ±1 is sufficient.** As we'll prove later, allowing a height difference of 1 still guarantees that the tree height is O(log n). Specifically, an AVL tree of height *h* contains at least F(h+3) - 1 nodes, where F(i) is the i-th Fibonacci number.\n\n3. **It minimizes rebalancing overhead.** Stricter invariants would require more frequent rotations, increasing constant factors."},"type":"text"},{"data":{"left":[{"data":{"items":["Every node has balance factor in {-1, 0, +1}","The BST property holds at all nodes","May be 'heavy' on either side at different nodes","Includes perfectly balanced trees as a subset"],"title":{"icon":"CheckCircle","text":"Valid AVL Trees","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["Any node with |balance factor| ≥ 2","Even if just ONE node violates the invariant","Degenerate (linear) trees","Trees violating the BST property"],"title":{"icon":"XCircle","text":"Invalid AVL Trees","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"}],"titleType":"number","titleNumber":2},{"id":"visualizing-avl","title":"Visualizing AVL Trees","content":[{"data":{"content":"Let's develop visual intuition for what makes an AVL tree. Understanding this 'shape' helps you recognize balanced and unbalanced configurations instantly."},"type":"text"},{"data":{"height":"400px","mermaidSyntax":"graph TD\n subgraph \"Valid AVL Tree (Height 3)\"\n A((50\nbf=0))\n B((25\nbf=0))\n C((75\nbf=+1))\n D((10\nbf=0))\n E((30\nbf=0))\n F((60\nbf=0))\n G((5\nbf=0))\n H((15\nbf=0))\n \n A --> B\n A --> C\n B --> D\n B --> E\n C --> F\n C -.-> |null| N1[\" \"]\n D --> G\n D --> H\n end\n \n style A fill:#10b981,stroke:#059669,color:#fff\n style B fill:#10b981,stroke:#059669,color:#fff\n style C fill:#10b981,stroke:#059669,color:#fff\n style D fill:#10b981,stroke:#059669,color:#fff\n style E fill:#10b981,stroke:#059669,color:#fff\n style F fill:#10b981,stroke:#059669,color:#fff\n style G fill:#10b981,stroke:#059669,color:#fff\n style H fill:#10b981,stroke:#059669,color:#fff\n style N1 fill:none,stroke:none"},"type":"mermaid-excalidraw"},{"data":{"content":"In the tree above, every node's balance factor is annotated as 'bf'. Notice:\n\n- **Node 50** (root): Left subtree has height 2, right subtree has height 2 → bf = 0\n- **Node 25**: Both subtrees have height 1 → bf = 0 \n- **Node 75**: Left subtree has height 1, right subtree is null (height -1) → bf = 1 - (-1) = +2... Wait!\n\nActually, let me correct this visualization. Node 75 having only a left child of height 0 with no right child would give bf = 0 - (-1) = +1, which IS valid. The key is that 75's left subtree (rooted at 60) has height 0, and its right subtree is null (height -1), giving bf = 0 - (-1) = +1. This is still valid!"},"type":"text"},{"data":{"icon":"Lightbulb","title":"Visual Heuristic for AVL Trees","content":"When looking at a tree, check each node mentally:\n\n1. Look at the maximum depth reachable going left vs. going right\n2. If the difference at any node exceeds 1, it's NOT an AVL tree\n3. Remember: null children have height -1, so a node with one child has bf ∈ {-1, +1}","variant":"tip"},"type":"callout"},{"data":{"content":"**Example of an INVALID AVL Tree:**"},"type":"text"},{"data":{"height":"350px","mermaidSyntax":"graph TD\n subgraph \"INVALID: Node 50 has bf = +2\"\n A((50\nbf=+2))\n B((25\nbf=+1))\n C((75\nbf=0))\n D((10\nbf=0))\n E((5\nbf=0))\n \n A --> B\n A --> C\n B --> D\n B -.-> |null| N1[\" \"]\n D --> E\n D -.-> |null| N2[\" \"]\n end\n \n style A fill:#ef4444,stroke:#dc2626,color:#fff\n style B fill:#fbbf24,stroke:#d97706,color:#000\n style C fill:#10b981,stroke:#059669,color:#fff\n style D fill:#10b981,stroke:#059669,color:#fff\n style E fill:#10b981,stroke:#059669,color:#fff\n style N1 fill:none,stroke:none\n style N2 fill:none,stroke:none"},"type":"mermaid-excalidraw"},{"data":{"content":"Here, the root node 50 has a left subtree of height 3 and a right subtree of height 1. The balance factor is +2, which violates the AVL property. This tree would need **rebalancing** to become a valid AVL tree."},"type":"text"}],"titleType":"number","titleNumber":3},{"id":"height-guarantee","title":"The Height Guarantee: Why AVL Trees Are Efficient","content":[{"data":{"content":"The most important property of AVL trees is the **guaranteed height bound**. This is what transforms BST operations from potentially O(n) to always O(log n)."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Theorem: AVL Height Bound","content":"For an AVL tree with n nodes:\n\n**height ≤ 1.44 × log₂(n + 2) - 0.328**\n\nSimplified: **height = O(log n)**\n\nThis means an AVL tree is never more than about 44% taller than a perfectly balanced tree.","variant":"success"},"type":"callout"},{"data":{"content":"**Proof Sketch (via Fibonacci numbers):**\n\nTo prove this, we ask: What is the *minimum* number of nodes in an AVL tree of height h? If we can show this minimum grows exponentially with h, then h must be logarithmic in n.\n\nLet N(h) be the minimum nodes in an AVL tree of height h.\n\n**Base cases:**\n- N(-1) = 0 (empty tree)\n- N(0) = 1 (single node)\n- N(1) = 2 (root with one child)\n\n**Recurrence:**\nTo build a minimal AVL tree of height h:\n- We need a root\n- One subtree must have height h-1 (to achieve overall height h)\n- The other subtree can have height h-2 (minimum allowed by AVL property)\n- Both subtrees must be minimal AVL trees themselves\n\nThus: **N(h) = 1 + N(h-1) + N(h-2)**\n\nThis is exactly the Fibonacci recurrence! In fact, N(h) = F(h+3) - 1, where F(i) is the i-th Fibonacci number."},"type":"text"},{"data":{"rows":[["0","1","F(3) - 1 = 2 - 1 = 1"],["1","2","F(4) - 1 = 3 - 1 = 2"],["2","4","F(5) - 1 = 5 - 1 = 4"],["3","7","F(6) - 1 = 8 - 1 = 7"],["4","12","F(7) - 1 = 13 - 1 = 12"],["5","20","F(8) - 1 = 21 - 1 = 20"],["10","143","F(13) - 1 = 144 - 1 = 143"],["20","17,710","F(23) - 1 = 17,711 - 1"]],"caption":"Minimum Nodes in AVL Trees of Given Heights","headers":["Height","N(h) = Min Nodes","Fibonacci Relation"]},"type":"table"},{"data":{"content":"Since Fibonacci numbers grow as F(n) ≈ φⁿ/√5 where φ ≈ 1.618 (the golden ratio), we have:\n\nn ≥ N(h) ≈ φʰ⁺³/√5\n\nSolving for h:\n\nh ≤ logᵩ(n√5) - 3 ≈ 1.44 log₂(n) - 1.33\n\n**The takeaway:** No matter how adversarially data is inserted, an AVL tree of n nodes has height at most ~1.44 log₂(n). This is the *worst* case, not the average case. Most AVL trees are even shorter."},"type":"text"},{"data":{"icon":"Info","title":"Comparison with Perfect Balance","content":"A perfectly balanced tree has height exactly ⌊log₂(n)⌋. An AVL tree has height at most 1.44 × log₂(n). The ratio 1.44 comes from the golden ratio: logᵩ(2) ≈ 1.44.\n\nIn practice, this ~44% overhead in height translates to only a few extra levels even for very large trees. For 1 billion nodes: perfect balance = 30 levels, worst AVL = 43 levels. That's 13 extra comparisons per search—a tiny price for *guaranteed* performance.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"avl-vs-others","title":"AVL Trees in Context: Why They Matter","content":[{"data":{"content":"AVL trees occupy a unique position in the landscape of data structures. Understanding their role helps you know when to use them and when alternatives might be better."},"type":"text"},{"data":{"items":["**First self-balancing BST (1962)** — Adelson-Velsky and Landis invented AVL trees before Red-Black trees (1972), B-trees (1970), or any other balanced tree variant. They proved that efficient, worst-case O(log n) search trees were possible.","**Elegant mathematical foundation** — The connection between minimal AVL trees and Fibonacci numbers is one of the most beautiful results in data structures. It demonstrates deep connections between combinatorics and computer science.","**Practical in-memory data structure** — AVL trees are still used today in memory-intensive applications where lookup performance is critical. The Linux kernel uses AVL trees for certain memory management tasks.","**Teaching tool** — AVL trees are often taught as the canonical example of a self-balancing tree because their invariant is simple to state and their rebalancing mechanism (rotations) is intuitive to visualize."],"title":{"icon":"Sparkles","text":"Historical Significance","type":"icon","color":"primary","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"rows":[["Worst-case height","O(n)","O(log n)"],["Search (worst)","O(n)","O(log n)"],["Insert (worst)","O(n)","O(log n)"],["Delete (worst)","O(n)","O(log n)"],["Space overhead","None","O(n) for height/balance info"],["Implementation complexity","Simple","Moderate (rotations required)"],["Insertion/deletion cost","Just BST operations","BST + potential rotations"]],"caption":"AVL Trees vs. Standard BSTs","headers":["Property","Standard BST","AVL Tree"]},"type":"table"},{"data":{"content":"**When to Use AVL Trees:**\n\n1. **Lookup-heavy workloads**: AVL trees maintain stricter balance than Red-Black trees, resulting in shallower trees and faster lookups. If you search far more often than you insert/delete, AVL is excellent.\n\n2. **Real-time systems**: The O(log n) guarantee matters when worst-case latency is unacceptable. Games, trading systems, and control systems benefit from predictable performance.\n\n3. **Database indices** (in-memory): When data lives entirely in RAM and rapid key lookup is essential.\n\n4. **Ordered data structures**: When you need not just lookup buy also predecessor/successor, range queries, and ordered iteration—all of which are O(log n) in AVL trees."},"type":"text"},{"data":{"icon":"Lightbulb","title":"AVL vs. Red-Black Trees","content":"You might have heard of Red-Black trees (used in Java's TreeMap, C++'s std::map). The key tradeoff:\n\n• **AVL trees**: Stricter balance → fewer levels → faster lookups\n• **Red-Black trees**: Looser balance → fewer rotations on insert/delete → faster modifications\n\nIn practice, the differences are small. Both are O(log n) for all operations. Choose AVL for read-heavy workloads; Red-Black for write-heavy.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"avl-node-structure","title":"The Structure of an AVL Node","content":[{"data":{"content":"To implement an AVL tree, each node must store additional information beyond the standard BST fields. Let's examine the complete node structure."},"type":"text"},{"data":{"fileName":"avl_node.py","languages":[{"code":"$63","label":"Python","value":"python"},{"code":"$64","label":"TypeScript","value":"typescript"},{"code":"$65","label":"Java","value":"java"}]},"type":"code"},{"data":{"content":"**Key Design Decisions:**\n\n1. **Store height, not balance factor**: While you could store balance factor directly (it's just -1, 0, or +1), storing height is more robust. Heights are needed for rotation calculations, and deriving balance factor from heights is trivial.\n\n2. **Null convention**: Null children have height -1. This ensures that:\n - A leaf (no children) has height 0 = max(-1, -1) + 1\n - Single-child nodes have correct balance factors\n\n3. **Update height after changes**: Any operation that modifies the tree structure (insertion, deletion, rotation) must update affected nodes' heights."},"type":"text"},{"data":{"icon":"Info","title":"Space Overhead","content":"Each AVL node requires one extra integer (the height field) compared to a standard BST node. For 1 million nodes with 32-bit integers, this is just 4 MB of extra space—negligible for the guaranteed O(log n) performance it enables.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"summary","title":"Summary: Understanding AVL Trees","content":[{"data":{"content":"Let's consolidate what we've learned about AVL trees before moving on to the mechanics of how they maintain balance."},"type":"text"},{"data":{"type":"ordered","items":["**AVL trees are self-balancing BSTs** — They automatically maintain balance after insertions and deletions, eliminating the O(n) worst case of standard BSTs.","**The AVL property is simple: |balance factor| ≤ 1 at every node** — The balance factor is the difference between left and right subtree heights.","**Height is guaranteed to be O(log n)** — Specifically, height ≤ 1.44 log₂(n), ensuring all operations are logarithmic.","**The height bound derives from Fibonacci numbers** — Minimal AVL trees follow the Fibonacci recurrence, connecting this data structure to beautiful mathematics.","**AVL nodes store height information** — This O(n) space overhead enables O(1) balance factor computation and efficient rebalancing.","**AVL trees excel at lookup-heavy workloads** — Their stricter balance (compared to Red-Black trees) makes them faster for searches."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's Next:**\n\nWe've defined what an AVL tree IS—but how does it STAY balanced? When we insert or delete a node, the balance factors change. If any node's balance factor becomes ±2, the AVL property is violated.\n\nIn the next section, we'll deep-dive into the **balance factor** concept, examining exactly how insertions and deletions affect balance factors throughout the tree. Then we'll learn about **rotations**—the elegant mechanism AVL trees use to restore balance in O(1) time."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now understand what an AVL tree is: a binary search tree where every node has a balance factor of -1, 0, or +1. This simple invariant guarantees O(log n) height, transforming BST operations from potentially linear to always logarithmic. Next, we'll explore the balance factor in depth and prepare for understanding rotations.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":7}],"isLocked":false},{"id":"seed_0262df18e2afa34736adf91d8711cf49","title":"Balance Factor — Height Difference Analysis","order":1,"content":null,"isLocked":true},{"id":"seed_edf173622dce7f51b149b886d1515e52","title":"Single and Double Rotations","order":2,"content":null,"isLocked":true},{"id":"seed_87ac44af89976e1031f2524ecdbac3c7","title":"How Rotations Restore Balance","order":3,"content":null,"isLocked":true},{"id":"seed_bba1d4fcf39bad71f7334530b11a527a","title":"Time Complexity of AVL Operations","order":4,"content":null,"isLocked":true}]}},"dataUpdateCount":1,"dataUpdatedAt":1792294844885,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getModule"],{"input":{"slug":"avl-trees-rotations-balancing"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getModule\"],{\"input\":{\"slug\":\"avl-trees-rotations-balancing\"},\"type\":\"query\"}]"},{"dehydratedAt":1792294845140,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792294844883,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getProgress"],{"input":{"moduleId":"seed_362da0b8406bcb78c5b3c4bc7abd0d84"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getProgress\"],{\"input\":{\"moduleId\":\"seed_362da0b8406bcb78c5b3c4bc7abd0d84\"},\"type\":\"query\"}]"},{"dehydratedAt":1792294845140,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792294844884,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","get"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_0262df18e2afa34736adf91d8711cf49"},"type":"query"}],"queryHash":"[[\"feedback\",\"get\"],{\"input\":{\"contentId\":\"seed_0262df18e2afa34736adf91d8711cf49\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792294845140,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792294844884,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","getUserLike"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_0262df18e2afa34736adf91d8711cf49"},"type":"query"}],"queryHash":"[[\"feedback\",\"getUserLike\"],{\"input\":{\"contentId\":\"seed_0262df18e2afa34736adf91d8711cf49\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792294845140,"state":{"data":{"json":[]},"dataUpdateCount":1,"dataUpdatedAt":1792294844884,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["highlights","getHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_0262df18e2afa34736adf91d8711cf49"},"type":"query"}],"queryHash":"[[\"highlights\",\"getHighlights\"],{\"input\":{\"contentId\":\"seed_0262df18e2afa34736adf91d8711cf49\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792294845140,"state":{"data":"$undefined","dataUpdateCount":0,"dataUpdatedAt":0,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"pending","fetchStatus":"fetching"},"queryKey":[["highlights","getPopularHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_0262df18e2afa34736adf91d8711cf49","minCount":2},"type":"query"}],"queryHash":"[[\"highlights\",\"getPopularHighlights\"],{\"input\":{\"contentId\":\"seed_0262df18e2afa34736adf91d8711cf49\",\"contentType\":\"LEARNING_PAGE\",\"minCount\":2},\"type\":\"query\"}]","promise":"$@66"}]},"children":"$L67"}]