您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
这期内容当中小编将会给大家带来有关JavaScript中怎么构建一个avl树,文章内容丰富且以专业的角度为大家分析和叙述,阅读完这篇文章希望大家可以有所收获。
function Node(value) {
this.value = value;
this.left = this.right = null;
this.height = 0;
}
function height(node) {
return node ? node.height : 0;
}
function rotateLeft(node) {
const right = node.right;
node.right = right.left;
right.left = node;
node.height = Math.max(height(node.left, node.right)) + 1;
right.height = Math.max(height(right.left, right.right)) + 1;
return right;
}
function rotateRight(node) {
const left = node.left;
node.left = left.right;
left.right = node;
node.height = Math.max(height(node.left, node.right)) + 1;
left.height = Math.max(height(left.left, left.right)) + 1;
return left;
}
function rotateLeftRight(node) {
node.left = rotateLeft(node.left);
return rotateRight(node);
}
function rotateRightLeft(node) {
node.right = rotateRight(node.right);
return rotateLeft(node);
}
function avlTreeInsert(node, value) {
if (!node) {
node = new Node(value);
} else if (value > node.value) {
node.right = avlTreeInsert(node.right, value);
if (height(node.right) - height(node.left) == 2) {
if (value > node.right.value) {
node = rotateLeft(node);
} else {
node = rotateRightLeft(node);
}
}
} else if (value < node.value){
node.left = avlTreeInsert(node.left, value);
if (height(node.right) - height(node.left) == 2) {
if (value > node.left.value) {
node = rotateRight(node);
} else {
node = rotateLeftRight(node);
}
}
}
node.height = Math.max(height(node.right), height(node.left)) + 1;
return node;
}
(function test() {
let i = 0;
let data = [];
while(i < 100) {
data.push(i++);
}
i = 0;
let root;
while(i < data.length) {
root = avlTreeInsert(root, data[i++]);
}
const queue = [root];
let current;
while(current = queue.shift()) {
console.log(current.value, height(current.right) - height(current.left));
queue.push(current.right);
queue.push(current.left);
}
console.log(root);
console.log(find(root ,99))
})();
function find(node, value) {
if (!node) {
return null;
}
if (node.value === value) {
return node;
}
return find(node.value > value ? node.left : node.right, value);
}
上述就是小编为大家分享的JavaScript中怎么构建一个avl树了,如果刚好有类似的疑惑,不妨参照上述分析进行理解。如果想知道更多相关知识,欢迎关注亿速云行业资讯频道。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。