PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम AVL Rotations: Single Rotations (LL, RR) and Double (LR, RL) (AVL रोटेशन्स: LL, RR, LR और RL रोटेशन द्वारा ट्री संतुलन) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।
Overview: AVL rotations restore height balance whenever insertion or deletion pushes a node's Balance Factor to +2 or -2 while strictly preserving BST inorder order. Single rotations resolve LL and RR outer-heavy cases, whereas double rotations (LR and RL) fix inner zigzag imbalances.
अध्याय सार: जब किसी नोड का बैलेंस फैक्टर +2 या -2 हो जाता है, तब AVL रोटेशन्स बिना BST क्रम बिगाड़े ट्री को पुनः संतुलित करते हैं। बाहरी असंतुलन (LL व RR) को सिंगल रोटेशन से तथा भीतरी ज़िगज़ैग असंतुलन (LR व RL) को डबल रोटेशन से ठीक किया जाता है।
AVL Rotations: Single Rotations (LL, RR) and Double (LR, RL): Detailed Notes & Architecture (AVL रोटेशन्स: LL, RR, LR और RL रोटेशन द्वारा ट्री संतुलन)
1. Identifying the Four Imbalance Cases (LL, RR, LR, RL) (चारों असंतुलन स्थितियों (LL, RR, LR, RL) की पहचान)
[EN] After inserting a key, we trace upward from the newly added leaf to find the FIRST (lowest) ancestor node z whose |BF(z)| reaches 2. The imbalance type depends solely on the two steps from z down the taller child toward the insertion: Left-Left (LL: BF(z)=+2, BF(z.left)>=0), Right-Right (RR: BF(z)=-2, BF(z.right)<=0), Left-Right (LR: BF(z)=+2, BF(z.left)=-1), and Right-Left (RL: BF(z)=-2, BF(z.right)=+1).
[HI] नया नोड जोड़ने के बाद ऊपर रूट की ओर बढ़ते हुए सबसे पहले असंतुलित हुए पूर्वज नोड z (|BF|=2) को खोजते हैं। इसके बाद z से भारी सब-ट्री की ओर दो कदम देखकर केस तय होता है: LL (BF(z)=+2, बायाँ चाइल्ड >=0), RR (BF(z)=-2, दायाँ चाइल्ड <=0), LR (BF(z)=+2, बायाँ चाइल्ड -1) और RL (BF(z)=-2, दायाँ चाइल्ड +1)।
2. Single Rotations: LL (Right Rotate) and RR (Left Rotate) (सिंगल रोटेशन: LL (राइट रोटेट) और RR (लेफ्ट रोटेट))
[EN] In an LL imbalance at root z with left child y (e.g., inserting 30, 20, 10), a Single Right Rotation promotes y to replace z, making z the right child of y and moving y's original right subtree T2 to become z's new left subtree. Symmetrically, an RR imbalance (e.g., 10, 20, 30) triggers a Single Left Rotation promoting right child y, placing z as y.left and reattaching T2 as z.right. Both execute in O(1) pointer updates and preserve T1 < y < T2 < z < T3.
[HI] LL असंतुलन (जैसे 30, 20, 10) में नोड z पर Single Right Rotation चलाकर उसके बाएँ चाइल्ड y को ऊपर रूट बनाया जाता है, z उसका दायाँ चाइल्ड बनता है और y का पुराना दायाँ सब-ट्री T2 अब z के बाएँ जुड़ जाता है। ठीक विपरीत RR केस (10, 20, 30) में Single Left Rotation चलता है। दोनों O(1) समय में पूरा होते हैं और इनऑर्डर क्रम सुरक्षित रखते हैं।
3. Double Rotations: LR and RL Zigzag Rebalancing (डबल रोटेशन: LR और RL ज़िगज़ैग संतुलन)
[EN] When a key falls into an inner subtree—such as inserting 30, 10, 20 (LR) or 10, 30, 20 (RL)—a single rotation merely mirrors the imbalance without reducing height. An LR rotation first executes a Left Rotation on z.left (converting the inner kink into an outer LL line), then performs a Right Rotation on z, lifting the grandchild x above both z.left and z. Symmetrically, an RL rotation applies Right Rotation on z.right followed by Left Rotation on z.
[HI] जब असंतुलन अंदरूनी शाखा में हो (जैसे 30, 10, 20 का LR या 10, 30, 20 का RL), तब एक रोटेशन ऊंचाई कम नहीं कर पाता। LR केस में पहले z के बाएँ चाइल्ड पर Left Rotation चलाकर ट्री को LL रूप में लाते हैं और फिर z पर Right Rotation करते हैं। RL केस में पहले z के दाएँ चाइल्ड पर Right और फिर z पर Left Rotation किया जाता है।
4. Deletion Rebalancing & Subtree Height Propagation (डिलीशन में रोटेशन और R0/R1/R-1 केस)
[EN] Deletion uses the exact same four rotation mechanisms, except the taller remaining sibling y of the deleted side can have BF(y) == 0. For a left-heavy deletion imbalance BF(z) = +2: BF(y) == +1 (R1) or BF(y) == 0 (R0) uses a Single Right Rotation, whereas BF(y) == -1 (R-1) requires an LR Double Rotation. Note that in the R0 case, the rotated subtree keeps its pre-deletion height, stopping further upward propagation; in R1 and R-1, subtree height drops by 1 and checks continue toward the root.
[HI] डिलीशन में भी यही चारों रोटेशन काम आते हैं, परंतु यहाँ भारी चाइल्ड y का BF = 0 भी हो सकता है। यदि BF(z)=+2 के साथ BF(y) = +1 या 0 हो तो Single Right Rotation, और BF(y) = -1 होने पर LR Double Rotation लगाया जाता है; R0 स्थिति में ऊंचाई घटती नहीं और आगे रोटेशन रुक जाते हैं।
Syntax, Formula & Technical Example (AVL Rotations: Single Rotations (LL, RR) and Double (LR, RL))
def right_rotate(z):
y = z.left; T2 = y.right
y.right = z; z.left = T2
update_height(z); update_height(y)
return y # LL Fix; LR Fix = right_rotate(z) after z.left = left_rotate(z.left)
def left_rotate(z):
y = z.right; T2 = y.left
y.left = z; z.right = T2
update_height(z); update_height(y)
return y # RR Fix; RL Fix = left_rotate(z) after z.right = right_rotate(z.right)
AVL Rotations: Single Rotations (LL, RR) and Double (LR, RL) Quick Reference & Comparison Table
| Imbalance Case | Balance Factor Signature | Corrective Rotation |
|---|---|---|
| LL (Left-Left) | BF(z) = +2 and BF(z.left) >= 0 | Single Right Rotation at unbalanced node z |
| RR (Right-Right) | BF(z) = -2 and BF(z.right) <= 0 | Single Left Rotation at unbalanced node z |
| LR (Left-Right) | BF(z) = +2 and BF(z.left) = -1 | Left Rotate(z.left), then Right Rotate(z) |
| RL (Right-Left) | BF(z) = -2 and BF(z.right) = +1 | Right Rotate(z.right), then Left Rotate(z) |
AVL Rotations: Single Rotations (LL, RR) and Double (LR, RL) Top 20 Bilingual MCQs with Answers
Q1. Inserting keys 30, 20, 10 sequentially into an initially empty AVL tree produces which imbalance and corrective rotation?
(खाली AVL ट्री में क्रमशः 30, 20, 10 डालने पर कौन सा असंतुलन और सुधारात्मक रोटेशन होगा?)
(A) LL imbalance fixed by Single Right Rotation at 30
(B) RR imbalance fixed by Single Left Rotation at 30
(C) RL imbalance fixed by Right then Left rotation
(D) LR imbalance fixed by Left then Right rotation
Correct Answer: (A)
[EN] 20 goes left of 30 and 10 goes left of 20, creating BF(30)=+2 and BF(20)=+1 (LL), solved by right-rotating 30 so 20 becomes root.
[HI] 20, 30 के बाएँ और 10, 20 के बाएँ जाता है जिससे LL असंतुलन बनता है; 30 पर Single Right Rotation से 20 नया रूट बनता है।
Q2. Inserting keys 10, 30, 20 into an empty AVL tree creates which imbalance at root 10, and what becomes the new root?
(खाली AVL ट्री में 10, 30, 20 क्रम में डालने पर कौन सा असंतुलन बनेगा और नया रूट क्या होगा?)
(A) LL imbalance; new root becomes 10
(B) LR imbalance; new root becomes 20
(C) RL imbalance; new root becomes 20
(D) RR imbalance; new root becomes 30
Correct Answer: (C)
[EN] 30 attaches right of 10 and 20 attaches left of 30 (RL); Right Rotate(30) then Left Rotate(10) promotes 20 to the root.
[HI] 30, 10 के दाएँ और 20, 30 के बाएँ जाता है (RL केस); डबल रोटेशन के बाद मध्य मान 20 नया रूट बन जाता है।
Q3. In a Single Right Rotation on unbalanced node z whose left child is y (with subtree T2 = y.right), where does T2 move?
(नोड z (जिसका बायाँ चाइल्ड y और y का दायाँ सब-ट्री T2 है) पर Single Right Rotation करने पर सब-ट्री T2 कहाँ जाता है?)
(A) Becomes the left child of z (z.left = T2)
(B) Becomes the right child of y
(C) Becomes the right child of z
(D) Is deleted permanently
Correct Answer: (A)
[EN] Since y < T2 < z in BST order, once z becomes y.right, T2 naturally fits as z's left child while preserving BST invariants.
[HI] BST नियम से y < T2 < z होता है; इसलिए z के नीचे जाने पर T2 सुरक्षित रूप से z का नया बायाँ सब-ट्री बन जाता है।
Q4. Which exact sequence of single rotations implements an LR (Left-Right) Double Rotation at unbalanced node z?
(असंतुलित नोड z पर LR डबल रोटेशन करने के लिए दो सिंगल रोटेशन किस सटीक क्रम में चलाए जाते हैं?)
(A) Two consecutive Right Rotations on z
(B) First Left Rotate on z.left, then Right Rotate on z
(C) First Right Rotate on z, then Left Rotate on z.left
(D) First Right Rotate on z.right, then Left Rotate on z
Correct Answer: (B)
[EN] Left-rotating z.left straightens the zigzag into an LL chain, and right-rotating z completes the height reduction.
[HI] पहले z के बाएँ चाइल्ड पर Left Rotation करके कर्व सीधा करते हैं और फिर z पर Right Rotation चलाते हैं।
Q5. How many total rotations (counting a double rotation as 1 double or 2 single) occur when inserting 10, 20, 30, 40, 50 into an empty AVL tree?
(खाली AVL ट्री में क्रमशः 10, 20, 30, 40, 50 डालने पर कुल कितने रोटेशन (RR/LL/LR/RL) होंगे?)
(A) 4 Single Left Rotations
(B) 0 Rotations
(C) 1 Double Rotation only
(D) 2 Single Left Rotations (RR)
Correct Answer: (D)
[EN] Inserting 30 causes RR at 10 (root becomes 20). Inserting 40 keeps balance. Inserting 50 causes RR at 30 (promoting 40), giving 2 RR rotations total.
[HI] 30 डालने पर पहला RR रोटेशन (रूट 20) और 50 डालने पर दूसरा RR रोटेशन (30-40-50 पर) होता है—कुल 2 सिंगल लेफ्ट रोटेशन।
Q6. What is the time complexity of executing a single or double AVL rotation (excluding tree traversal)?
(ट्री में नोड तक पहुँचने के समय को छोड़कर केवल एक सिंगल या डबल AVL रोटेशन करने की समय जटिलता क्या होती है?)
(A) O(n)
(B) O(n log n)
(C) O(log n)
(D) O(1)
Correct Answer: (D)
[EN] Each rotation reassigns a fixed constant number of child pointers and updates heights of 2 or 3 nodes in O(1) time.
[HI] प्रत्येक रोटेशन केवल कुछ निश्चित पॉइंटर और 2-3 नोड्स की ऊंचाई बदलता है, अतः यह O(1) समय लेता है।
Q7. Why must heights be updated in bottom-up order (first z, then new root y) inside right_rotate(z)?
(right_rotate(z) में ऊंचाई अपडेट करते समय पहले पुराने रूट z की और फिर नए रूट y की ऊंचाई क्यों निकाली जाती है?)
(A) Because y becomes a child of z
(B) To convert AVL into a min-heap
(C) Because BST keys change during rotation
(D) Because z becomes a child of y, so y's updated height depends on z's newly computed height
Correct Answer: (D)
[EN] After rotation, z sits lower as y.right; computing y.height before z.height would read stale height values.
[HI] रोटेशन के बाद z, y का चाइल्ड बन जाता है, इसलिए y की सही ऊंचाई जानने से पहले उसके चाइल्ड z की नई ऊंचाई निकालना आवश्यक है।
Q8. Suppose node z has BF = +2 and its left child y has BF = 0 after a DELETION on z's right subtree. Which rotation fixes this?
(किसी नोड z के दाएँ सब-ट्री से डिलीशन के बाद BF(z) = +2 और BF(z.left) = 0 हो तो कौन सा रोटेशन चलाया जाता है?)
(A) Single Left Rotation (RR)
(B) RL Double Rotation
(C) LR Double Rotation
(D) Single Right Rotation (LL / R0 case)
Correct Answer: (D)
[EN] In deletion, BF(z.left) == 0 is resolved cleanly by a single Right Rotation (R0), leaving the subtree height unchanged.
[HI] डिलीशन में यदि भारी चाइल्ड का BF 0 हो तो केवल एक Single Right Rotation (R0) ट्री को संतुलित कर देता है।
Q9. Inserting keys [50, 20, 60, 10, 30, 25] into an empty AVL tree triggers which rotation upon inserting 25?
(खाली AVL ट्री में [50, 20, 60, 10, 30, 25] डालने पर अंतिम कुंजी 25 डालते समय किस नोड पर कौन सा रोटेशन होगा?)
(A) No rotation needed
(B) RL Double Rotation at 20
(C) Single Right Rotation at 50
(D) LR Double Rotation at root 50
Correct Answer: (D)
[EN] Before 25, 50 has left height 1 (20 with 10,30) and right height 0 (60), BF(50)=+1. Adding 25 under 30.left makes 20 right-heavy (BF=-1) and BF(50)=+2, triggering LR at 50.
[HI] 25 (30 के बाएँ) डालने पर नोड 20 का BF=-1 और रूट 50 का BF=+2 हो जाता है, जिससे रूट 50 पर LR डबल रोटेशन चलता है।
Q10. After an LR Double Rotation promotes grandchild x over left child y and unbalanced root z, what are the relative positions of y, x, and z?
(LR डबल रोटेशन के बाद दादा z, बाएँ चाइल्ड y और पोते x की नई स्थिति क्या होती है?)
(A) y becomes new root, x becomes y.right
(B) x becomes leaf under z
(C) z remains root, x becomes z.left
(D) x becomes new root, y becomes x.left, and z becomes x.right
Correct Answer: (D)
[EN] By BST ordering y < x < z, lifting middle key x leaves y on its left and z on its right.
[HI] BST क्रम y < x < z के अनुसार मध्य कुंजी x रूट बनती है, y उसके बाएँ और z उसके दाएँ जुड़ता है।
Q11. When climbing up after an insertion, why do we rotate ONLY at the FIRST (lowest) node with |BF| = 2 rather than at the root first?
(इन्सर्शन के बाद ऊपर जाते समय हम सीधे रूट पर रोटेशन करने के बजाय सबसे पहले मिले असंतुलित नोड (|BF|=2) पर ही रोटेशन क्यों करते हैं?)
(A) Double rotations fail at internal nodes
(B) Fixing the lowest unbalanced ancestor restores its pre-insert height, automatically fixing all higher ancestors
(C) Root rotations destroy leaf nodes
(D) Higher ancestors cannot have |BF| >= 2
Correct Answer: (B)
[EN] Rotating the deepest node with |BF| = 2 brings its subtree height back down by 1, resetting every ancestor's balance factor back to valid values.
[HI] सबसे निचले |BF|=2 नोड को रोटेट करने से उसकी ऊंचाई वापस पहले जितनी हो जाती है, जिससे ऊपर के सभी पूर्वज स्वतः संतुलित हो जाते हैं।
Q12. How many node links/child pointers actually change during one Single Rotation (excluding parent pointers)?
(एक सिंगल रोटेशन में (पैरेंट पॉइंटर के बिना) ट्री के कुल कितने चाइल्ड पॉइंटर्स में बदलाव होता है?)
(A) All n pointers in subtree
(B) log2(n) pointers
(C) 3 pointers (parent->y, y.right/left, and z.left/right)
(D) 1 pointer only
Correct Answer: (C)
[EN] Specifically: the link from z's parent to y, z's child pointer receiving T2, and y's child pointer receiving z.
[HI] मुख्यतः 3 लिंक बदलते हैं: z के पैरेंट का नया लिंक y से, z का T2 से, और y का z से।
Q13. If an unbalanced AVL node z has BF = -2 and z.right has BF = +1, what type of imbalance is present?
(यदि किसी असंतुलित नोड z का BF = -2 और उसके दाएँ चाइल्ड z.right का BF = +1 हो, तो यह किस प्रकार का असंतुलन है?)
(A) RR (Right-Right) imbalance
(B) LL (Left-Left) imbalance
(C) RL (Right-Left) imbalance
(D) LR (Left-Right) imbalance
Correct Answer: (C)
[EN] BF(z) = -2 indicates right-heavy; BF(z.right) = +1 indicates its tall branch goes left, forming Right-Left (RL).
[HI] z दाईं ओर भारी (-2) और उसका दायाँ चाइल्ड बाईं ओर भारी (+1) होने से यह RL असंतुलन है।
Q14. In the AVL tree obtained after inserting 15, 10, 20, 5, 12, 11, which node is the root of the final balanced tree?
(15, 10, 20, 5, 12, 11 को क्रमशः डालने और रोटेशन के बाद अंतिम संतुलित AVL ट्री का रूट कौन होगा?)
(A) 12
(B) 10
(C) 15
(D) 11
Correct Answer: (A)
[EN] 11 attaches left of 12 (BF(10)=-1, BF(15)=+2 -> LR at 15). LR lifts 12 to become the new root with 10 on left and 15 on right.
[HI] 11 को 12 के बाएँ जोड़ने पर रूट 15 पर LR असंतुलन होता है, जिससे 12 ऊपर आकर नया रूट बनता है।
Q15. What fundamental invariant MUST every AVL rotation guarantee before and after execution?
(प्रत्येक AVL रोटेशन से पहले और बाद कौन सा मूलभूत नियम सदैव अपरिवर्तित रहना अनिवार्य है?)
(A) Inorder traversal sequence (BST sorted order) must remain 100% identical
(B) Root key must never change
(C) Preorder traversal must remain identical
(D) Number of leaves must double
Correct Answer: (A)
[EN] Rotations restructure heights locally without ever altering the left-to-right BST sorted key sequence.
[HI] रोटेशन केवल ऊंचाई कम करने के लिए नोड्स की स्थिति बदलता है, लेकिन BST का इनऑर्डर (सॉर्टेड क्रम) बिल्कुल समान रहना चाहिए।
Q16. Which statement about AVL Rotations is FALSE?
(AVL रोटेशन्स के संबंध में निम्नलिखित में से कौन सा कथन असत्य (FALSE) है?)
(A) An LR rotation can always be replaced by a single Right Rotation on the root without losing balance
(B) RL rotation consists of a Right Rotation on the right child followed by a Left Rotation on the unbalanced node
(C) RR imbalance is corrected using a single Left Rotation
(D) Single rotations take O(1) time regardless of subtree size
Correct Answer: (A)
[EN] Applying only a single Right Rotation to an LR zigzag flips the tall inner branch T2 to become equally tall on the opposite side, keeping |BF| = 2.
[HI] LR असंतुलन में केवल एक सिंगल राइट रोटेशन करने पर अंदरूनी लंबा सब-ट्री दूसरी तरफ उतना ही लंबा रह जाता है, जिससे ट्री संतुलित नहीं होता।
Q17. Within AVL Rotations: Single Rotations (LL, RR) and Double (LR, RL), which imbalance case directly maps to: "BF(z) = +2 and BF(z.left) >= 0"?
(AVL Rotations: Single Rotations (LL, RR) and Double (LR, RL) में कौन सा Imbalance Case सीधे "BF(z) = +2 and BF(z.left) >= 0" से संबंधित है?)
(A) RR (Right-Right)
(B) LL (Left-Left)
(C) LR (Left-Right)
(D) RL (Right-Left)
Correct Answer: (B)
[EN] In AVL Rotations: Single Rotations (LL, RR) and Double (LR, RL), 'LL (Left-Left)' handles 'BF(z) = +2 and BF(z.left) >= 0' (Single Right Rotation at unbalanced node z).
[HI] AVL Rotations: Single Rotations (LL, RR) and Double (LR, RL) में 'LL (Left-Left)' का कार्य/विवरण 'BF(z) = +2 and BF(z.left) >= 0' (Single Right Rotation at unbalanced node z) है।
Q18. Which option accurately describes 'RR (Right-Right)' in AVL Rotations: Single Rotations (LL, RR) and Double (LR, RL)?
(AVL Rotations: Single Rotations (LL, RR) and Double (LR, RL) के संदर्भ में 'RR (Right-Right)' की सही विशेषता कौन सी है?)
(A) BF(z) = -2 and BF(z.right) <= 0
(B) BF(z) = -2 and BF(z.right) = +1
(C) BF(z) = +2 and BF(z.left) = -1
(D) BF(z) = +2 and BF(z.left) >= 0
Correct Answer: (A)
[EN] 'RR (Right-Right)' provides 'BF(z) = -2 and BF(z.right) <= 0' — key point: Single Left Rotation at unbalanced node z.
[HI] 'RR (Right-Right)' का मुख्य विवरण 'BF(z) = -2 and BF(z.right) <= 0' है (Single Left Rotation at unbalanced node z)।
Q19. In AVL Rotations: Single Rotations (LL, RR) and Double (LR, RL), identify the correct parameter for the specification: "BF(z) = +2 and BF(z.left) = -1".
(AVL Rotations: Single Rotations (LL, RR) and Double (LR, RL) में "BF(z) = +2 and BF(z.left) = -1" विवरण किस विकल्प के लिए सही है?)
(A) LR (Left-Right)
(B) LL (Left-Left)
(C) RL (Right-Left)
(D) RR (Right-Right)
Correct Answer: (A)
[EN] 'LR (Left-Right)' corresponds to 'BF(z) = +2 and BF(z.left) = -1' (Left Rotate(z.left), then Right Rotate(z)).
[HI] 'LR (Left-Right)' का संबंध 'BF(z) = +2 and BF(z.left) = -1' (Left Rotate(z.left), then Right Rotate(z)) से है।
Q20. Considering AVL Rotations: Single Rotations (LL, RR) and Double (LR, RL), what key behavior defines 'RL (Right-Left)'?
(AVL Rotations: Single Rotations (LL, RR) and Double (LR, RL) में 'RL (Right-Left)' की मुख्य भूमिका या मान क्या है?)
(A) BF(z) = +2 and BF(z.left) = -1
(B) BF(z) = -2 and BF(z.right) <= 0
(C) BF(z) = +2 and BF(z.left) >= 0
(D) BF(z) = -2 and BF(z.right) = +1
Correct Answer: (D)
[EN] 'RL (Right-Left)' represents 'BF(z) = -2 and BF(z.right) = +1' (Right Rotate(z.right), then Left Rotate(z)).
[HI] 'RL (Right-Left)' का अर्थ/मान 'BF(z) = -2 and BF(z.right) = +1' है (Right Rotate(z.right), then Left Rotate(z))।
AVL Rotations: Single Rotations (LL, RR) and Double (LR, RL) — Exam FAQs
Q1: How can students quickly remember which rotation direction fixes LL vs RR?
LL और RR में रोटेशन की दिशा (Left या Right) याद रखने की आसान ट्रिक क्या है?
[EN] Rotate in the OPPOSITE direction of the heavy side! LL hangs to the Left, so rotate Right; RR hangs to the Right, so rotate Left.
[HI] हमेशा भारी दिशा के विपरीत घुमाएं! LL में झुकाव बाईं (Left) ओर है, तो Right Rotate करें; RR में दाईं (Right) ओर है, तो Left Rotate करें।
Q2: Why does LR double rotation move the grandchild up instead of the child?
LR डबल रोटेशन में चाइल्ड के बजाय पोता (Grandchild) ऊपर रूट क्यों बनता है?
[EN] Because in BST order for LR (y < x < z), grandchild x is the median value between y and z, so only x can cleanly sit at the top with y left and z right.
[HI] क्योंकि LR में मानों का क्रम y < x < z होता है; अतः मध्य मान x के ऊपर आने पर ही y बाएँ और z दाएँ BST नियम से फिट बैठते हैं।
Q3: Do rotations preserve Preorder or Postorder traversals?
क्या AVL रोटेशन के बाद Preorder या Postorder ट्रैवर्सल भी समान रहते हैं?
[EN] No—rotating promotes a child to parent, changing Preorder and Postorder sequences; ONLY Inorder traversal remains strictly unchanged.
[HI] नहीं, रोटेशन से पैरेंट-चाइल्ड संबंध बदलने के कारण Preorder और Postorder बदल जाते हैं; केवल Inorder ट्रैवर्सल सदैव समान रहता है।
Post a Comment
Post a Comment