AVL Tree এবং অন্যান্য Balanced Trees হল Binary Search Tree (BST) এর একটি বিশেষ ধরনের ডাটা স্ট্রাকচার যা self-balancing হয়। এতে প্রতিটি নোডের জন্য একটি নির্দিষ্ট balance factor থাকে যা নিশ্চিত করে যে গাছের উচ্চতা কখনোই খুব বেশি বৃদ্ধি পায় না। এর ফলে, গাছের অপারেশনগুলো (যেমন insertion, deletion, এবং searching) সবসময় O(log n) টাইম কমপ্লেক্সিটি সহ সম্পাদিত হয়।
এই গাইডে আমরা AVL Tree এবং Balanced Trees এর কার্যকারিতা, কাঠামো, এবং জাভাতে এর বাস্তবায়ন নিয়ে আলোচনা করব।
1. Balanced Tree এর ধারণা
Balanced Trees হল এমন একটি ডাটা স্ট্রাকচার যেখানে গাছের প্রতিটি নোডের বাম এবং ডান সাবট্রি এর উচ্চতার মধ্যে একটি নির্দিষ্ট সীমার মধ্যে পার্থক্য থাকে। এর ফলে গাছের গঠন কেবল একে অপরের থেকে সমানভাবে সোজা হয়ে থাকে, যা গাছের অপারেশনগুলোকে অপটিমাইজ করে।
AVL Tree এর মধ্যে এমন একটি বিশেষ ধরনের ব্যালেন্সিং অ্যালগরিদম রয়েছে যা গাছের উচ্চতা নিশ্চিতভাবে নিয়ন্ত্রণ করে রাখে।
2. AVL Tree (Adelson-Velsky and Landis Tree)
AVL Tree হল একটি self-balancing binary search tree যেখানে প্রতিটি নোডের জন্য balance factor থাকে। একটি নোডের balance factor হল তার বাম সাবট্রি এবং ডান সাবট্রি এর উচ্চতার পার্থক্য। যদি এটি 1, 0, বা -1 থাকে, তবে গাছটি ব্যালেন্সড থাকে; অন্যথায়, গাছটিকে পুনরায় ব্যালেন্স করতে হবে।
- Balance Factor:
BF = Height(Left Subtree) - Height(Right Subtree) - AVL Tree Rules:
- এক নোডের বাম এবং ডান সাবট্রির উচ্চতার পার্থক্য সর্বাধিক 1 হতে পারে।
2.1. Rotation Operations in AVL Tree
এখানে চারটি rotation অপারেশন আছে যা AVL গাছের ব্যালেন্স ঠিক রাখতে সাহায্য করে:
- Left Rotation (Single Rotation)
- Right Rotation (Single Rotation)
- Left-Right Rotation (Double Rotation)
- Right-Left Rotation (Double Rotation)
2.2. AVL Tree Implementation in Java
class AVLTree {
class Node {
int data;
Node left, right;
int height;
public Node(int data) {
this.data = data;
this.height = 1; // Initial height is 1 (for new nodes)
}
}
private Node root;
// Utility method to get height of a node
private int height(Node node) {
return (node == null) ? 0 : node.height;
}
// Utility method to get balance factor of a node
private int getBalanceFactor(Node node) {
return (node == null) ? 0 : height(node.left) - height(node.right);
}
// Right rotation
private Node rightRotate(Node y) {
Node x = y.left;
Node T2 = x.right;
// Perform rotation
x.right = y;
y.left = T2;
// Update heights
y.height = Math.max(height(y.left), height(y.right)) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
return x; // New root
}
// Left rotation
private Node leftRotate(Node x) {
Node y = x.right;
Node T2 = y.left;
// Perform rotation
y.left = x;
x.right = T2;
// Update heights
x.height = Math.max(height(x.left), height(x.right)) + 1;
y.height = Math.max(height(y.left), height(y.right)) + 1;
return y; // New root
}
// Insert a node
public void insert(int data) {
root = insert(root, data);
}
private Node insert(Node node, int data) {
if (node == null) {
return new Node(data);
}
// Perform the normal BST insertion
if (data < node.data) {
node.left = insert(node.left, data);
} else if (data > node.data) {
node.right = insert(node.right, data);
} else {
return node; // Duplicates are not allowed
}
// Update the height of this ancestor node
node.height = 1 + Math.max(height(node.left), height(node.right));
// Get the balance factor of this ancestor node to check whether it became unbalanced
int balance = getBalanceFactor(node);
// If the node becomes unbalanced, then there are 4 cases
// Left Left Case
if (balance > 1 && data < node.left.data) {
return rightRotate(node);
}
// Right Right Case
if (balance < -1 && data > node.right.data) {
return leftRotate(node);
}
// Left Right Case
if (balance > 1 && data > node.left.data) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && data < node.right.data) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node; // Return the (unchanged) node pointer
}
// Preorder traversal of the tree
public void preorder() {
preorder(root);
}
private void preorder(Node node) {
if (node != null) {
System.out.print(node.data + " ");
preorder(node.left);
preorder(node.right);
}
}
public static void main(String[] args) {
AVLTree tree = new AVLTree();
tree.insert(10);
tree.insert(20);
tree.insert(30);
tree.insert(15);
tree.insert(25);
System.out.print("Preorder traversal: ");
tree.preorder(); // Output: 20 10 15 30 25
}
}
2.3. Explanation:
- Insert Operation: ইনসার্ট করার সময়, গাছটি self-balancing হয় এবং যথাযথ রোটেশন অপারেশনগুলি প্রয়োগ হয়।
- Balancing the Tree: গাছের যেকোনো নোডের balance factor যদি 1 বা -1 এর বাইরে চলে যায়, তখন রোটেশন প্রয়োগ করা হয়।
- Traversal:
preorder()মেথডের মাধ্যমে গাছের সমস্ত উপাদান preorder traversal অনুসারে প্রদর্শন করা হয়।
3. Balanced Trees - Other Types
Balanced Trees এর মধ্যে বিভিন্ন ধরনের গাছ রয়েছে, যেমন Red-Black Tree, AVL Tree, এবং Splay Tree। তবে, AVL Tree হল একটি সবচেয়ে জনপ্রিয় এবং কার্যকরী self-balancing tree। এটি গাছের গঠনকে সব সময় ব্যালেন্সড রাখতে সাহায্য করে।
3.1. Red-Black Tree
- এটি একটি বিশেষ ধরনের ব্যালেন্সড বাইনারি সার্চ ট্রি যেখানে প্রতিটি নোডের একটি রঙ (লাল বা কালো) থাকে এবং নির্দিষ্ট নিয়ম অনুসরণ করে গাছটি ব্যালেন্স করা হয়। Red-Black Tree খুব দ্রুত অ্যাড/ডিলিট অপারেশন পরিচালনা করে।
3.2. Splay Tree
- এটি একটি অটো-ব্যালেন্সিং বাইনারি সার্চ ট্রি যেখানে নোডগুলিকে স্লাইড করা হয়, তবে এর পারফরম্যান্স সবসময় সেরা নয়।
সারাংশ
AVL Tree হল একটি self-balancing binary search tree, যেখানে প্রতিটি নোডের balance factor চেক করা হয় এবং সেই অনুযায়ী রোটেশন প্রয়োগ করা হয়। এর সাহায্যে আপনি বাইনারি সার্চ ট্রির অপারেশনগুলোকে O(log n) টাইমে সম্পাদন করতে পারেন। অন্যান্য Balanced Trees এর মধ্যে Red-Black Tree এবং Splay Tree রয়েছে যা ব্যালেন্সড গাছের ক্ষেত্রে বিভিন্ন ধরনের সমাধান প্রদান করে।
AVL Tree একটি খুবই কার্যকরী ডাটা স্ট্রাকচার যখন আপনাকে ডাটা সার্চ, ইনসার্ট এবং ডিলিট করার অপারেশন দ্রুত এবং সুনির্দিষ্টভাবে সম্পাদন করতে হয়।
Read more
