红黑树¶

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

const RED_BLACK_TREE_COLORS = {
  red: 'red',
  black: 'black',
};

const COLOR_PROP_NAME = 'color';

/**
 * 红黑树是一种含有红黑结点并能自平衡的二叉查找树。
 * ![x](http://river.chenleileicode.com/algorithms/red-black-tree.svg)
 * 
 * 性质：
 * 1：每个节点要么是黑色，要么是红色。
 * 2：根节点是黑色。
 * 3：叶子节点是NIL且黑色。
 * 4：红色结点的两个孩子都是黑色（不存在两个相邻的红色结点）。
 * 5：任意一结点到每个叶子结点的路径，都经过数量相同的黑结点。
 * 所以，我们叫红黑树这种平衡为 **黑色完美平衡**。
 * 
 * 操作：
 * 红黑树能自平衡，它靠的是什么？三种操作：左旋、右旋和变色。
 * 红黑树总是通过旋转和变色达到自平衡。
 * */
export default class RedBlackTree extends BinarySearchTree {
  /**
   * @param {*} value
   * @return {BinarySearchTreeNode}
   */
  insert(value) {
    const insertedNode = super.insert(value);

    if (this.nodeValueComparator.equal(this.root, insertedNode)) {
      this.makeNodeBlack(insertedNode);
    } else {
      this.makeNodeRed(insertedNode);
    }

    this.balance(insertedNode);

    return insertedNode;
  }

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

  /**
   * @param {BinarySearchTreeNode} node
   * 1. 插入空树，不调整；
   * 2. 插入结点的父结点为黑色，不调整；
   * 3. 叔叔存在且为红色，变色;
   * 4. 如果叔叔不存在或叔叔为黑色，旋转。
   */
  balance(node) {
    // 1. 插入空树，不调整
    if (this.nodeValueComparator.equal(node, this.root)) {
      return;
    }

    // 2. 插入结点的父结点为黑色，不调整。
    if (this.isNodeBlack(node.parent)) {
      return;
    }

    const grandParent = node.parent.parent;     

    if (node.uncle && this.isNodeRed(node.uncle)) {
      // 3. 叔叔存在且为红色，变色;
      this.makeNodeBlack(node.uncle);
      this.makeNodeBlack(node.parent);

      if (this.nodeValueComparator.equal(grandParent, this.root)) {
        // 如果祖父是根节点，啥也不干
        return;
      }

      this.makeNodeRed(grandParent);
      this.balance(grandParent); // 递归
    } else if (!node.uncle || this.isNodeBlack(node.uncle)) {
      // 4. 如果叔叔不存在或叔叔为黑色，旋转。
      if (!grandParent) {
        // 如果没有祖父，啥也不干
        return; 
      }

      let newGrandParent; // 旋转之后的新祖父
      if (this.nodeValueComparator.equal(grandParent.left, node.parent)) {
        // 左旋
        if (this.nodeValueComparator.equal(node.parent.left, node)) {
          // 左左旋
          newGrandParent = this.leftLeftRotation(grandParent)
        } else {
          // 左右旋
          newGrandParent = this.leftRightRotation(grandParent)
        }
      } else {
        // 右旋
        if (this.nodeValueComparator.equal(node.parent.right, node)) {
          // 左左旋
          newGrandParent = this.rightRightRotation(grandParent)
        } else {
          // 左右旋
          newGrandParent = this.rightLeftRotation(grandParent)
        }
      }

      this.balance(newGrandParent); // 递归
    }
  }

  /**
   * Left Left Case
   * @param {BinarySearchTreeNode|BinaryTreeNode} grandParentNode
   * @return {BinarySearchTreeNode}
   */
  leftLeftRotation(grandParentNode) {
    // detach parentNode from grandParentNode
    const parentNode = grandParentNode.left;
    grandParentNode.setLeft(null);

    if (grandParentNode.parent) {
      grandParentNode.parent.replaceChild(grandParentNode, parentNode);
    } else {
      this.root = parentNode;
      parentNode.parent = null;
    }

    // Move parent's right subtree to grandParentNode's left subtree.
    if (parentNode.right) {
      grandParentNode.setLeft(parentNode.right);
    }

    parentNode.setRight(grandParentNode);

    this.makeNodeRed(grandParentNode);
    this.makeNodeBlack(parentNode);

    return parentNode;
  }

  leftRightRotation(grandParentNode) {
    // detach parentNode from grandParentNode
    const parentNode = grandParentNode.left;
    grandParentNode.setLeft(null);
    // detach node from parentNode
    const childNode = parentNode.right;
    parentNode.setRight(null);

    // Move child's left subtree to parent's right subtree.
    if (childNode.left) {
      parentNode.setRight(childNode.left);
    }

    childNode.setLeft(parentNode);
    grandParentNode.setLeft(childNode);

    return this.leftLeftRotation(grandParentNode);
  }

  /**
   * Right Right Case
   * @param {BinarySearchTreeNode|BinaryTreeNode} grandParentNode
   * @return {BinarySearchTreeNode}
   */
  rightRightRotation(grandParentNode) {
    // detach parentNode from grandParentNode
    const parentNode = grandParentNode.right;
    grandParentNode.setRight(null);

    if (grandParentNode.parent) {
      grandParentNode.parent.replaceChild(grandParentNode, parentNode);
    } else {
      this.root = parentNode;
      parentNode.parent = null;
    }

    // Move parent's right subtree to grandParentNode's left subtree.
    if (parentNode.left) {
      grandParentNode.setRight(parentNode.left);
    }

    parentNode.setLeft(grandParentNode);

    this.makeNodeRed(grandParentNode);
    this.makeNodeBlack(parentNode);

    return parentNode;
  }

  rightLeftRotation(grandParentNode) {
    // detach parentNode from grandParentNode
    const parentNode = grandParentNode.right;
    grandParentNode.setRight(null);
    // detach left child from parent
    const childNode = parentNode.left;
    parentNode.setLeft(null);

    // 移动孩子的右子树为父亲的左子树
    if (childNode.right) {
      parentNode.setLeft(childNode.right);
    }

    childNode.setRight(parentNode);
    grandParentNode.setRight(childNode);

    return this.rightRightRotation(grandParentNode);
  }

  makeNodeRed(node) {
    node.meta.set(COLOR_PROP_NAME, RED_BLACK_TREE_COLORS.red);

    return node;
  }

  makeNodeBlack(node) {
    node.meta.set(COLOR_PROP_NAME, RED_BLACK_TREE_COLORS.black);

    return node;
  }

  isNodeRed(node) {
    return node.meta.get(COLOR_PROP_NAME) === RED_BLACK_TREE_COLORS.red;
  }

  isNodeBlack(node) {
    return node.meta.get(COLOR_PROP_NAME) === RED_BLACK_TREE_COLORS.black;
  }
}