কম্পিউটার বিজ্ঞানে একটি AA ট্রিকে সংজ্ঞায়িত করা হয় সুষম বৃক্ষের একটি ফর্ম হিসাবে যা কার্যকরীভাবে আদেশকৃত ডেটা সংরক্ষণ এবং পুনরুদ্ধার করার জন্য প্রয়োগ করা হয়। AA গাছগুলিকে লাল-কালো গাছের একটি বৈচিত্র হিসাবে বিবেচনা করা হয়, বাইনারি অনুসন্ধান গাছের একটি রূপ যা এন্ট্রিগুলির দক্ষ সংযোজন এবং মুছে ফেলাকে সমর্থন করে। লাল-কালো গাছের বিপরীতে, একটি AA গাছে লাল নোডগুলি শুধুমাত্র ডান সাবচাইল্ড হিসাবে যোগ করা যেতে পারে, বাম সাবচাইল্ড নয়। এই অপারেশনের ফলাফল হল 2-3-4 গাছের পরিবর্তে একটি 2-3 গাছের সিমুলেশন, যা রক্ষণাবেক্ষণের কাজগুলিকে সরলীকরণ করে। একটি লাল-কালো গাছের রক্ষণাবেক্ষণের অ্যালগরিদমগুলিকে গাছের সঠিক ভারসাম্য রক্ষার জন্য সাতটি ভিন্ন আকৃতি অনুমান বা বিবেচনা করতে হবে -
লাল-কালো গাছের বিপরীতে, অন্য দিকে একটি AA গাছের জন্য শুধুমাত্র সঠিক লিঙ্কগুলি লাল হতে পারে এমন কঠোর প্রয়োজনীয়তার কারণে শুধুমাত্র দুটি আকার অনুমান বা বিবেচনা করতে হবে -
ভারসাম্য ঘূর্ণন
যেখানে লাল-কালো গাছের জন্য নোড (রঙ) প্রতি এক বিট ব্যালেন্সিং মেটাডেটা প্রয়োজন, AA গাছের জন্য নোড প্রতি O(log(log(N))) বিট মেটাডেটা প্রয়োজন, একটি পূর্ণসংখ্যা "লেভেল" আকারে। নিচের ইনভেরিয়েন্টগুলি AA গাছের জন্য ধরে −
-
প্রতিটি লিফ নোডের স্তরকে এক হিসাবে বিবেচনা করা হয়৷
-
প্রতিটি বাম সন্তানের স্তর তার পিতামাতার চেয়ে ঠিক এক ছোট।
-
প্রতিটি সঠিক সন্তানের স্তর তার পিতামাতার সমান বা তার চেয়ে ছোট।
-
প্রতিটি ডান নাতি-নাতনির স্তর তার দাদা-দাদির থেকে কঠোরভাবে ছোট।
-
একটির চেয়ে উচ্চ স্তরের প্রতিটি নোডে দুটি সন্তান রয়েছে৷
একটি AA গাছকে পুনরায় ভারসাম্য করা একটি লাল-কালো গাছকে পুনরায় ভারসাম্য দেওয়ার চেয়ে পদ্ধতিগতভাবে অনেক সহজ বা সহজ৷
একটি AA গাছের ক্ষেত্রে ভারসাম্য পুনরুদ্ধারের জন্য শুধুমাত্র দুটি স্বতন্ত্র ক্রিয়াকলাপ প্রয়োজন:"স্কু" এবং "বিভক্ত"। একটি বাম অনুভূমিক লিঙ্ক সমন্বিত একটি উপবৃক্ষের পরিবর্তে একটি ডান অনুভূমিক লিঙ্ক সহ একটি সাবট্রিকে প্রতিস্থাপন করার জন্য স্কুকে ডান ঘূর্ণন হিসাবে বিবেচনা করা হয়। স্প্লিটের ক্ষেত্রে, এটি একটি বাম ঘূর্ণন এবং স্তর বৃদ্ধি যা একটি সাবট্রিকে প্রতিস্থাপন করে যার মধ্যে দুটি বা ততোধিক ক্রমাগত ডান অনুভূমিক লিঙ্ক রয়েছে এবং একটিতে দুটি কম পরপর ডান অনুভূমিক লিঙ্ক রয়েছে। অপারেশন, "Skew" এবং "split" , নীচে ব্যাখ্যা করা হয়েছে −
ফাংশন স্কু হল
ইনপুট:একটি AA ট্রি যেটিকে পুনরায় ভারসাম্যপূর্ণ করতে হবে একটি নোড দ্বারা প্রতিনিধিত্ব করা হয়, t। আউটপুট:পুনরায় ভারসাম্যপূর্ণ AA ট্রি অন্য নোড দ্বারা প্রতিনিধিত্ব করা হয়। যদি nil(t) তারপর nilelse রিটার্ন করুন যদি nil(left(t)) তারপর telse if level(left(t)) ==level(t) তারপর অনুভূমিক বাম দিকের পয়েন্টারগুলি বিনিময় করুন লিঙ্ক l =left(t)left(t) :=right(l)right(l) :=treturn lelsereturn tend ifend ফাংশন
ফাংশন বিভাজন হল
ইনপুট:একটি AA ট্রি যেটিকে পুনরায় ভারসাম্যপূর্ণ করতে হবে একটি নোড দ্বারা প্রতিনিধিত্ব করা হয়, t। আউটপুট:ভারসাম্যপূর্ণ AA ট্রি অন্য নোড দ্বারা প্রতিনিধিত্ব করা হয়। যদি nil(t) তারপর nilelse রিটার্ন করুন যদি nil(right(t)) বা nil(right(right(t))) তারপর telse if level(t) ==level(right) (right(t))) তারপর আমাদের দুটি অনুভূমিক ডান লিঙ্ক আছে। মাঝের নোডটি নেওয়া হয়, এটিকে উন্নত করুন এবং এটি ফিরিয়ে দিন। r =ডান
বিভক্ত -
