सी/सी ++ में एए पेड़?

कंप्यूटर विज्ञान में AA ट्री को संतुलित ट्री के रूप में परिभाषित किया गया है, जो ऑर्डर किए गए डेटा को कुशलतापूर्वक संग्रहीत करने और पुनर्प्राप्त करने के लिए लागू किया गया है। एए पेड़ों को लाल-काले पेड़ की विविधता के रूप में माना जाता है, बाइनरी सर्च ट्री का एक रूप जो प्रविष्टियों के कुशल जोड़ और विलोपन का समर्थन करता है। लाल-काले पेड़ों के विपरीत, एए पेड़ पर लाल नोड्स को केवल दाएं उपचाइल्ड के रूप में जोड़ा जा सकता है, बाएं उपचाइल्ड नहीं। इस ऑपरेशन का परिणाम 2-3-4 पेड़ के बजाय 2-3 पेड़ का अनुकरण है, जो रखरखाव कार्यों को सरल बनाता है। लाल-काले पेड़ के लिए रखरखाव एल्गोरिदम को पेड़ को ठीक से संतुलित करने के लिए सात अलग-अलग आकृतियों को मानने या विचार करने की आवश्यकता होती है -

लाल-काले पेड़ के विपरीत, दूसरी ओर एक एए पेड़ को केवल दो आकृतियों को मानने या विचार करने की आवश्यकता होती है क्योंकि सख्त आवश्यकता है कि केवल सही लिंक लाल हो सकते हैं -

घुमावों को संतुलित करना

जबकि लाल-काले पेड़ों को प्रति नोड (रंग) संतुलित मेटाडेटा की एक बिट की आवश्यकता होती है, एए पेड़ों को पूर्णांक "स्तर" के रूप में प्रति नोड मेटाडेटा के ओ (लॉग (लॉग (एन))) बिट्स की आवश्यकता होती है। नीचे दिए गए इनवेरिएंट AA ट्री के लिए होल्ड करते हैं -

• प्रत्येक पत्ती नोड का स्तर एक माना जाता है।

• प्रत्येक बाएं बच्चे का स्तर उसके माता-पिता के स्तर से ठीक एक छोटा होता है।

• हर सही बच्चे का स्तर उसके माता-पिता के बराबर या उससे छोटा होता है।

• हर सही पोते का स्तर अपने दादा-दादी के स्तर से काफी छोटा होता है।

• एक से अधिक स्तर के प्रत्येक नोड में दो बच्चे होते हैं।

लाल-काले पेड़ को फिर से संतुलित करने की तुलना में AA ट्री को री-बैलेंस करना प्रक्रियात्मक रूप से बहुत आसान या सरल है।

एए पेड़ के मामले में संतुलन बहाल करने के लिए केवल दो अलग-अलग संचालन की आवश्यकता होती है:"स्क्यू" और "स्प्लिट"। तिरछा को एक बाएं क्षैतिज लिंक से युक्त एक उपट्री को बदलने के लिए एक सही रोटेशन के रूप में माना जाता है, जिसमें एक के बजाय एक सही क्षैतिज लिंक होता है। स्प्लिट के मामले में, यह एक उपट्री को बदलने के लिए एक बाएं रोटेशन और स्तर की वृद्धि है जिसमें दो या दो से अधिक लगातार दाएं क्षैतिज लिंक होते हैं जिसमें दो लगातार दाएं क्षैतिज लिंक होते हैं। संचालन, "तिरछा" और "विभाजन", नीचे समझाया गया है -

फ़ंक्शन तिरछा है

   input: An AA tree that needs to be rebalanced is represented by a node, t.
   output: The rebalanced AA tree is represented by another node.
if nil(t) then
return nil
else if nil(left(t)) then
return t
else if level(left(t)) == level(t) then
   Exchange the pointers of horizontal left links.
   l = left(t)
left(t) := right(l)
right(l) := t
return l
else
return t
end if
end function

फ़ंक्शन स्प्लिट है

   input: An AA tree that needs to be rebalanced is represented by a node, t.
   output: The rebalanced AA tree is represented by another node.
if nil(t) then
return nil
else if nil(right(t)) or nil(right(right(t))) then
return t
else if level(t) == level(right(right(t))) then
We have two horizontal right links. The middle node is taken, elevate it, and return it.
      r = right(t)
right(t) := left(r)
left(r) := t
level(r) := level(r) + 1
return r
else
return t
end if
end function

विभाजित करें -