这期内容当中小编将会给大家带来有关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树了,如果刚好有类似的疑惑,不妨参照上述分析进行理解。如果想知道更多相关知识,欢迎关注亿速云行业资讯频道。
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。
原文链接:https://my.oschina.net/u/4217331/blog/4379502