二叉搜索树¶

import Comparator from '../utils/Comparator.js';
import HashTable from '../hash-table/HashTable.js';

export default class BinaryTreeNode {
  constructor(value = null) {
    this.left = null;
    this.right = null;
    this.parent = null;
    this.value = value;

    this.nodeComparator = new Comparator();

    this.meta = new HashTable();
  }

  /**
   * 左视高
   * @return {number}
   */
  get leftHeight() {
    if (!this.left) {
      return 0;
    }

    return this.left.height + 1;
  }

  /**
   * 右视高
   * @return {number}
   */
  get rightHeight() {
    if (!this.right) {
      return 0;
    }

    return this.right.height + 1;
  }

  /**
   * @return {number}
   */
  get height() {
    return Math.max(this.leftHeight, this.rightHeight);
  }

  /**
   * 平衡因子： 某个结点的左子树的高度减去右子树的高度得到的差值。
   * in AVL Tree
   * @return {number}
   */
  get balanceFactor() {
    return this.leftHeight - this.rightHeight;
  }

  /**
   * Get parent's sibling if it exists.
   * @return {BinaryTreeNode}
   */
  get uncle() {
    if (!this.parent) {
      return null;
    }

    if (!this.parent.parent) {
      return null;
    }

    if (this.nodeComparator.equal(this.parent.parent.left, this.parent)) {
      return this.parent.parent.right;
    }

    if (this.nodeComparator.equal(this.parent.parent.right, this.parent)) {
      return this.parent.parent.left;
    }
  }

  /**
   * @param {BinaryTreeNode} sourceNode
   * @param {BinaryTreeNode} targetNode
   */
   static copyNode(sourceNode, targetNode) {
    targetNode.value = sourceNode.value;
    targetNode.setLeft(sourceNode.left);
    targetNode.setRight(sourceNode.right);
  }

  setLeft(node) {
    // Reset parent for left node since it is going to be detached.
    if (this.left) {
      this.left.parent = null;
    }

    // Attach new node to the left.
    this.left = node;

    // Make current node to be a parent for new left one.
    if (this.left) {
      this.left.parent = this;
    }

    return this;
  }

  setRight(node) {
    if (this.right) {
      this.right.parent = null;
    }

    this.right = node;

    if (this.right) {
      this.right.parent = this;
    }

    return this;
  }

  /**
   * @param {BinaryTreeNode} nodeToRemove
   * @return {boolean}
   */
  removeChild(nodeToRemove) {
    if (this.left && this.nodeComparator.equal(this.left, nodeToRemove)) {
      this.left = null;
      nodeToRemove.parent = null;
      return true;
    }

    if (this.right && this.nodeComparator.equal(this.right, nodeToRemove)) {
      this.right = null;
      nodeToRemove.parent = null;
      return true;
    }

    return false;
  }

  /**
   * @param {BinaryTreeNode} nodeToReplace
   * @param {BinaryTreeNode} replacementNode
   * @return {boolean}
   */
  replaceChild(nodeToReplace, replacementNode) {
    if (!nodeToReplace || !replacementNode) {
      return false;
    }

    if (this.left && this.nodeComparator.equal(this.left, nodeToReplace)) {
      this.left = replacementNode;
      replacementNode.parent = this;
      nodeToReplace.parent = null;
      return true;
    }

    if (this.right && this.nodeComparator.equal(this.right, nodeToReplace)) {
      this.right = replacementNode;
      replacementNode.parent = this;
      nodeToReplace.parent = null;
      return true;
    }

    return false;
  }

  /**
   * 中序遍历（inorder）
   * 即 left -> root -> right
   * @return {*[]}
   */
  traverseInOrder() {
    let traverse = [];

    // 左
    if (this.left) {
      traverse = traverse.concat(this.left.traverseInOrder());
    }

    // 中
    traverse.push(this.value);

    // 右
    if (this.right) {
      traverse = traverse.concat(this.right.traverseInOrder());
    }

    return traverse;
  }

  /**
   * 先序遍历（preorder)
   * 即 root -> left -> right
   * @return {*[]}
   */
  traversePreOrder() {}

  /**
   * 后序遍历（postorder)
   * 即 left -> right -> root
   * @return {*[]}
   */
  traversePostOrder() {}

  toString() {
    return this.traverseInOrder().toString();
  }
}

import BinaryTreeNode from '../BinaryTreeNode.js';
import Comparator from '../../utils/Comparator.js';

export default class BinarySearchTreeNode extends BinaryTreeNode {
  constructor(value = null, compareFunction = undefined) {
    super(value);

    // This comparator is used to compare node values with each other.
    this.compareFunction = compareFunction;
    this.nodeValueComparator = new Comparator(compareFunction);
  }

  /**
   * @param {*} value
   * @return {BinarySearchTreeNode}
   */
  insert(value) {
    if (this.nodeValueComparator.equal(this.value, null)) {
      // Insert root node
      this.value = value;
      return this;
    }

    if (this.nodeValueComparator.lessThan(value, this.value)) {
       // Insert to the left.
      if (this.left) {
        return this.left.insert(value);
      } 

      const newNode = new BinarySearchTreeNode(value, this.compareFunction);
      this.setLeft(newNode);

      return newNode;
    }

    if (this.nodeValueComparator.greaterThan(value, this.value)) {
      // Insert to the right.
      if (this.right) {
        return this.right.insert(value);
      }

      const newNode = new BinarySearchTreeNode(value, this.compareFunction);
      this.setRight(newNode);

      return newNode;
    }
  }

  /**
   * @param {*} value
   * @return {BinarySearchTreeNode}
   */
  find(value) {
    if (this.nodeValueComparator.equal(value, this.value)) {
      return this;
    }

    if (this.nodeValueComparator.lessThan(value, this.value) &&  this.left) {
      return this.left.find(value);
    }

    if (this.nodeValueComparator.greaterThan(value, this.value) &&  this.right) {
      return this.right.find(value)
    }

    return null;
  }

  /**
   * @param {*} value
   * @return {boolean}
   */
  contains(value) {
    return !!this.find(value);
  }

  /**
   * 1. 若为叶节点，即无孩子，其父指向它的指针设为 null；
   * 2. 若一个孩子，其父指向它的指针改指向其孩子；
   * 3. 若俩孩子，首先，要么找到其左子树的最大值，要么找到其右子树的最小值。
   * 本文采用后者，后续步骤转到4；
   * 4. 将该节点值替换为最小值，`递归地删除`右子树中最小值节点。
   * 
   * @param {*} value
   * @return {boolean}
   */
  remove(value) {
    const nodeToRemove = this.find(value);

    if (!nodeToRemove) {
      throw new Error('找不到节点 In the tree');
    }

    const { parent } = nodeToRemove;

    if (!nodeToRemove.left && !nodeToRemove.right) {
      // 1. 无孩子：Node is leaf & has no child
      if (parent) {
        parent.removeChild(nodeToRemove);
      } else {
        nodeToRemove.value = undefined;
      }
      return true;
    } else if (!nodeToRemove.left || !nodeToRemove.right) {
      // 2. 只有一个：孩子Node has only one child
      const childNode = nodeToRemove.left || nodeToRemove.right;
      if (parent) {
        parent.replaceChild(nodeToRemove, childNode);
      } else {
        BinaryTreeNode.copyNode(childNode, nodeToRemove);  // 根节点
      }
    } else {
      // 3. 有两个孩子：Node has two children
      const nextBiggerNode = nodeToRemove.right.findMin();

      if (this.nodeComparator.equal(nextBiggerNode, nodeToRemove.right)) {
        nodeToRemove.value = nodeToRemove.right.value;
        nodeToRemove.setRight(nodeToRemove.right.right);
      } else {
        // 这里递归
        this.remove(nextBiggerNode.value);
        nodeToRemove.value = nextBiggerNode.value;
      }
    }

    nodeToRemove.parent = null;

    return true;
  }

  /**
   * @return {BinarySearchTreeNode}
   */
  findMin() {
    if (!this.left) {
      return this;
    }

    return this.left.findMin();
  }
}

import BinarySearchTreeNode from './BinarySearchTreeNode.js';

/**
 * 二叉查找树（BST）
 * “A binary search tree is a binary tree in 
 * which data with lesser values are stored in left nodes 
 * and data with greater values are stored in right nodes.”
 */
export default class BinarySearchTree {
  constructor(nodeValueCompareFunction) {
    this.root = new BinarySearchTreeNode(null, nodeValueCompareFunction);
    this.nodeValueComparator = this.root.nodeValueComparator;
  }

  insert(value) {
    return this.root.insert(value);
  }

  remove(value) {
    return this.root.remove(value);
  }

  toString() {
    return this.root.toString();
  }

  /**
   * Traverse by level
   * @param {BinarySearchTreeNode} node
   * @param {Function} visit
   * @return {*[]}
   */
  bfs(node, visit) {
    const queue = [];
    queue.push(node);

    while(queue.length) {
      const head = queue.shift();
      visit && visit(head);

      if (head.left) {
        queue.push(head.left);
      }

      if (head.right) {
        queue.push(head.right);
      }
    }
  }

  print() {
    this.bfs(this.root, node => {
      if (node.height > 0) {
        const nodeVal = `${node.value}(${node.meta.get('color')})`;
        const leftVal = node.left
          ? `${node.left.value}(${node.left.meta.get('color')})`
          : 'NIL';
        const rightVal = node.right
          ? `${node.right.value}(${node.right.meta.get('color')})`
          : 'NIL';

        console.log(`${nodeVal} -> ${leftVal} | ${rightVal}`);
      }
    });
  }
}