Javascript中的AVL树类
这是AVL树类的完整实现-
示例
class AVLTree {
constructor() {
//将根元素初始化为null。
this.root = null;
}
getBalanceFactor(root) {
return this.getHeight(root.left) - this.getHeight(root.right);
}
getHeight(root) {
let height = 0;
if (root === null || typeof root == "undefined") {
height = -1;
} else {
height = Math.max(this.getHeight(root.left), this.getHeight(root.right)) + 1;
}
return height;
}
insert(data) {
let node = new this.Node(data);
//检查树是否为空
if (this.root === null) {
//作为第一个元素插入this.root=node;
} else {
insertHelper(this, this.root, node);
}
}
inOrder() {
inOrderHelper(this.root);
}
}
AVLTree.prototype.Node = class {
constructor(data, left = null, right = null) {
this.data = data;
this.left = left;
this.right = right;
}
};
function insertHelper(self, root, node) {
(root === null) {
root = node;
} else if (node.data < root.data) {
//向左走！
root.left = insertHelper(self, root.left, node);
//检查平衡系数并执行适当的旋转
if (root.left !== null && self.getBalanceFactor(root) > 1) {
if (node.data > root.left.data) {
root = rotationLL(root);
} else {
root = rotationLR(root);
}
}
} else if (node.data > root.data) {
//向右走！根。
right = insertHelper(self, root.right, node);
//检查平衡系数并执行适当的旋转
if (root.right !== null && self.getBalanceFactor(root) < -1) {
if (node.data > root.right.data) {
root = rotationRR(root);
} else {
root = rotationRL(root);
}
}
}
return root;
}
function inOrderHelper(root) {
if (root !== null) {
inOrderHelper(root.left);
console.log(root.data);
inOrderHelper(root.right);
}
}
function rotationLL(node) {
let tmp = node.left;
node.left = tmp.right;
tmp.right = node;
return tmp;
}
function rotationRR(node) {
let tmp = node.right;
node.right = tmp.left;
tmp.left = node;
return tmp;
}
function rotationLR(node) {
node.left = rotationRR(node.left);
return rotationLL(node);
}
function rotationRL(node) {
node.right = rotationLL(node.right);
return rotationRR(node);
}