एवीएल पेड़ संतुलन

Question

मैंने एक एवीएल पेड़ लागू किया है, लेकिन मुझे एक समस्या है।

मान लीजिए मैं निम्नलिखित है पेड़:

और एक और नोड जोड़ने के बाद:

अब मैं छोड़ दिया करने के लिए node5 बारी बारी से करना होगा:

लेकिन घूर्णन के बाद, यह अभी भी असंतुलित है।

मैं कहां गलती कर रहा हूं?

Answer 1

प्रस्तुत परिदृश्य this वर्णन से राइट-लेफ्ट मामले के अनुरूप है।

आपकी गलती यह है कि आप असंतुलित नोड (5) को एक बार में घुमाएं, बिना अपने उप-पेड़ के घूर्णन के पहले।

balance(N) = Depth(Nleft) - Depth(Nright) 

if (balance(P) > 1) // P is node 5 in this scenario 
{ 
    if (balance(L) < 0) 
    { 
     rotate_left(L); 
    } 

    rotate_right(P); 
} 
else if (balance(P) < -1) // P is node 5 in this scenario 
{ 
    if (balance(R) > 0) // R is node 11 in this scenario 
    { 
     rotate_right(R); // This case conforms to this scenario 
    } 

    rotate_left(P);  // ... and of course this, after the above 
} 

तो कभी-कभी दो रोटेशन की जरूरत है:

सामान्य अपनी बाईं उप पेड़ के रूप में P असंतुलित नोड के रूप में, L और उसके सही उप पेड़ के रूप में R होने में निम्नलिखित नियम प्रविष्टि में पालन किया जाना चाहिए, और कभी-कभी केवल एक प्रदर्शन किया जाना है।

यह अच्छी तरह से Wikipedia पर कल्पना है: जब दो रोटेशन की जरूरत है

शीर्ष पंक्ति स्थितियों को दर्शाता है। मध्यम पंक्ति संभावित परिदृश्य प्रस्तुत करती है जब एक रोटेशन पर्याप्त होता है। अतिरिक्त रोटेशन किसी भी शीर्ष-पंक्ति परिदृश्य को मध्य-पंक्ति परिदृश्य में बदल देते हैं।

विशेष रूप से, इस पेड़ के लिए:

7 के बाद जोड़ा जाता है:

5 का संतुलन 2 है। यह छद्म कोड में उपर्युक्त टिप्पणी के साथ चिह्नित विकिपीडिया चित्र में शीर्ष-पंक्ति परिदृश्य (दाईं ओर वाला एक) के साथ चिह्नित परिदृश्य के अनुरूप है।तो 5 से पहले किया जाता है बाएं घुमाया, अपने अधिकार उप पेड़ 11 राइट घुमाया होने की जरूरत है:

और यह हो जाता है:

केवल अब, यह सरल बात है (विकिपीडिया तस्वीर में मध्य-पंक्ति सही परिदृश्य) 5 पर एक बाएं-रोटेशन द्वारा संतुलन बहाल करने के लिए:

और पेड़ फिर से संतुलित हो जाता है:

Answer 2

मुझे AVL पेड़, किसी भी सबसे बाईं ओर पत्ती से प्रत्येक नोड की ऊंचाई अंतर होने के लिए एक द्विआधारी पेड़ के लिए, अधिक व्यापक विश्लेषण करने के लिए कोशिश करते हैं किसी भी दाहिने पत्ते के लिए {-1, 0, 1} के भीतर झूठ बोलना चाहिए। AVL के लिए

प्रविष्टि:

AVL insertion- एल के लिए चार मामलों रहे हैं - एल एल - आर आर - आर आर - एल

अब, मामले (क)। [यदि संतुलन> 1] एलएल (बाएं - बाएं) एक नोड एक्स {-1, 0, 1} बाधा का उल्लंघन करता है और दाएं से अधिक ऊंचाई छोड़ देता है - एल का पहला बायां एक बायां उप बच्चा वाई है जिसके बाएं ऊंचाई दाएं से बड़ा है .. फिर एल एक्शन - वाई घड़ी के बारे में घूमें। अर्थात। एक दाएं रोटेशन।

केस (बी) (एल-आर केस) मान लीजिए कि ज़ेड के लिए कुछ जेड नोड डालना है, इसका पहला मूल्यांकन किया गया है, जिस पत्ते पर, बाएं या दाएं, इसे रखा गया है। ठीक है, अगर अधिक वजन, कम वजन अगर छोड़ दिया। कहें, ज़ेड ', नया नोड, wt (Z')> wt (Z), यानी, ज़ेड 'जेड के दाहिने बच्चे के रूप में डाला गया है, एल-आर के मामले में, संपूर्ण लिंक जेडजेड' घड़ी की दिशा में घुमाया गया है, अब यह एलएल केस है और इसलिए उपरोक्त मामले (ए) का उपयोग कर हल किया गया है। अर्थात। एक बाएं और फिर एक दाएं रोटेशन।

केस (सी) [यदि शेष < -1] (आर - आर मामले) इसी प्रकार, आर-आर केस, समायोजन के लिए बस बाइनरी खोज नियम लागू करें और यह मामला काम करता है। अर्थात। एक बाएं रोटेशन।

केस (डी) (आर - एल केस) इसे पहले आर-आर मामले में परिवर्तित किया गया है और इसलिए उपरोक्त मामले (सी) का उपयोग करके हल किया गया है। अर्थात। एक दाएं और फिर एक बाएं रोटेशन।