কম্পিউটার সায়েন্সে AA ট্রি হল একটি ব্যালেন্সড ট্রির ফর্ম যা অর্ডার্ড ডেটা দক্ষতার সাথে স্টোর ও রিট্রিভ করার জন্য ইমপ্লিমেন্টেড। AA ট্রি রেড-ব্ল্যাক ট্রির একটি ভেরিয়েশন, একটি বাইনারি সার্চ ট্রির ফর্ম যা এন্ট্রি যোগ ও ডিলিশন দক্ষতার সাথে সাপোর্ট করে। রেড-ব্ল্যাক ট্রির বিপরীতে, AA ট্রিতে রেড নোডগুলো শুধু রাইট সাবচাইল্ড হিসেবে অ্যাড করা যায়, লেফট সাবচাইল্ড নয়। এই অপারেশনের ফলাফল হল ২-৩-৪ ট্রির বদলে ২-৩ ট্রির সিমুলেশন, যা মেইনটেনেন্স অপারেশনগুলোকে সিম্পলিফাই করে। রেড-ব্ল্যাক ট্রির মেইনটেনেন্স অ্যালগরিদম ট্রি সঠিকভাবে ব্যালেন্স করার জন্য সাতটি ভিন্ন শেপ ধরে বা বিবেচনা করে −
রেড-ব্ল্যাক ট্রির বিপরীতে, AA ট্রি অন্যদিকে শুধু দুটি শেপ ধরে বা বিবেচনা করে কבות কঠোর প্রয়োজনীয়তায় যে শুধু রাইট লিংকগুলো রেড হতে পারে −
ব্যালেন্সিং রোটেশন
যেখানে রেড-ব্ল্যাক ট্রি প্রতি নোডে এক বিট ব্যালেন্সিং মেটাডেটা প্রয়োজন (কালার), AA ট্রি O(log(log(N))) বিট মেটাডেটা প্রতি নোডে প্রয়োজন, একটি ইন্টিজার "লেভেল" রূপে। নিচের ইনভেরিয়েন্টগুলো AA ট্রিতে হোল্ড করে −
প্রতি লিফ নোডের লেভেল এক হিসেবে বিবেচিত হয়।
প্রতি লেফট চাইল্ডের লেভেল এর প্যারেন্টের চেয়ে এক ছোট।
প্রতি রাইট চাইল্ডের লেভেল এর প্যারেন্টের সমান বা এক ছোট।
প্রতি রাইট গ্র্যান্ডচাইল্ডের লেভেল এর গ্র্যান্ডপ্যারেন্টের চেয়ে স্ট্রিক্টলি ছোট।
লেভেল একodeon বেশি যেকোনো নোডের দুটি চাইল্ড থাকে।
এক AA ট্রি রি-ব্যালেন্স করা প্রসিডিউরালি অনেক সহজ বা সিম্পল রেড-ব্ল্যাক ট্রি রি-ব্যালেন্স করার চেয়ে।
AA ট্রির ক্ষেত্রে ব্যালেন্স রিস্টোর করার জন্য শুধু দুটি ডISTINCT অপারেশন প্রয়োজন: "skew" এবং "split"। Skew হল একটি রাইট রোটেশন যা একটি সাবট্রি যাতে লেফট হরিজন্টাল লিংক থাকে সেটিকে রাইট হরিজন্টাল লিংক থাকা সাবট্রি দিয়ে রিপ্লেস করে। Split-এর কেসে, এটি একটি লেফট রোটেশন এবং লেভেল ইনক্রিমেন্ট যা দুই বা অধিক কনসেকিউটিভ রাইট হরিজন্টাল লিংক থাকা সাবট্রি কে দুটি কম কনসেকিউটিভ রাইট হরিজন্টাল লিংক থাকা সাবট্রি দিয়ে রিপ্লেস করে। অপারেশনগুলো, "skew" এবং "split", নিচে ব্যাখ্যা করা হলো −
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
Split −
