कंप्यूटर साइंस में AA ट्री को संतुलित ट्री के एक रूप के रूप में परिभाषित किया गया है जिसे क्रमबद्ध डेटा को कुशलतापूर्वक स्टोर और पुनर्प्राप्त करने के लिए लागू किया जाता है। AA ट्रीज को रेड-ब्लैक ट्री के एक रूपांतर के रूप में माना जाता है, एक प्रकार का बाइनरी सर्च ट्री जो प्रविष्टियों के कुशल जोड़ और विलोपन का समर्थन करता है। रेड-ब्लैक ट्री के विपरीत, AA ट्री पर रेड नोड्स को केवल राइट सबचाइल्ड के रूप में जोड़ा जा सकता है, लेफ्ट सबचाइल्ड नहीं। इस ऑपरेशन का परिणाम 2-3-4 ट्री के बजाय 2-3 ट्री का अनुकरण है, जो रखरखाव ऑपरेशन्स को सरल बनाता है। रेड-ब्लैक ट्री के लिए रखरखाव एल्गोरिदम को ट्री को ठीक से संतुलित करने के लिए सात अलग-अलग आकृतियों को मानने या विचार करने की आवश्यकता होती है -
रेड-ब्लैक ट्री के विपरीत, AA ट्री दूसरी ओर केवल दो आकृतियों को मानने या विचार करने की आवश्यकता होती है क्योंकि केवल राइट लिंक्स रेड हो सकते हैं की सख्त आवश्यकता के कारण -
बैलेंसिंग रोटेशन्स
जहां रेड-ब्लैक ट्रीज को प्रति नोड बैलेंसिंग मेटाडेटा के एक बिट की आवश्यकता होती है (रंग), AA ट्रीज को प्रति नोड O(log(log(N))) बिट्स मेटाडेटा की आवश्यकता होती है, एक इंटीजर "लेवल" के रूप में। नीचे दिए गए इनवेरिएंट्स AA ट्रीज के लिए मान्य हैं -
प्रत्येक लीफ नोड का लेवल एक माना जाता है।
प्रत्येक लेफ्ट चाइल्ड का लेवल उसके पैरेंट से ठीक एक छोटा होता है।
प्रत्येक राइट चाइल्ड का लेवल उसके पैरेंट के बराबर या एक छोटा होता है।
प्रत्येक राइट ग्रैंडचाइल्ड का लेवल उसके ग्रैंडपैरेंट से सख्ती से छोटा होता है।
लेवल एक से अधिक का प्रत्येक नोड के दो चाइल्ड होते हैं।
AA ट्री को री-बैलेंस करना रेड-ब्लैक ट्री को री-बैलेंस करने की तुलना में प्रोसीजरली बहुत आसान या सरल है।
AA ट्री के मामले में बैलेंस बहाल करने के लिए केवल दो विशिष्ट ऑपरेशन्स की आवश्यकता होती है: "स्क्यू" और "स्प्लिट"। स्क्यू को एक राइट रोटेशन के रूप में माना जाता है जो लेफ्ट हॉरिजॉन्टल लिंक से बने सबट्री को राइट हॉरिजॉन्टल लिंक से बने सबट्री से बदल देता है। स्प्लिट के मामले में, यह एक लेफ्ट रोटेशन और लेवल वृद्धि है जो दो या अधिक लगातार राइट हॉरिजॉन्टल लिंक्स से बने सबट्री को दो कम लगातार राइट हॉरिजॉन्टल लिंक्स वाले से बदल देता है। ऑपरेशन्स, "स्क्यू" और "स्प्लिट", नीचे समझाए गए हैं -
function skew is
input: एक AA ट्री जिसे रीबैलेंस करने की आवश्यकता है, एक नोड t द्वारा दर्शाया गया।
output: रीबैलेंस्ड AA ट्री को दूसरे नोड द्वारा दर्शाया गया।
if nil(t) then return nil
else if nil(left(t)) then return t
else if level(left(t)) == level(t) then
हॉरिजॉन्टल लेफ्ट लिंक्स के पॉइंटर्स एक्सचेंज करें।
l = left(t)
left(t) := right(l)
right(l) := t
return l
else return t
end if
end function
function split is
input: एक AA ट्री जिसे रीबैलेंस करने की आवश्यकता है, एक नोड t द्वारा दर्शाया गया।
output: रीबैलेंस्ड AA ट्री को दूसरे नोड द्वारा दर्शाया गया।
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
हमारे पास दो हॉरिजॉन्टल राइट लिंक्स हैं। मध्य नोड को लें, उसे ऊपर उठाएं, और लौटाएं।
r = right(t)
right(t) := left(r)
left(r) := t
level(r) := level(r) + 1
return r
else return t
end if
end function
स्प्लिट -
