AVL树

import BinarySearchTree from '../binary-search-tree/BinarySearchTree';

export default class AvlTree extends BinarySearchTree {//AVL树类，继承自二叉搜索树
  /**
   * @param {*} value
   */
  insert(value) {//往AVL树中插入新节点
    // Do the normal BST insert.
    super.insert(value);//调用父类二叉搜索书的插入方法插入节点

    // Let's move up to the root and check balance factors along the way.
    //移除根节点沿着顺序检查平衡因子
    let currentNode = this.root.find(value);//找到刚才被插入的节点
    while (currentNode) {
      this.balance(currentNode);//调用balance方法使当前节点平衡，然后当前节点赋值为父节点，继续循环
      currentNode = currentNode.parent;
    }
  }

  /**
   * @param {*} value
   * @return {boolean}
   */
  remove(value) {//在AVL树中删除节点
    // Do standard BST removal.
    super.remove(value);//调用父类二叉搜索树的删除方法删除节点

    // Balance the tree starting from the root node.
    this.balance(this.root);//从根节点开始做平衡操作
  }

  /**
   * @param {BinarySearchTreeNode} node
   */
  balance(node) {
    // If balance factor is not OK then try to balance the node.
    if (node.balanceFactor > 1) {//如果当前节点的平衡因子大于1了，说明不平衡了
      // Left rotation.
      if (node.left.balanceFactor > 0) {//当前节点的左子节点平衡因子大于0，做左左旋转
        // Left-Left rotation
        this.rotateLeftLeft(node);
      } else if (node.left.balanceFactor < 0) {//当前节点的左子节点平衡因子小于0，做左右旋转
        // Left-Right rotation.
        this.rotateLeftRight(node);
      }
    } else if (node.balanceFactor < -1) {//当前节点的平衡因子小于-1
      // Right rotation.
      if (node.right.balanceFactor < 0) {//当前节点的右子节点平衡因子小于0，做右右旋转
        // Right-Right rotation
        this.rotateRightRight(node);
      } else if (node.right.balanceFactor > 0) {//当前节点的右子节点平衡因子大于0，做右左旋转
        // Right-Left rotation.
        this.rotateRightLeft(node);
      }
    }
  }

  /**
   * @param {BinarySearchTreeNode} rootNode
   */
  rotateLeftLeft(rootNode) {//左左旋转
    // Detach left node from root node.
    const leftNode = rootNode.left;//rootNode的左子节点
    rootNode.setLeft(null);//rootNode的左子节点设置为空

    // Make left node to be a child of rootNode's parent.
    if (rootNode.parent) {//如果rootNode有父节点
      rootNode.parent.setLeft(leftNode);//给rootNode的父节点设置左子节点为rootNode的左子节点
    } else if (rootNode === this.root) {
      //如果rooNode本身就是树的根节点，就将rootNode的左子节点设置为当前树的根节点
      // If root node is root then make left node to be a new root.
      this.root = leftNode;
    }

    // If left node has a right child then detach it and
    // attach it as a left child for rootNode.
    if (leftNode.right) {//如果rootNode的左子节点有右子节点，就分离它，将它作为rootNode的左子节点连接
      rootNode.setLeft(leftNode.right);
    }

    // Attach rootNode to the right of leftNode.
    leftNode.setRight(rootNode);//将rootNode作为其左子节点的右子节点
  }

  /**
   * @param {BinarySearchTreeNode} rootNode
   */
  rotateLeftRight(rootNode) {//左右旋转
    // Detach left node from rootNode since it is going to be replaced.
    const leftNode = rootNode.left;//rootNode节点的左子节点
    rootNode.setLeft(null);//设置rootNode的左子节点为空

    // Detach right node from leftNode.
    const leftRightNode = leftNode.right;//rootNode的左子节点的右子节点
    leftNode.setRight(null);//设置左子节点的右节点为空

    // Preserve leftRightNode's left subtree.
    if (leftRightNode.left) {//如果rootNode的左子节点的右子节点拥有左子节点
      //就设置rootNode的左子节点的右子节点为如果rootNode的左子节点的右子节点的左子节点
      leftNode.setRight(leftRightNode.left);
      leftRightNode.setLeft(null);//rootNode的左子节点的右子节点的左子节点设置为空
    }

    // Attach leftRightNode to the rootNode.
    rootNode.setLeft(leftRightNode);//rootNode设置左子节点为rootNode的左子节点的右子节点

    // Attach leftNode as left node for leftRight node.
    leftRightNode.setLeft(leftNode);//rootNode的左子节点的右子节点设置左子节点为rootNode的左子节点

    // Do left-left rotation.
    this.rotateLeftLeft(rootNode);//对rootNode进行左左旋转操作
  }

  /**
   * @param {BinarySearchTreeNode} rootNode
   */
  rotateRightLeft(rootNode) {//右左旋转
    // Detach right node from rootNode since it is going to be replaced.
    const rightNode = rootNode.right;//rootNode的右子节点
    rootNode.setRight(null);//设置rootNode的右子节点为空

    // Detach left node from rightNode.
    const rightLeftNode = rightNode.left;//rootNode的右子节点的左子节点
    rightNode.setLeft(null);//设置rootNode的右子节点的左子节点为空

    if (rightLeftNode.right) {//如果rootNode的右子节点的左子节点拥有右子节点
      rightNode.setLeft(rightLeftNode.right);//设置rootNode的右节点的左子节点为rootNode的右子节点的左子节点的右子节点
      rightLeftNode.setRight(null);//rootNode的右子节点的左子节点的右子节点设置为空
    }

    // Attach rightLeftNode to the rootNode.
    rootNode.setRight(rightLeftNode);//设置rootNode的哦右子节点为rootNode的右子节点的左子节点

    // Attach rightNode as right node for rightLeft node.
    rightLeftNode.setRight(rightNode);//设置rootNode的右子节点的左子节点的右子节点为rootNode的右子节点

    // Do right-right rotation.
    this.rotateRightRight(rootNode);//对rootNode进行右右旋转
  }

  /**
   * @param {BinarySearchTreeNode} rootNode
   */
  rotateRightRight(rootNode) {//右右旋转
    // Detach right node from root node.
    const rightNode = rootNode.right;//rootNode的右子节点
    rootNode.setRight(null);//设置rootNode的右子节点为空

    // Make right node to be a child of rootNode's parent.
    if (rootNode.parent) {//如果rootNode拥有父节点，就设置rootNode的父节点的右子节点为rootNode的右子节点
      rootNode.parent.setRight(rightNode);
    } else if (rootNode === this.root) {//如果rootNode本身就是根节点，就像根节点设置为rootNode的右子节点
      // If root node is root then make right node to be a new root.
      this.root = rightNode;
    }

    // If right node has a left child then detach it and
    // attach it as a right child for rootNode.
    if (rightNode.left) {//如果rootNode的右子节点拥有左子节点，就设置rootNode的右子节点为rootNode的右子节点的左子节点
      rootNode.setRight(rightNode.left);
    }

    // Attach rootNode to the left of rightNode.
    rightNode.setLeft(rootNode);//rootNode的右子节点的左子节点设置为rootNode
  }
}