PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम AVL Tree: Self-Balancing BST, Balance Factor (-1, 0, +1) (AVL ट्री: स्व-संतुलित BST और बैलेंस फैक्टर (-1, 0, 1)) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।
Overview: An AVL Tree (Adelson-Velsky & Landis, 1962) is the first self-balancing Binary Search Tree, maintaining a Balance Factor (height(left) - height(right)) within {-1, 0, +1} at every node. This strict height invariant bounds tree height below 1.44 * log2(n + 2), guaranteeing worst-case O(log n) search, insertion, and deletion.
अध्याय सार: AVL ट्री (Adelson-Velsky और Landis, 1962) कंप्यूटर विज्ञान का पहला स्व-संतुलित (Self-Balancing) BST है, जहाँ प्रत्येक नोड का बैलेंस फैक्टर {-1, 0, +1} के बीच रहता है। यह सख्त नियम ट्री की ऊंचाई को 1.44 * log2(n + 2) से कम रखकर सर्च, इन्सर्ट और डिलीट को वर्स्ट-केस O(log n) में सुनिश्चित करता है।
AVL Tree: Self-Balancing BST, Balance Factor (-1, 0, +1): Detailed Notes & Architecture (AVL ट्री: स्व-संतुलित BST और बैलेंस फैक्टर (-1, 0, 1))
1. Balance Factor Definition & AVL Invariant (बैलेंस फैक्टर (BF) और AVL नियम)
[EN] For any node N in an AVL tree, the Balance Factor is defined as BF(N) = height(N.left) - height(N.right). A node is balanced if and only if BF(N) belongs to {-1, 0, +1}, meaning its left and right subtree heights differ by at most 1. Using edge-count height (empty NULL child = -1, single leaf = 0) or node-count height (NULL = 0, leaf = 1) produces identical Balance Factors because the offset cancels out in subtraction.
[HI] AVL ट्री में किसी नोड N का बैलेंस फैक्टर BF(N) = height(N.left) - height(N.right) होता है। ट्री तभी AVL संतुलित कहलाता है जब प्रत्येक नोड का BF केवल -1, 0 या +1 हो अर्थात बाएँ और दाएँ सब-ट्री की ऊंचाई में अधिकतम 1 का अंतर हो। NULL की ऊंचाई 0 या -1 मानने पर भी घटाव के कारण BF मान समान रहता है।
2. Fibonacci Recurrence & Worst-Case Height Proof (1.44 log2 n) (फाइबोनैचि संबंध और अधिकतम ऊंचाई सीमा)
[EN] The sparsest valid AVL tree of height h (minimum nodes N(h)) satisfies the Fibonacci recurrence N(h) = 1 + N(h-1) + N(h-2). With edge-based height (N(0)=1 for 1 node, N(1)=2, N(2)=4, N(3)=7, N(4)=12), N(h) = F_{h+3} - 1, where F_k is the k-th Fibonacci number growing as phi^k / sqrt(5) with golden ratio phi = 1.618. Solving for h yields h < 1.44 * log2(n + 2) - 0.328, proving logarithmic worst-case height.
[HI] ऊंचाई h वाले AVL ट्री में न्यूनतम नोड्स N(h) फाइबोनैचि समीकरण N(h) = 1 + N(h-1) + N(h-2) से तय होते हैं (एज-आधारित ऊंचाई पर N(0)=1, N(1)=2, N(2)=4, N(3)=7, N(4)=12)। स्वर्ण अनुपात (Golden Ratio phi ≈ 1.618) से हल करने पर अधिकतम ऊंचाई 1.44 * log2(n + 2) से कम सिद्ध होती है।
3. Time Complexity & Rotation Count Bounds (समय जटिलता और रोटेशन की संख्या)
[EN] Because height is strictly O(log n), searching an AVL tree takes O(log n) worst-case time without any skew degradation. Inserting a key walks down O(log n) levels and rebalances via at most ONE single rotation or ONE double rotation (O(1) structural pointer changes) at the lowest unbalanced ancestor. Deletion takes O(log n) time too, but reducing a subtree's height can propagate imbalances upward, requiring up to O(log n) rotations in the worst case.
[HI] सदैव O(log n) ऊंचाई रहने से सर्च, इन्सर्ट और डिलीट सभी वर्स्ट-केस में O(log n) समय लेते हैं। इन्सर्शन के बाद केवल एक सिंगल या एक डबल रोटेशन से ट्री संतुलित हो जाता है, जबकि डिलीशन में ऊंचाई घटने के कारण रूट तक अधिकतम O(log n) रोटेशन लग सकते हैं।
4. AVL Tree vs Red-Black Tree Trade-offs (AVL ट्री बनाम Red-Black ट्री तुलना)
[EN] Compared to Red-Black trees (whose worst-case height can reach 2 * log2(n + 1)), AVL trees are more rigidly balanced (1.44 * log2 n) and therefore deliver faster lookup/search queries. However, Red-Black trees need fewer rotations during updates (at most 2 for insert and 3 for delete) and require only 1 bit per node for color instead of an integer height/BF field. Thus AVL suits read-heavy workloads while Red-Black trees power std::map, Java TreeMap, and Linux kernel schedulers.
[HI] Red-Black ट्री (ऊंचाई <= 2 log2 n) की तुलना में AVL ट्री अधिक सख्ती से संतुलित (1.44 log2 n) होता है, इसलिए इसमें सर्च तेज होता है। इसके विपरीत, बार-बार इन्सर्ट/डिलीट वाले कार्यों में कम रोटेशन के कारण Red-Black ट्री (जैसे C++ std::map, Java TreeMap) पसंद किए जाते हैं।
Syntax, Formula & Technical Example (AVL Tree: Self-Balancing BST, Balance Factor (-1, 0, +1))
class AVLNode:
def __init__(self, key):
self.key = key
self.left = self.right = None
self.height = 0 # Empty child = -1, Leaf = 0
def balance_factor(node):
lh = node.left.height if node.left else -1
rh = node.right.height if node.right else -1
return lh - rh # Valid AVL requires -1 <= BF <= +1
AVL Tree: Self-Balancing BST, Balance Factor (-1, 0, +1) Quick Reference & Comparison Table
| AVL Property / Metric | Exact Definition / Bound | Exam Fact |
|---|---|---|
| Balance Factor (BF) | height(left) - height(right) in {-1, 0, +1} | |BF| >= 2 signals imbalance needing rotation |
| Maximum Height Bound | h < 1.44 * log2(n + 2) - 0.328 | Tighter than Red-Black Tree's 2 * log2(n + 1) |
| Minimum Nodes N(h) | 1 + N(h - 1) + N(h - 2) (Fibonacci) | Edge heights h=0..4 need min 1, 2, 4, 7, 12 nodes |
| Asymptotic Operations | Search, Insert, Delete all O(log n) worst-case | Insert needs <= 1 rotation; Delete up to O(log n) |
AVL Tree: Self-Balancing BST, Balance Factor (-1, 0, +1) Top 20 Bilingual MCQs with Answers
Q1. Who invented the AVL Tree in 1962, creating the first self-balancing Binary Search Tree?
(1962 में पहला स्व-संतुलित BST (AVL ट्री) किन वैज्ञानिकों ने विकसित किया था?)
(A) Georgy Adelson-Velsky and Evgenii Landis
(B) Donald Knuth and Robert Tarjan
(C) Edsger Dijkstra and C.A.R. Hoare
(D) Rudolf Bayer and Edward McCreight
Correct Answer: (A)
[EN] AVL stands for its Soviet inventors Adelson-Velsky and Landis, who published it in 1962.
[HI] AVL नाम इसके आविष्कारक Georgy Adelson-Velsky और Evgenii Landis के नाम के पहले अक्षरों से पड़ा है।
Q2. Which set of Balance Factor values is permissible for every node inside a valid AVL Tree?
(एक मान्य AVL ट्री के प्रत्येक नोड के लिए बैलेंस फैक्टर (BF) के कौन से मान स्वीकार्य हैं?)
(A) {-2, -1, 0, +1, +2}
(B) {-1, +1} only
(C) {0, +1} only
(D) {-1, 0, +1}
Correct Answer: (D)
[EN] A node is height-balanced when height(left) and height(right) differ by at most 1, giving {-1, 0, +1}.
[HI] बाएँ और दाएँ सब-ट्री की ऊंचाई में अंतर अधिकतम 1 होने के कारण मान्य BF मान केवल -1, 0 और +1 होते हैं।
Q3. Using edge-count height (single node height = 0, NULL = -1), what is the MINIMUM number of nodes in an AVL tree of height 3?
(एज-आधारित ऊंचाई (एकल नोड h=0, NULL=-1) के अनुसार ऊंचाई 3 वाले AVL ट्री में न्यूनतम कितने नोड्स हो सकते हैं?)
(A) 7
(B) 4
(C) 8
(D) 12
Correct Answer: (A)
[EN] By N(h) = 1 + N(h-1) + N(h-2): N(0)=1, N(1)=2, N(2)=4, and N(3)=1 + 4 + 2 = 7.
[HI] सूत्र N(h) = 1 + N(h-1) + N(h-2) से N(0)=1, N(1)=2, N(2)=4 और N(3) = 1 + 4 + 2 = 7 नोड्स होंगे।
Q4. Using node-count height (single leaf height = 1, NULL = 0), what is the minimum number of nodes in an AVL tree of height 4?
(नोड-आधारित ऊंचाई (लीफ की ऊंचाई = 1, NULL = 0) के अनुसार ऊंचाई 4 के AVL ट्री में न्यूनतम कितने नोड्स होंगे?)
(A) 4
(B) 15
(C) 7
(D) 12
Correct Answer: (C)
[EN] With node-count height: N(0)=0, N(1)=1, N(2)=2, N(3)=4, and N(4)=1 + 4 + 2 = 7 nodes (equivalent to edge-height 3).
[HI] नोड-गिनती ऊंचाई में N(1)=1, N(2)=2, N(3)=4 तथा N(4) = 1 + 4 + 2 = 7 नोड्स होते हैं।
Q5. What is the tightest asymptotic upper bound on the height h of an AVL tree containing n nodes?
(n नोड्स वाले AVL ट्री की ऊंचाई h की सटीक ऊपरी सीमा (Upper Bound) लगभग क्या होती है?)
(A) 2.00 * log2(n)
(B) sqrt(n)
(C) 0.50 * log2(n)
(D) 1.44 * log2(n)
Correct Answer: (D)
[EN] Derived from 1 / log2(golden ratio phi) = 1 / log2(1.618) = 1.4404, giving h < 1.44 * log2(n + 2).
[HI] गोल्डन रेश्यो (1.618) के लघुगणक से AVL ट्री की अधिकतम ऊंचाई 1.44 * log2(n) से कम सिद्ध होती है।
Q6. If node X has a left subtree of height 3 and a right subtree of height 1 (using same convention), what is BF(X) under height(L)-height(R) and is it AVL-valid?
(यदि नोड X के बाएँ सब-ट्री की ऊंचाई 3 और दाएँ सब-ट्री की ऊंचाई 1 है, तो BF(X) क्या होगा और क्या ट्री संतुलित है?)
(A) BF = +2; Invalid (left-heavy imbalance)
(B) BF = +2; Valid AVL node
(C) BF = -2; Valid AVL node
(D) BF = +1; Invalid
Correct Answer: (A)
[EN] BF(X) = 3 - 1 = +2, which falls outside {-1, 0, +1}, so node X must be rebalanced via rotation.
[HI] BF = 3 - 1 = +2 होने से यह {-1, 0, +1} के बाहर है, इसलिए नोड X असंतुलित है और रोटेशन आवश्यक है।
Q7. How many rotations at most are required to rebalance an AVL tree after a SINGLE key insertion?
(AVL ट्री में एक नई कुंजी डालने (Insertion) के बाद ट्री को पुनः संतुलित करने में अधिकतम कितने रोटेशन लग सकते हैं?)
(A) Up to O(log n) rotations
(B) At most 1 single rotation or 1 double rotation (O(1) rotations)
(C) Exactly n rotations
(D) Zero rotations always
Correct Answer: (B)
[EN] Restoring balance at the lowest unbalanced ancestor after insertion restores that subtree's pre-insert height, stopping propagation immediately.
[HI] इन्सर्शन के बाद सबसे निचले असंतुलित पूर्वज को केवल 1 सिंगल या 1 डबल रोटेशन से ठीक करते ही पूरे ट्री की ऊंचाई सामान्य हो जाती है।
Q8. How many rotations in the worst case can be triggered after deleting a key from an AVL tree of n nodes?
(n नोड्स वाले AVL ट्री से एक कुंजी डिलीट करने पर वर्स्ट केस में अधिकतम कितने रोटेशन करने पड़ सकते हैं?)
(A) O(log n) rotations
(B) Always 0 rotations
(C) Strictly at most 1 single rotation
(D) O(n^2) rotations
Correct Answer: (A)
[EN] Deleting a node may shorten a subtree by 1 even after rotating, propagating height imbalance up along the ancestor path to the root.
[HI] डिलीशन में एक रोटेशन के बाद भी सब-ट्री की ऊंचाई 1 कम हो सकती है, जिससे रूट तक O(log n) रोटेशन करने पड़ सकते हैं।
Q9. Between AVL Trees and Red-Black Trees, which statement accurately describes their performance trade-off?
(AVL ट्री और Red-Black ट्री के प्रदर्शन अंतर के बारे में कौन सा कथन सटीक है?)
(A) Red-Black trees always have smaller height than AVL trees
(B) AVL trees provide faster lookups due to stricter balance, whereas Red-Black trees allow faster frequent insertions/deletions
(C) AVL trees require O(n) worst-case search while Red-Black takes O(log n)
(D) Red-Black trees perform no rotations during deletion
Correct Answer: (B)
[EN] AVL's 1.44 log n max height beats Red-Black's 2 log n max height for reads, while Red-Black caps deletion rotations at 3.
[HI] सख्त संतुलन से AVL में सर्च तेज होती है, जबकि कम रोटेशन के कारण बार-बार बदलाव होने पर Red-Black ट्री बेहतर रहता है।
Q10. What mathematical sequence directly governs the minimum number of nodes N(h) in an AVL tree of height h?
(ऊंचाई h वाले AVL ट्री में न्यूनतम नोड्स N(h) की गणना किस प्रसिद्ध गणितीय श्रेणी से सीधे जुड़ी है?)
(A) Catalan numbers
(B) Prime numbers
(C) Pascal triangular powers of 2
(D) Fibonacci sequence
Correct Answer: (D)
[EN] Because one child has height h-1 and the other has minimum height h-2, N(h) = 1 + N(h-1) + N(h-2) matches Fibonacci sums minus 1.
[HI] न्यूनतम नोड्स के लिए एक शाखा की ऊंचाई h-1 और दूसरी की h-2 लेने पर N(h) = 1 + N(h-1) + N(h-2) फाइबोनैचि श्रेणी बनाता है।
Q11. What is the MAXIMUM number of nodes in an AVL tree of edge-based height 3 (root at level 0, leaves at level 3)?
(एज-आधारित ऊंचाई 3 (रूट लेवल 0, लीव्स लेवल 3) वाले AVL ट्री में अधिकतम कितने नोड्स हो सकते हैं?)
(A) 7
(B) 15
(C) 12
(D) 31
Correct Answer: (B)
[EN] Maximum nodes occur in a full complete binary tree of edge-height h: 2^(h+1) - 1 = 2^4 - 1 = 15 nodes.
[HI] ऊंचाई 3 वाले पूर्ण बाइनरी ट्री में अधिकतम 2^(3+1) - 1 = 15 नोड्स हो सकते हैं।
Q12. What is the Balance Factor of EVERY leaf node in an AVL Tree?
(AVL ट्री के प्रत्येक लीफ नोड (Leaf Node) का बैलेंस फैक्टर सदैव कितना होता है?)
(A) Undefined
(B) 0
(C) -1
(D) +1
Correct Answer: (B)
[EN] Both left and right children of a leaf are NULL (same height), so height(NULL) - height(NULL) = 0.
[HI] लीफ नोड के दोनों चाइल्ड NULL होते हैं, इसलिए उनकी समान ऊंचाई घटने पर BF सदैव 0 प्राप्त होता है।
Q13. Suppose an AVL tree stores 1,000,000 (10^6) keys. Approximately what is the worst-case maximum height h (given log2(10^6) ~ 20)?
(यदि किसी AVL ट्री में 10 लाख (10^6) कुंजियाँ हैं (log2(10^6) ≈ 20), तो ट्री की वर्स्ट-केस अधिकतम ऊंचाई लगभग कितनी होगी?)
(A) Around 1,000 levels
(B) Around 100 levels
(C) Around 29 levels (1.44 * 20)
(D) Strictly 10 levels
Correct Answer: (C)
[EN] 1.44 * 20 = 28.8; even in the worst possible AVL layout, searching 1 million items needs fewer than 30 comparisons.
[HI] 1.44 * 20 = 28.8; अर्थात 10 लाख रिकॉर्ड्स में भी खोजने के लिए अधिकतम 30 से कम तुलनाएँ लगेंगी।
Q14. What extra metadata must each AVL tree node typically store beyond BST key and left/right pointers?
(सामान्य BST नोड (key, left, right) के अतिरिक्त AVL नोड में प्रायः कौन सा अतिरिक्त डेटा संग्रहीत किया जाता है?)
(A) Preorder sequence rank
(B) Node height (or Balance Factor)
(C) Hash signature of subtree
(D) Parent color bit (Red/Black)
Correct Answer: (B)
[EN] Storing the integer height (or 2-bit balance factor) lets insert/delete compute BF(N) in O(1) without recomputing subtree heights.
[HI] प्रत्येक नोड की ऊंचाई (या बैलेंस फैक्टर) संग्रहीत करने से BF की गणना O(1) समय में हो जाती है।
Q15. In an AVL tree, if all nodes have Balance Factor = 0, what shape does the tree necessarily take?
(यदि किसी AVL ट्री के सभी नोड्स का बैलेंस फैक्टर 0 हो, तो उस ट्री का आकार कैसा होगा?)
(A) A B+ Tree
(B) A Perfect Binary Tree (all levels completely filled)
(C) A complete tree with arbitrary missing leaves
(D) A right-skewed chain
Correct Answer: (B)
[EN] BF = 0 everywhere means left and right subtrees of every node have identical heights and structures, yielding a full perfect binary tree with 2^k - 1 nodes.
[HI] हर नोड पर BF = 0 का अर्थ है बायाँ व दायाँ सब-ट्री बराबर ऊंचाई के हैं, अर्थात ट्री पूर्णतः भरा हुआ (Perfect Binary Tree) है।
Q16. Which statement about AVL Trees is NOT true?
(AVL ट्री के संदर्भ में निम्नलिखित में से कौन सा कथन असत्य (NOT true) है?)
(A) Every AVL tree is strictly a valid Binary Search Tree
(B) Insertion of a single key can violate the BST inorder sorted sequence permanently until rebuilt
(C) Searching an AVL tree takes O(log n) in worst case
(D) Deleting a node can trigger multiple rotations up toward the root
Correct Answer: (B)
[EN] AVL trees always preserve the BST ordering invariant at all times—even during rebalancing rotations.
[HI] AVL ट्री सदैव BST के सॉर्टेड इनवेरिएंट का पालन करता है; रोटेशन के दौरान भी इनऑर्डर क्रम नहीं बिगड़ता।
Q17. Within AVL Tree: Self-Balancing BST, Balance Factor (-1, 0, +1), which avl property / metric directly maps to: "height(left) - height(right) in {-1, 0, +1}"?
(AVL Tree: Self-Balancing BST, Balance Factor (-1, 0, +1) में कौन सा AVL Property / Metric सीधे "height(left) - height(right) in {-1, 0, +1}" से संबंधित है?)
(A) Asymptotic Operations
(B) Maximum Height Bound
(C) Balance Factor (BF)
(D) Minimum Nodes N(h)
Correct Answer: (C)
[EN] In AVL Tree: Self-Balancing BST, Balance Factor (-1, 0, +1), 'Balance Factor (BF)' handles 'height(left) - height(right) in {-1, 0, +1}' (|BF| >= 2 signals imbalance needing rotation).
[HI] AVL Tree: Self-Balancing BST, Balance Factor (-1, 0, +1) में 'Balance Factor (BF)' का कार्य/विवरण 'height(left) - height(right) in {-1, 0, +1}' (|BF| >= 2 signals imbalance needing rotation) है।
Q18. Which option accurately describes 'Maximum Height Bound' in AVL Tree: Self-Balancing BST, Balance Factor (-1, 0, +1)?
(AVL Tree: Self-Balancing BST, Balance Factor (-1, 0, +1) के संदर्भ में 'Maximum Height Bound' की सही विशेषता कौन सी है?)
(A) height(left) - height(right) in {-1, 0, +1}
(B) 1 + N(h - 1) + N(h - 2) (Fibonacci)
(C) h < 1.44 * log2(n + 2) - 0.328
(D) Search, Insert, Delete all O(log n) worst-case
Correct Answer: (C)
[EN] 'Maximum Height Bound' provides 'h < 1.44 * log2(n + 2) - 0.328' — key point: Tighter than Red-Black Tree's 2 * log2(n + 1).
[HI] 'Maximum Height Bound' का मुख्य विवरण 'h < 1.44 * log2(n + 2) - 0.328' है (Tighter than Red-Black Tree's 2 * log2(n + 1))।
Q19. In AVL Tree: Self-Balancing BST, Balance Factor (-1, 0, +1), identify the correct parameter for the specification: "1 + N(h - 1) + N(h - 2) (Fibonacci)".
(AVL Tree: Self-Balancing BST, Balance Factor (-1, 0, +1) में "1 + N(h - 1) + N(h - 2) (Fibonacci)" विवरण किस विकल्प के लिए सही है?)
(A) Asymptotic Operations
(B) Maximum Height Bound
(C) Balance Factor (BF)
(D) Minimum Nodes N(h)
Correct Answer: (D)
[EN] 'Minimum Nodes N(h)' corresponds to '1 + N(h - 1) + N(h - 2) (Fibonacci)' (Edge heights h=0..4 need min 1, 2, 4, 7, 12 nodes).
[HI] 'Minimum Nodes N(h)' का संबंध '1 + N(h - 1) + N(h - 2) (Fibonacci)' (Edge heights h=0..4 need min 1, 2, 4, 7, 12 nodes) से है।
Q20. Considering AVL Tree: Self-Balancing BST, Balance Factor (-1, 0, +1), what key behavior defines 'Asymptotic Operations'?
(AVL Tree: Self-Balancing BST, Balance Factor (-1, 0, +1) में 'Asymptotic Operations' की मुख्य भूमिका या मान क्या है?)
(A) height(left) - height(right) in {-1, 0, +1}
(B) 1 + N(h - 1) + N(h - 2) (Fibonacci)
(C) Search, Insert, Delete all O(log n) worst-case
(D) h < 1.44 * log2(n + 2) - 0.328
Correct Answer: (C)
[EN] 'Asymptotic Operations' represents 'Search, Insert, Delete all O(log n) worst-case' (Insert needs <= 1 rotation; Delete up to O(log n)).
[HI] 'Asymptotic Operations' का अर्थ/मान 'Search, Insert, Delete all O(log n) worst-case' है (Insert needs <= 1 rotation; Delete up to O(log n))।
AVL Tree: Self-Balancing BST, Balance Factor (-1, 0, +1) — Exam FAQs
Q1: Why is Balance Factor defined as height(left) - height(right) in most textbooks, while some use right - left?
अधिकांश किताबों में BF = height(left) - height(right) क्यों लिखते हैं, जबकि कुछ right - left उपयोग करती हैं?
[EN] Both conventions check |BF| <= 1 identically! You just must stay consistent: under left - right, +2 means left-heavy (LL/LR); under right - left, +2 means right-heavy (RR/RL).
[HI] दोनों विधियों में संतुलन की शर्त |BF| <= 1 समान रहती है। बस संकेतन में एकरूपता जरूरी है: left - right में +2 का अर्थ बायाँ भारी (LL/LR) होता है।
Q2: If an AVL tree already checks |BF| <= 1 at the root, do we still need to check children?
यदि रूट नोड का बैलेंस फैक्टर {-1, 0, +1} में है, तो क्या पूरा ट्री AVL माना जाएगा?
[EN] No! Every single node in the tree must satisfy |BF| <= 1. A root could have left height 3 and right height 3 (BF = 0), while its left subtree itself is skewed and unbalanced.
[HI] नहीं! रूट का BF 0 होने के बावजूद उसके अंदर कोई सब-ट्री असंतुलित हो सकता है। इसलिए ट्री के हर नोड पर |BF| <= 1 होना अनिवार्य है।
Q3: Why do database engines prefer B+ Trees over AVL Trees on disk?
डेटाबेस डिस्क स्टोरेज के लिए AVL ट्री की जगह B+ ट्री को प्राथमिकता क्यों देते हैं?
[EN] AVL trees are binary (only 2 children per node), causing ~30 random disk seeks for 10^6 keys, whereas high-fanout B+ Trees pack hundreds of keys per page and finish in 3-4 disk reads.
[HI] AVL केवल बाइनरी ट्री (2 चाइल्ड) है जिससे 10 लाख कुंजियों पर ~30 डिस्क सीक लगेंगे, जबकि B+ ट्री प्रति पेज सैकड़ों कुंजियाँ रखकर 3-4 डिस्क रीड में कार्य कर लेता है।
Post a Comment
Post a Comment