← Back to DSA Course | Chapter 11: Trees | Lesson 6 of 10

AVL Tree क्या है

एक AVL tree एक seesaw जैसी है जो खुद को ठीक करती है: जब भी एक side बहुत भारी हो जाए, यह दोनों sides को लगभग balanced रखने के लिए rotate करती है।

In this page:

  1. AVL Idea
  2. Rotations
  3. Four Cases
  4. Double Rotations
  5. AVL Practice
Syntax
markup 
balance = height(node.left) - height(node.right)
if balance > 1:
    node = rotate_right(node)    # left-heavy
elif balance < -1:
    node = rotate_left(node)     # right-heavy

AVL Idea

एक AVL tree एक binary search tree है जो अपने आप खुद को balanced रखती है, यह गारंटी देते हुए कि किसी भी node के left और right subtrees के बीच height का difference कभी एक से ज़्यादा नहीं होता। यह worst-case degradation रोकता है जो एक plain BST sorted input से बनने पर झेल सकता है।

उदाहरण: AVL Idea

#include <iostream>
using namespace std;
struct Node { int val, height; Node *left, *right; };
int h(Node* n) { return n ? n->height : 0; }
int balance(Node* n) { return n ? h(n->left) - h(n->right) : 0; }
int main() {
    Node l={3,1,nullptr,nullptr}, r={8,1,nullptr,nullptr};
    Node root={5,2,&l,&r};
    cout << "Balance factor: " << balance(&root) << " (must stay in [-1,1])" << endl;
    return 0;
}
public class Main {
    static class Node { int val, height; Node left, right; Node(int v){val=v;height=1;} }
    static int h(Node n) { return n == null ? 0 : n.height; }
    static int balance(Node n) { return n == null ? 0 : h(n.left) - h(n.right); }
    public static void main(String[] args) {
        Node root = new Node(5); root.height = 2;
        root.left = new Node(3); root.right = new Node(8);
        System.out.println("Balance factor: " + balance(root) + " (must stay in [-1,1])");
    }
}
class Node:
    def __init__(self, val):
        self.val = val; self.height = 1; self.left = None; self.right = None

def h(n):
    return n.height if n else 0

def balance(n):
    return h(n.left) - h(n.right) if n else 0

root = Node(5); root.height = 2
root.left = Node(3); root.right = Node(8)
print("Balance factor:", balance(root), "(must stay in [-1,1])")
#include <stdio.h>
#include <stddef.h>
struct Node { int val, height; struct Node *left, *right; };
int h(struct Node* n) { return n ? n->height : 0; }
int balance(struct Node* n) { return n ? h(n->left) - h(n->right) : 0; }
int main() {
    struct Node l={3,1,NULL,NULL}, r={8,1,NULL,NULL};
    struct Node root={5,2,&l,&r};
    printf("Balance factor: %d (must stay in [-1,1])\n", balance(&root));
    return 0;
}

Rotations

जब भी एक insertion या deletion किसी subtree के balance को उस allowed range से बाहर धकेलता है, tree एक rotation perform करता है — कुछ nodes का एक local restructuring — tree के overall sorted order बदले बिना balance property restore करने के लिए।

उदाहरण: Rotations

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
Node* rotateLeft(Node* x) {
    Node* y = x->right;
    x->right = y->left;
    y->left = x;
    return y;
}
int main() {
    Node* c = new Node{30, nullptr, nullptr};
    Node* b = new Node{20, nullptr, c};
    Node* newRoot = rotateLeft(b);
    cout << "After left rotation, new subtree root: " << newRoot->val << endl;
    return 0;
}
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static Node rotateLeft(Node x) {
        Node y = x.right;
        x.right = y.left;
        y.left = x;
        return y;
    }
    public static void main(String[] args) {
        Node b = new Node(20);
        b.right = new Node(30);
        Node newRoot = rotateLeft(b);
        System.out.println("After left rotation, new subtree root: " + newRoot.val);
    }
}
class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

def rotate_left(x):
    y = x.right
    x.right = y.left
    y.left = x
    return y

b = Node(20)
b.right = Node(30)
new_root = rotate_left(b)
print("After left rotation, new subtree root:", new_root.val)
#include <stdio.h>
#include <stdlib.h>
struct Node { int val; struct Node *left, *right; };
struct Node* rotateLeft(struct Node* x) {
    struct Node* y = x->right;
    x->right = y->left;
    y->left = x;
    return y;
}
int main() {
    struct Node* c = malloc(sizeof(struct Node)); c->val=30; c->left=c->right=NULL;
    struct Node* b = malloc(sizeof(struct Node)); b->val=20; b->left=NULL; b->right=c;
    struct Node* newRoot = rotateLeft(b);
    printf("After left rotation, new subtree root: %d\n", newRoot->val);
    return 0;
}

Four Cases

चार rotation cases हैं इस आधार पर कि कौन सी side unbalanced है और offending node कहां बैठता है: left-left, right-right, left-right, और right-left, हर एक imbalance की direction और किसी भी zigzag shape के नाम पर।

उदाहरण: Four Cases

#include <iostream>
using namespace std;
int main() {
    cout << "Left-Left, Right-Right, Left-Right, Right-Left -- named after the path of the two unbalancing insertions" << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        System.out.println("Left-Left, Right-Right, Left-Right, Right-Left -- named after the path of the two unbalancing insertions");
    }
}
print("Left-Left, Right-Right, Left-Right, Right-Left -- named after the path of the two unbalancing insertions")
#include <stdio.h>
int main() {
    printf("Left-Left, Right-Right, Left-Right, Right-Left -- named after the path of the two unbalancing insertions\n");
    return 0;
}

Double Rotations

left-right और right-left cases 'double rotations' हैं — उन्हें balance पूरी तरह restore करने के लिए sequence में दो अलग single rotations चाहिए, जबकि left-left और right-right cases को सिर्फ एक-एक rotation चाहिए।

उदाहरण: Double Rotations

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
Node* rotateRight(Node* y) { Node* x = y->left; y->left = x->right; x->right = y; return x; }
Node* rotateLeft(Node* x) { Node* y = x->right; x->right = y->left; y->left = x; return y; }
int main() {
    Node* c = new Node{25, nullptr, nullptr};
    Node* b = new Node{10, nullptr, c};
    Node* a = new Node{30, b, nullptr};
    a->left = rotateLeft(b);
    Node* newRoot = rotateRight(a);
    cout << "Left-Right case: rotate left on child, then right on root -> " << newRoot->val << endl;
    return 0;
}
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static Node rotateRight(Node y) { Node x = y.left; y.left = x.right; x.right = y; return x; }
    static Node rotateLeft(Node x) { Node y = x.right; x.right = y.left; y.left = x; return y; }
    public static void main(String[] args) {
        Node a = new Node(30);
        a.left = new Node(10);
        a.left.right = new Node(25);
        a.left = rotateLeft(a.left);
        Node newRoot = rotateRight(a);
        System.out.println("Left-Right case: rotate left on child, then right on root -> " + newRoot.val);
    }
}
class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

def rotate_right(y):
    x = y.left; y.left = x.right; x.right = y
    return x

def rotate_left(x):
    y = x.right; x.right = y.left; y.left = x
    return y

a = Node(30)
a.left = Node(10)
a.left.right = Node(25)
a.left = rotate_left(a.left)
new_root = rotate_right(a)
print("Left-Right case: rotate left on child, then right on root ->", new_root.val)
#include <stdio.h>
#include <stdlib.h>
struct Node { int val; struct Node *left, *right; };
struct Node* rotateRight(struct Node* y) { struct Node* x = y->left; y->left = x->right; x->right = y; return x; }
struct Node* rotateLeft(struct Node* x) { struct Node* y = x->right; x->right = y->left; y->left = x; return y; }
int main() {
    struct Node* c = malloc(sizeof(struct Node)); c->val=25; c->left=c->right=NULL;
    struct Node* b = malloc(sizeof(struct Node)); b->val=10; b->left=NULL; b->right=c;
    struct Node* a = malloc(sizeof(struct Node)); a->val=30; a->left=b; a->right=NULL;
    a->left = rotateLeft(b);
    struct Node* newRoot = rotateRight(a);
    printf("Left-Right case: rotate left on child, then right on root -> %d\n", newRoot->val);
    return 0;
}

AVL Practice

Values किसी भी order में insert या delete हों tree height को O(log n) पर रखकर, AVL trees गारंटी देते हैं कि search, insertion, और deletion सभी worst case में O(log n) रहें — cost हर update पर extra bookkeeping और कभी-कभी rotations है।

उदाहरण: AVL Practice

#include <iostream>
using namespace std;
int main() {
    cout << "AVL guarantees O(log n) height, so search/insert/delete all run in O(log n)" << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        System.out.println("AVL guarantees O(log n) height, so search/insert/delete all run in O(log n)");
    }
}
print("AVL guarantees O(log n) height, so search/insert/delete all run in O(log n)")
#include <stdio.h>
int main() {
    printf("AVL guarantees O(log n) height, so search/insert/delete all run in O(log n)\n");
    return 0;
}
Related Topics

Tree की Height और Diameter · Binary Search Tree क्या है · Tree Views यानि Left, Right, Top, Bottom · Tree Traversals यानि Inorder, Preorder, Postorder

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. एक rotation के बाद node heights update न करना, इसलिए बाद के balance factors गलत हैं।
  2. left-right या right-left case के लिए एक single rotation apply करना, जब दो rotations चाहिए।
  3. Balance factor को एक जगह right - left और दूसरी जगह left - right compute करना।
🔒

Chapter Quiz — Complete all 10 topics to unlock

0/10 topics done

Complete these topics first:

← Previous Lesson BST Insert Delete Search Next Lesson → Height and Diameter of Tree

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.