/**
* 平衡二叉搜索树 avl
*/
let alert = console.log;
// console.log = () => {};
class TreeNode {
constructor(value, leftNode, rightNode) {
this.value = value;
this.leftNode = leftNode;
this.rightNode = rightNode;
}
}
/**
* 1、创建 create(){}
* 2、插入 insert(){}
* 3、遍历 display(){}
* 4、查看 find(){}
* 5、删除 remove(){}
*/
class AvlTree {
constructor() {
this.root = null;
}
create() {
let length = 100;
for (let i = 0; i < length; i++) {
let value = Math.trunc(Math.random() * 100 + 1);
console.log("新增元素节点: ", value);
this.root = this.insert(this.root, value);
}
}
getHeight(root) {
if (root == null) {
return 0;
}
let leftHeight = 0;
if (root.leftNode) {
leftHeight = this.getHeight(root.leftNode);
}
let rightHeight = 0;
if (root.rightNode) {
rightHeight = this.getHeight(root.rightNode);
}
return Math.max(leftHeight, rightHeight) + 1;
}
getDelta(root) {
if (root == null) {
return 0;
}
let leftHeight = this.getHeight(root.leftNode);
let rightHeight = this.getHeight(root.rightNode);
return leftHeight - rightHeight;
}
//对增加,删除时,对节点进行平衡
balance(root) {
if (root == null) {
return null;
}
console.log(`${root.value}: ${this.getDelta(root)}`);
//左子树导致不平衡。//表示是 LR 类型的旋转。
if (this.getDelta(root) > 1 && this.getDelta(root.leftNode) < 0) {
console.log(`开始LR旋转: ${root.value}`);
return this.lrrotate(root);
//左子树导致不平衡。//表示是 LL 类型的旋转。
} else if (this.getDelta(root) > 1) {
console.log(`开始LL旋转: ${root.value}`);
return this.llrotate(root);
} else if (
//右子树导致的不平衡。 //表示是 RL 类型的旋转
this.getDelta(root) < -1 &&
this.getDelta(root.rightNode) > 0
) {
//右子树导致的不平衡。 //表示是 RL 类型的旋转
console.log(`开始RL旋转: ${root.value}`);
return this.rlrotate(root);
} else if (this.getDelta(root) < -1) {
console.log(`开始RR旋转: ${root.value}`);
return this.rrrotate(root);
}
return root;
}
llrotate(root) {
//左边的失衡,让左子节点 A 替代当前节点 B。
let leftNode = root.leftNode;
root.leftNode = leftNode.rightNode;
leftNode.rightNode = root;
console.log("LL", leftNode);
return leftNode;
}
rrrotate(root) {
let rightNode = root.rightNode;
root.rightNode = rightNode.leftNode;
rightNode.leftNode = root;
console.log("RR", rightNode);
return rightNode;
}
lrrotate(root) {
root.leftNode = this.rrrotate(root.leftNode);
return this.llrotate(root);
}
rlrotate(root) {
root.rightNode = this.llrotate(root.rightNode);
return this.rrrotate(root);
}
insert(root, value) {
if (!root) {
return new TreeNode(value, null, null);
}
if (root.value >= value) {
root.leftNode = this.insert(root.leftNode, value);
}
if (root.value < value) {
root.rightNode = this.insert(root.rightNode, value);
}
return this.balance(root);
}
display(root) {
if (root == null) {
return;
}
let queue = [];
let level = 0;
let input = "";
root.level = 1;
queue.push(root);
while (queue.length) {
let node = queue.shift();
if (level != node.level) {
level++;
console.log(input.replace(/,$/, ""));
input = "";
}
input += `${node.value},`;
if (node.leftNode) {
node.leftNode.level = node.level + 1;
queue.push(node.leftNode);
}
if (node.rightNode) {
node.rightNode.level = node.level + 1;
queue.push(node.rightNode);
}
}
console.log(input.replace(/,$/, ""));
}
find(root, value) {
if (!root) {
return null;
}
if (root.value > value) {
return this.find(root.leftNode, value);
}
if (root.value < value) {
return this.find(root.rightNode, value);
}
if (root.value == value) {
return root;
}
}
remove(root, value) {
if (!root) {
return null;
}
if (root.value > value) {
root.leftNode = this.remove(root.leftNode, value);
return this.balance(root);
}
if (root.value < value) {
root.rightNode = this.remove(root.rightNode, value);
return this.balance(root);
}
//找到当前节点
//处理删除的四种情形
if (!root.leftNode && !root.rightNode) {
return null;
} else if (!root.leftNode) {
return root.rightNode;
} else if (!root.rightNode) {
return root.leftNode;
} else {
//左右子节点都存在的情形
let node = root.rightNode;
while (node.leftNode) {
node = node.leftNode;
}
root.value = node.value;
//删除node
root.rightNode = this.remove(root.rightNode, node.value);
return this.balance(root);
}
}
}
function isAvlTree(root) {
if (root == undefined || root == null) {
return {
level: 0,
isAvl: true,
};
}
let leftDelta = isAvlTree(root.leftNode);
let rightDelta = isAvlTree(root.rightNode);
let delta = leftDelta.level - rightDelta.level;
let level = Math.max(leftDelta.level, rightDelta.level) + 1;
return {
isAvl: leftDelta.isAvl && rightDelta.isAvl && Math.abs(delta) < 2,
level,
};
}
let length = 1000;
let count = 0;
// for (let i = 0; i < 1; i++) {
console.log("");
console.log("");
console.log("");
console.log("========================>");
const avlTree = new AvlTree();
avlTree.create();
const delta = isAvlTree(avlTree.root);
if (!delta.isAvl) {
count++;
alert("不是一棵平衡树: ", delta.isAvl);
avlTree.display(avlTree.root);
}
console.log("<========================");
console.log("");
console.log("");
console.log("");
// }
// alert(count);
for (let i = 0; i < 1000; i++) {
let value = Math.trunc(Math.random() * 100);
avlTree.remove(avlTree.root, value);
const delta = isAvlTree(avlTree.root);
if (!delta.isAvl) {
count++;
alert("不是一棵平衡树: ", delta.isAvl);
avlTree.display(avlTree.root);
} else {
alert("是一棵平衡树: ", delta.isAvl);
avlTree.display(avlTree.root);
}
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)