平衡二叉树¶

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

/**
 * 自平衡二叉搜索树
 * 
 * 1. 左右子树的高度差小于等于 1；
 * 2. 其每一个子树均为平衡二叉树。
 * */
export default class AvlTree extends BinarySearchTree {
  /**
   * @param {*} value
   */
  insert(value) {
    const insertedNode = super.insert(value);

    // 调整 from 插入节点 to 根节点
    let currentNode = this.root.find(value);
    while(currentNode) {
      this.balance(currentNode);
      currentNode = currentNode.parent;
    }

    return insertedNode;
  }

  /**
   * @param {*} value
   * @return {boolean}
   */
  remove(value) {
    super.remove(value);

    this.balance(this.root);
  }

  /**
   * @param {BinarySearchTreeNode} node
   */
  balance(node) {
    if(node.balanceFactor > 1) {
      // Left rotation.
      if (node.left.balanceFactor > 0) {
        // 左左旋
        this.rotateLeftLeft(node);
      } else if (node.left.balanceFactor < 0) {
        // 左右旋
        this.rotateLeftRight(node);
      }
    } else if(node.balanceFactor  < -1) {
      // Right rotation.
      if (node.right.balanceFactor > 0) {
        // 右左旋
        this.rotateRightLeft(node);
      } else if (node.right.balanceFactor < 0) {
        // 右右旋
        this.rotateRightRight(node);
      }
    }
  }

  /**
   * @param {BinarySearchTreeNode} rootNode
   */
  rotateLeftLeft(rootNode) {
    // Detach left node from root node.
    const leftNode = rootNode.left;
    rootNode.setLeft(null);

    // Make left node to be a child of rootNode's parent.
    if (rootNode.parent) {
      // rootNode.parent.setLeft(leftNode);
      rootNode.parent.replaceChild(rootNode, leftNode);
    } else if (rootNode === this.root) {
      // 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.setLeft(leftNode.right);
    }

    // Attach rootNode to the right of leftNode.
    leftNode.setRight(rootNode);
  }


  /**
   * @param {BinarySearchTreeNode} rootNode
   */
  rotateLeftRight(rootNode) {
    // Detach left node from root node.
    const leftNode = rootNode.left;
    rootNode.setLeft(null);

    // Detach leftRightNode from leftNode.
    const leftRightNode = leftNode.right;
    leftNode.setRight(null);

    // Preserve leftRightNode's left subtree.
    if (leftRightNode.left) {
      leftNode.setRight(leftRightNode.left);
      leftRightNode.setLeft(null);
    }

    leftRightNode.setLeft(leftNode);
    rootNode.setLeft(leftRightNode);

    this.rotateLeftLeft(rootNode);
  }

  /**
   * @param {BinarySearchTreeNode} rootNode
   */
  rotateRightLeft(rootNode) {
    // Detach right node 
    const rightNode = rootNode.right;
    rootNode.setRight(null);

    // Detach rightLeftNode
    const rightLeftNode = rightNode.left;
    rightNode.setLeft(null);

    // Preserve rightLeftNode's right subtree.
    if (rightLeftNode.right) {
      rightNode.setLeft(rightLeftNode.right);
      rightLeftNode.setRight(null);
    }

    rightLeftNode.setRight(rightNode);
    rootNode.setRight(rightLeftNode);

    this.rotateRightRight(rootNode);
  }

  /**
   * @param {BinarySearchTreeNode} rootNode
   */
  rotateRightRight(rootNode) {
    // Detach right node from root node.
    const rightNode = rootNode.right;
    rootNode.setRight(null);

    if (rootNode.parent) {
      rootNode.parent.replaceChild(rootNode, rightNode);
    } else if (rootNode === this.root) {
      this.root = rightNode;
    }

    // Preserve rightNode's left subtree.
    if (rightNode.left) {
      rootNode.setRight(rightNode.left);
    }

    rightNode.setLeft(rootNode);
  }
}