AVL গাছ বাম এবং ডান উপ-বৃক্ষের উচ্চতা পরীক্ষা করে এবং নিশ্চিত করে যে পার্থক্য 1-এর বেশি নয়। এই পার্থক্যটিকে বলা হয় ব্যালেন্স ফ্যাক্টর।>
উদাহরণস্বরূপ, নিম্নলিখিত গাছগুলিতে, প্রথম গাছটি ভারসাম্যপূর্ণ এবং পরের দুটি গাছ ভারসাম্যপূর্ণ নয় −
দ্বিতীয় গাছে, C-এর বাম উপবৃক্ষের উচ্চতা 2 এবং ডান উপবৃক্ষের উচ্চতা 0, তাই পার্থক্য হল 2। তৃতীয় গাছে, A-এর ডান উপবৃক্ষের উচ্চতা 2 এবং বাম উপবৃক্ষটি অনুপস্থিত, তাই এটি 0 , এবং পার্থক্য আবার 2. AVL গাছ পার্থক্য (ব্যালেন্স ফ্যাক্টর) শুধুমাত্র 1 হতে অনুমতি দেয়।
BalanceFactor = height(left-sutree) − height(right-sutree)
বাম এবং ডান উপ-গাছের উচ্চতার পার্থক্য 1-এর বেশি হলে, কিছু ঘূর্ণন কৌশল ব্যবহার করে গাছটি ভারসাম্যপূর্ণ হয়।
আসুন আমরা এই পদ্ধতিটি সংজ্ঞায়িত করি এবং ক্লাসটিও শুরু করি -
উদাহরণ
class AVLTree {
constructor() {
// Initialize a root element to null.
this.root = null;
}
getBalanceFactor(root) {
return this.getHeight(root.left) - this.getHeight(root.right);
}
getHeight(root) {
let height = 0;
if (root === null) {
height = -1;
} else {
height = Math.max(this.getHeight(root.left), this.getHeight(root.right)) + 1;
}
return height;
}
}
AVLTree.prototype.Node = class {
constructor(data, left = null, right = null) {
this.data = data;
this.left = left;
this.right = right;
}
}; 