संतुलित BST (AVL आणि लाल-काळे वृक्ष) काय आहेत आणि ते महत्वाचे का आहेत?

Question

Accepted Answer

एक साधा BST कळीजच्या क्रमबद्ध क्रमाने येऊ शकतो तर एक लिंक केलेली यादी (O(n) ऑपरेशन) मध्ये खराब होऊ शकते. **स्व-संतुलन BST** — जसे की **AVL** आणि **लाल-काळे वृक्ष** — सन्निहित होयीयाद्या/हटवणीच्या नंतर नोड्सला आपोआप **फिरवतात** उंची ~`log n` राखण्यासाठी, **O(log n)** ऑपरेशन्स हमी देतात.

## संतुलन समस्या

```text
Unbalanced (insert 1,2,3,4):   Balanced after rotations:
  1                                  2
   \                                / \
    2                              1   3
     \                                  \
      3                                  4
   height ~ n (BAD)            height ~ log n (GOOD)
```

## AVL विरुद्ध लाल-काळे वृक्ष

| | AVL वृक्ष | लाल-काळे वृक्ष |
|---|---|---|
| संतुलन कडकपणा | कडक (उंचीने संतुलित) | हलक्या |
| शोध | वेगवान (लहान) | थोडेसे मंद |
| समाविष्ट/हटवणी | अधिक फिरवणे | कमी फिरवणे |
| सर्वोत्तम | वाचन-गहन कार्यभार | लेखन-गहन कार्यभार |

## गारंटीकृत जटिलता

| ऑपरेशन | वेळ |
|---|---|
| शोध | O(log n) |
| समाविष्ट | O(log n) |
| हटवणी | O(log n) |

दोन्ही **फिरवणीद्वारे** संतुलन राखतात — स्थानिक O(1) पुनर्संरचना जो BST क्रम संरक्षित करते उंची कमी करताना.

## हे महत्वाचे का आहे

संतुलित वृक्ष मानक लायब्ररीमध्ये क्रमबद्ध मानचित्र आणि संच समर्थित करतात (उदा. Java `TreeMap`, C++ `std::map` लाल-काळे वृक्ष वापरतात), क्रमबद्ध पुनरावृत्ती आणि हमीबद्ध लॉगरिदमिक ऑपरेशन देतात.

हे उत्तर आहे जेव्हा तुम्हाला BST च्या क्रमबद्धता *आणि* प्रतिकूल इनपुटविरुद्ध कठोर कार्यक्षमता गारंटी हवी असेल.

	AVL वृक्ष	लाल-काळे वृक्ष
संतुलन कडकपणा	कडक (उंचीने संतुलित)	हलक्या
शोध	वेगवान (लहान)	थोडेसे मंद
समाविष्ट/हटवणी	अधिक फिरवणे	कमी फिरवणे
सर्वोत्तम	वाचन-गहन कार्यभार	लेखन-गहन कार्यभार

ऑपरेशन	वेळ
शोध	O(log n)
समाविष्ट	O(log n)
हटवणी	O(log n)