জাভাস্ক্রিপ্টে AVL রোটেশন

খुदকে ব্যালেন্স করতে, একটি AVL ট্রি নিচের চার ধরনের রোটেশন পারফর্ম করতে পারে:

• লেফট রোটেশন (Left rotation)
• রাইট রোটেশন (Right rotation)
• লেফট-রাইট রোটেশন (Left-Right rotation)
• রাইট-লেফট রোটেশন (Right-Left rotation)

প্রথম দুটি রোটেশন হলো সিঙ্গল রোটেশন এবং পরের দুটি হলো ডাবল রোটেশন। একটি আনব্যালেন্সড ট্রি পেতে হলে আমাদের কমপক্ষে উচ্চতা ২-এর একটি ট্রি দরকার। এই সিম্পল ট্রি দিয়ে আসুন একে একে বুঝি।

লেফট রোটেশন (Left Rotation)

যদি একটি ট্রি আনব্যালেন্সড হয়, যখন একটি নোড ডান সাবট্রির ডান সাবট্রিতে ইনসার্ট হয়, তবে আমরা একটি সিঙ্গল লেফট রোটেশন পারফর্ম করি:

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

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

রাইট রোটেশন (Right Rotation)

যদি একটি নোড বাম সাবট্রির বাম সাবট্রিতে ইনসার্ট হয় তবে AVL ট্রি আনব্যালেন্সড হতে পারে। ট্রিটাকে তখন একটি রাইট রোটেশন দরকার।

যেমন চিত্রে দেখানো, আনব্যালেন্সড নোডটি তার বাম চাইল্ডের ডান চাইল্ড বানতে একটি রাইট রোটেশন পারফর্ম করে। এটাকে RR রোটেশনও বলা হয়। আসুন কোডে কীভাবে দেখে তা দেখি:

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

লেফট-রাইট রোটেশন (Left-Right Rotation)

ডাবল রোটেশনগুলি ইতিমধ্যে ব্যাখ্যা করা রোটেশনগুলোর কিছুটা জটিল ভার্সন। সেগুলো ভালোভাবে বুঝতে, রোটেশনের সময় প্রতিটি অ্যাকশন নোট করা উচিত। আসুন প্রথমে চেক করি লেফট-রাইট রোটেশন কীভাবে পারফর্ম করতে হয়। একটি লেফট-রাইট রোটেশন হলো একটি লেফট রোটেশন যেটি একটি রাইট রোটেশনের পরвенি।

স্টেট (State)	অ্যাকশন (Action)
	বাম সাবট্রির ডান সাবট্রিতে একটি নোড ইনসার্ট হয়েছে। এতে C একটি আনব্যালেন্সড নোড হয়ে যায়। এই পরিস্থিতিগুলো AVL ট্রিকে লেফট-রাইট রোটেশন পারফর্ম করতে বাধ্য করে।
	আমরা প্রথমে C-এর বাম সাবট্রিতে লেফট রোটেশন পারফর্ম করি। এতে A, B-এর বাম সাবট্রি হয়ে যায়।
	নোড C এখনও আনব্যালেন্সড, কিন্তু এখন এর কারণ হলো বাম-সাবট্রির বাম-সাবট্রি।
	এখন আমরা ট্রিটি রাইট-রোটেট করব, যা B-কে এই সাবট্রির নতুন রুট নোড বানাবে। C এখন তার নিজস্ব বাম সাবট্রির ডান সাবট্রি হয়ে যায়।
	ট্রি এখন ব্যালেন্সড।

এটাকে LR রোটেশনও বলা হয় কারণ আমরা প্রথমে একটি লেফট রোটেশন এরপর একটি রাইট রোটেশন পারফর্ম করি। এটি পূর্বের ২টি মেথড ব্যবহার করে নিচের মত বাস্তবায়ন করা যায়:

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

রাইট-লেফট রোটেশন (Right-Left Rotation)

ডাবল রোটেশনের দ্বিতীয় ধরন হলো রাইট-লেফট রোটেশন। এটি একটি রাইট রোটেশন যেটি একটি লেফট রোটেশনের পরвенি।

স্টেট (State)	অ্যাকশন (Action)
	ডান সাবট্রির বাম সাবট্রিতে একটি নোড ইনসার্ট হয়েছে। এতে A, একটি আনব্যালেন্সড নোড হয়ে যায় যার ব্যালেন্স ফ্যাক্টর ২।
	প্রথমে, আমরা C নোডের সাথে রাইট রোটেশন পারফর্ম করি, যা C-কে তার নিজস্ব বাম সাবট্রি B-এর ডান সাবট্রি বানায়। এখন, B A-এর ডান সাবট্রি হয়ে যায়।
	নোড A এখনও আনব্যালেন্সড কারণ এর ডান সাবট্রির ডান সাবট্রি এবং একটি লেফট রোটেশন দরকার।
	একটি লেফট রোটেশন পারফর্ম করা হয় B-কে সাবট্রির নতুন রুট নোড বানিয়ে। A তার ডান সাবট্রি B-এর বাম সাবট্রি হয়ে যায়।
	ট্রি এখন ব্যালেন্সড।

এটাকে RL রোটেশনও বলা হয় কারণ আমরা প্রথমে একটি রাইট রোটেশন এরপর একটি লেফট রোটেশন পারফর্ম করি। এটি পূর্বের ২টি মেথড ব্যবহার করে নিচের মত বাস্তবায়ন করা যায়:

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