জাভাস্ক্রিপ্টে AVL ঘূর্ণন

নিজের ভারসাম্য বজায় রাখতে, একটি AVL গাছ নিম্নলিখিত চার ধরণের ঘূর্ণন সম্পাদন করতে পারে -

• বাম ঘূর্ণন
• ডান ঘূর্ণন
• বাম-ডান ঘূর্ণন
• ডান-বাম ঘূর্ণন

প্রথম দুটি ঘূর্ণন একক ঘূর্ণন এবং পরের দুটি ঘূর্ণন দ্বিগুণ ঘূর্ণন। একটি ভারসাম্যহীন গাছের জন্য, আমাদের কমপক্ষে 2 উচ্চতার একটি গাছের প্রয়োজন। এই সাধারণ গাছটি দিয়ে, আসুন একে একে বুঝতে পারি।

বাম ঘূর্ণন

যদি একটি গাছ ভারসাম্যহীন হয়ে পড়ে, যখন একটি নোড ডান সাবট্রির ডান সাবট্রিতে ঢোকানো হয়, তখন আমরা একটি একক বাম ঘূর্ণন সম্পাদন করি -

আমাদের উদাহরণে, নোড A A-এর ডান সাবট্রির ডান সাবট্রিতে একটি নোড ঢোকানো হওয়ায় ভারসাম্যহীন হয়ে পড়েছে। আমরা A তৈরি করে বাম ঘূর্ণন সম্পাদন করি B-এর বাম-সাবট্রি . এই ঘূর্ণনকে এলএল ঘূর্ণনও বলা হয়। আসুন দেখি কিভাবে আমরা এটি বাস্তবায়ন করতে পারি -

function rotationLL(node) {
let tmp = node.left;
node.left = tmp.right;
tmp.right = node;
return tmp;
}

ডান ঘূর্ণন

বাম সাবট্রির বাম সাবট্রিতে একটি নোড ঢোকানো হলে AVL গাছ ভারসাম্যহীন হয়ে যেতে পারে। গাছের তখন সঠিক ঘূর্ণন প্রয়োজন।

চিত্রিত হিসাবে, ভারসাম্যহীন নোড একটি ডান ঘূর্ণন সম্পাদন করে তার বাম সন্তানের ডান সন্তান হয়ে ওঠে। একে আরআর রোটেশনও বলা হয়। আসুন দেখি এটা কোডে কেমন দেখায় −

function rotationRR(node) {
let tmp = node.right;
node.right = tmp.left;
tmp.left = node;
return tmp;
}

বাম-ডান ঘূর্ণন

ডাবল ঘূর্ণন হল ঘূর্ণনগুলির ইতিমধ্যে ব্যাখ্যা করা সংস্করণগুলির একটি সামান্য জটিল সংস্করণ। এগুলিকে আরও ভালভাবে বোঝার জন্য, আমাদের ঘূর্ণনের সময় সম্পাদিত প্রতিটি ক্রিয়াকে নোট করা উচিত। প্রথমে বাম-ডান ঘূর্ণন কিভাবে সঞ্চালন করতে হয় তা পরীক্ষা করা যাক। একটি বাম-ডান ঘূর্ণন হল বাম ঘূর্ণনের একটি সংমিশ্রণ যার পরে একটি ডান ঘূর্ণন।

রাজ্য	ক্রিয়া
	বাম সাবট্রির ডান সাবট্রিতে একটি নোড ঢোকানো হয়েছে। এটি C করে একটি ভারসাম্যহীন নোড। এই পরিস্থিতিগুলি AVL গাছকে বাম-ডান ঘূর্ণন সঞ্চালন করতে দেয়৷
	আমরা প্রথমে C. এর বাম সাবট্রিতে বাম ঘূর্ণন সম্পাদন করি এটি A করে , B এর বাম সাবট্রি .
	নোড C এখনও ভারসাম্যহীন, তবে এখন, এটি বাম-সাবট্রির বাম-সাবট্রির কারণে।
	আমরা এখন B তৈরি করে গাছটিকে ডানদিকে ঘোরাব এই সাবট্রির নতুন রুট নোড। C এখন তার নিজের বাম সাবট্রির ডান সাবট্রি হয়ে যায়।
	গাছটি এখন ভারসাম্যপূর্ণ।

এটিকে এলআর রোটেশনও বলা হয় কারণ আমরা প্রথমে একটি বাম ঘূর্ণন সঞ্চালন করি এবং তারপরে ডান ঘূর্ণন করি। এটি পূর্ববর্তী 2টি পদ্ধতি ব্যবহার করে প্রয়োগ করা যেতে পারে -

function rotationLR(node) {
node.left = rotationRR(node.left);
return rotationLL(node);
}

ডান-বাম ঘূর্ণন

দ্বিতীয় ধরনের ডবল ঘূর্ণন হল ডান-বাম ঘূর্ণন। এটি ডান ঘূর্ণনের সংমিশ্রণ এবং একটি বাম ঘূর্ণন দ্বারা অনুসরণ করা হয়।

রাজ্য	ক্রিয়া
	ডান সাবট্রির বাম সাবট্রিতে একটি নোড ঢোকানো হয়েছে। এটি A, করে ব্যালেন্স ফ্যাক্টর 2 সহ একটি ভারসাম্যহীন নোড।
	প্রথম, আমরা C বরাবর সঠিক ঘূর্ণন সম্পাদন করি নোড, C তৈরি করে তার নিজের বাম সাবট্রির ডান সাবট্রি B . এখন, B A এর ডান সাবট্রি হয়ে যায় .
	নোড A ডান সাবট্রির ডান সাবট্রির কারণে এখনও ভারসাম্যহীন এবং একটি বাম ঘূর্ণন প্রয়োজন৷
	একটি বাম ঘূর্ণন B করে সঞ্চালিত হয় সাবট্রির নতুন রুট নোড। A ডান সাবট্রি B এর বাম সাবট্রি হয়ে যায় .
	গাছটি এখন ভারসাম্যপূর্ণ।

এটিকে RL ঘূর্ণনও বলা হয় কারণ আমরা প্রথমে একটি ডান ঘূর্ণন সঞ্চালন করি এবং তারপরে একটি বাম ঘূর্ণন করি। এটি পূর্ববর্তী 2টি পদ্ধতি ব্যবহার করে প্রয়োগ করা যেতে পারে -

function rotationRL(node) {
node.right = rotationLL(node.right);
return rotationRR(node);
}