溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點(diǎn)擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

JavaScript中怎么構(gòu)建一個(gè)avl樹

發(fā)布時(shí)間：2021-06-21 18:27:15 來源：億速云 閱讀：149 作者：Leah 欄目：大數(shù)據(jù)

這期內(nèi)容當(dāng)中小編將會(huì)給大家?guī)碛嘘P(guān)JavaScript中怎么構(gòu)建一個(gè)avl樹，文章內(nèi)容豐富且以專業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

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中怎么構(gòu)建一個(gè)avl樹了，如果剛好有類似的疑惑，不妨參照上述分析進(jìn)行理解。如果想知道更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道。

向AI問一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手