js实现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);
}