二叉搜索树

二叉搜索树（BST）是二叉树的一种，是二叉树中最常用的一种类型。

二叉搜索树是为了实现快速查找而生的，不过它不仅仅支持快速查找一个数据，还支持快速插入、删除一个数据。这些都依赖于二叉查找树的特殊结构。二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

下图为二叉树搜索树的组织形式：

二叉搜索树中的节点通过引用来表示节点之间的关系，每个节点会有两个指针，一个指向左侧的节点，而另一个指向右侧的节点。

二叉搜索树的节点

下面创建一个类来表示二叉搜索树中的节点：

class Node<K> {
  key: K;
  left: Node<K> | null;
  right: Node<K> | null;
  constructor(key: K) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

二叉搜索树的实现

接口

下面的接口定义，表示二叉搜索树这个类需要实现的方法：

interface BSTInterface<T> {
  /** 向树中插入一个新键 */
  insert: (key: T) => void;

  /** 通过前序遍历方式遍历所有节点 */
  preOrderTraverse: (callback: Callback<T>) => void;
  /** 通过中序遍历方式遍历所有节点 */
  inOrderTraverse: (callback: Callback<T>) => void;
  /** 通过后序遍历方式遍历所有节点 */
  postOrderTraverse: (callback: Callback<T>) => void;
  /** 广度优先遍历 */
  levelOrder: (callback: Callback<T>) => void;

  /** 查找一个键 */
  search: (key: T) => boolean;
  /** 返回树中最小的键 */
  min: () => Node<T> | null;
  /** 返回树中最大的键 */
  max: () => Node<T> | null;

  /** 从树中删除某个键 */
  remove: (key: T) => void;
  /** 删除树中的最小键 */
  removeMin: (key: T) => Node<T> | null;
  /** 删除树中的最大键 */
  removeMax: (key: T) => Node<T> | null;

  /** 二叉搜索树是否为空 */
  isEmpty: () => boolean;
}

创建二叉搜索树类

interface Callback<T> {
  (key: T): void;
}

interface ICompareFunction<T> {
  (a: T, b: T): number;
}

enum Compare {
  LESS_THAN = -1,
  BIGGER_THAN = 1,
  EQUALS = 0,
}

function defaultCompare<T>(a: T, b: T): number {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}


class BST<T> implements BSTInterface<T> {
  protected _root: Node<T> | null = null;
  protected compareFunction: ICompareFunction<T>;
  protected _size = 0;

  constructor(compareFucnton: ICompareFunction<T> = defaultCompare) {
    this.compareFunction = compareFucnton;
  }
}

二叉搜索树的节点是可以存储任意的数据结构的，所以使用简单的比较运算符是无法比较两个节点的大小的。要让二叉搜索树可以得知两个节点谁大谁小，就需要借助可以比较这两个节点的比较函数，也就是上面代码中的 compareFunction 。这个属性会赋值一个默认的比较方法。

_root 表示二叉搜索树的根节点，而 _size 表示二叉搜索树中有多少个节点。

插入元素

插入元素的动画可以查看 https://algorithm-visualizer.org/branch-and-bound/binary-search-tree 。

插入元素的过程：

1. 如果当前二叉树为空，则元素赋值给 _root 属性。
2. 如果当前二叉树不为空，则元素先于根节点比较。如果比根节点小，则与根节点左侧子节点比较。如果比根节点大，则与根节点右侧子节点比较。无论是与左侧子节点比较还是与右侧子节点比较，一旦碰到子节点为 null 的情况，就可以通过元素来创建一个新的节点插入到该位置中。

class BST<T> implements BSTInterface<T> { 

  ...

    /**
   * 向二分搜索树中添加新的元素，如果元素重复，则数不会发生任何变化
   * @param key 新元素
   */
  insert(key: T): void {
    this._root = this._insertNode(this._root, key);
  }

  /**
   * 向以 node 为根的二分搜索树中插入节点 key，递归算法
   * @param node 
   * @param element
   */
  private _insertNode(node: Node<T> | null, key: T): Node<T> {
    if (node === null) {
      this._size++;
      return new Node(key);
    }

    const result = this.compareFunction(key, node.key);

    if (result === Compare.LESS_THAN) {
      node.left = this._insertNode(node.left, key);
    } else if (result === Compare.BIGGER_THAN) {
      node.right = this._insertNode(node.right, key);
    }

    return node;
  }
}

前序遍历

前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。

class BST<T> implements BSTInterface<T> { 

  ...

  /**
   * 前序遍历
   * @param callback
   */
  preOrderTraverse(callback: Callback<T>): void {
    this._preOrderTraverseNode(this._root, callback);
  }

  /**
   * 以 node 为根节点进行前序遍历
   * @param node
   * @param callback
   */
  private _preOrderTraverseNode(node: Node<T> | null, callback: Callback<T>) {
    if (node !== null) {
      callback(node.key);
      this._preOrderTraverseNode(node.left, callback);
      this._preOrderTraverseNode(node.right, callback);
    }
  }
}

中序遍历

中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。

class BST<T> implements BSTInterface<T> { 

  ...

  /**
   * 中序遍历
   * @param callback
   */
  inOrderTraverse(callback: Callback<T>): void {
    this._inOrderTraverseNode(this._root, callback);
  }

  /**
   * 以 node 为根节点进行中序遍历
   * @param node
   * @param callback
   */
  private _inOrderTraverseNode(node: Node<T> | null, callback: Callback<T>) {
    if (node !== null) {
      this._inOrderTraverseNode(node.left, callback);
      callback(node.key);
      this._inOrderTraverseNode(node.right, callback);
    }
  }
}

后序遍历

后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身

class BST<T> implements BSTInterface<T> { 

  ...


    /**
   * 后序遍历
   * @param callback
   */
  postOrderTraverse(callback: Callback<T>): void {
    this._postOrderTraverseNode(this._root, callback);
  }

  /**
   * 以 node 为根节点进行后序遍历
   * @param node
   * @param callback
   */
  private _postOrderTraverseNode(node: Node<T> | null, callback: Callback<T>) {
    if (node !== null) {
      this._postOrderTraverseNode(node.left, callback);
      this._postOrderTraverseNode(node.right, callback);
      callback(node.key);
    }
  }
}

广度优先遍历

广度优先遍历的意思是遍历的顺序是从二叉树的第零层开始遍历，随后是第一层、第二层，如此类推。

下面的逻辑中借用到队列这种数据结构。在遍历第零层的时候，如果存在左右子节点，则将左右子节点入队。在遍历第一层的时候，同样是重复之前的操作。

class BST<T> implements BSTInterface<T> { 

  ...

  levelOrder(callback: Callback<T>): void {
    if (!this._root) {
      return;
    }

    const queue = new ArrayQueue<Node<T>>();
    queue.enqueue(this._root);

    while (!queue.isEmpty()) {
      const node = queue.dequeue() as Node<T>;

      callback(node.key);

      if (node.left) {
        queue.enqueue(node.left);
      }

      if (node.right) {
        queue.enqueue(node.right);
      }
    }
  }
}

上面的逻辑中用到了 ArrayQueue，它的实现如下：

interface QueueInterface<T> {
  enqueue: (element: T) => void;
  dequeue: () => T | undefined;
  getFront: () => T | undefined;
  getSize: () => number;
  isEmpty: () => boolean;
}

class ArrayQueue<T> implements QueueInterface<T> {
  private queue: T[] = [];

  getSize(): number {
    return this.queue.length;
  }

  isEmpty(): boolean {
    return this.queue.length === 0;
  }

  enqueue(element: T): void {
    this.queue.push(element);
  }

  dequeue(): T | undefined {
    return this.queue.shift();
  }

  getFront(): T | undefined {
    return this.queue[0];
  }
}

查找元素是否存在于二叉搜索树中

查找元素的动画可以查看 https://visualgo.net/en/bst 。

查找元素的过程：

1. 先取根节点，如果等于要找的数据，则直接返回 true。
2. 如果查找的数据比根节点小，则向左子树进行递归的操作。
3. 如果查找的数据比根节点大，则向右子树进行递归的操作。
   

class BST<T> implements BSTInterface<T> { 

  ...

    /**
   * 查看树中是否包含某个元素
   * @param key
   */
  search(key: T): boolean {
    return this._search(this._root, key);
  }

  /**
   * 查看树中是否包含某个元素（递归方法）
   * @param node
   * @param key
   */
  private _search(node: Node<T> | null, key: T): boolean {
    if (node === null) {
      return false;
    }

    const result = this.compareFunction(key, node.key);

    if (result === Compare.EQUALS) {
      return true;
    } else if (result === Compare.LESS_THAN) {
      return this._search(node.left, key);
    } else {
      return this._search(node.right, key);
    }
  }
}

查找二叉搜索树中的最小节点和最大节点

二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

因此我们一直遍历节点的左子节点就可以找到最小节点，而一直遍历节点的右子节点就可以找到最大节点。

class BST<T> implements BSTInterface<T> { 

  ...

  /**
   * 获取二叉树中的最小键
   */
  min(): Node<T> | null {
    return this._min(this._root);
  }

  /**
   * 查找以 node 为根节点的二叉树的最小键
   * @param node
   */
  private _min(node: Node<T> | null): Node<T> | null {
    let currentNode = node;

    while (currentNode !== null && currentNode.left !== null) {
      currentNode = currentNode.left;
    }

    return currentNode;
  }

  /**
   * 获取二叉树中最大的键
   */
  max(): Node<T> | null {
    return this._max(this._root);
  }

  private _max(node: Node<T> | null): Node<T> | null {
    let currentNode = node;

    while (currentNode !== null && currentNode.right !== null) {
      currentNode = currentNode.right;
    }

    return currentNode;
  }
}

删除指定数据的节点

相比二叉搜索树的插入与查找操作，删除操作要复杂很多。

被删除的节点由三种情况：

1. 该节点为叶子节点，此时只需要将父节点对该叶子节点的引用赋值为 null 即可。
2. 该节点只有一个子节点，此时只需将父节点对该节点的引用更改为对该节点的子节点的引用即可。
3. 该节点有两个节点，此时需要找出该节点的右子树中的最小值，然后其 key 值赋值给该节点的 key，随后删掉右子树中的最小值即可。

export default class BST<T> implements BSTInterface<T> {

    ...

  remove(key: T): void {
    this._root = this._removeNode(this._root, key); // 1
  }

  /**
   * 删除一个数的节点
   * 所删除的节点有三种类型：
   * 1. 该节点为叶子节点
   * 2. 该节点只有一个子节点（一个左侧子节点或者一个右侧子节点）
   * 3. 该节点有两个子节点
   * @param node
   * @param key
   */
  private _removeNode(node: Node<T> | null, key: T): Node<T> | null {
    if (node === null) {
      return null;
    }

    const result = this.compareFunction(key, node.key);

    if (result === Compare.LESS_THAN) {
      // 如果当前
      node.left = this._removeNode(node.left, key);
      return node;
    } else if (result === Compare.BIGGER_THAN) {
      node.right = this._removeNode(node.right, key);
      return node;
    } else {
      this._size--;

      // 第一种情况：处理当前节点为叶子节点的情况：
      if (node.left === null && node.right === null) {
        node = null;
        return node;
      }

      // 第二种情况：处理当前节点仅有一个子节点的情况
      if (node.left === null) {
        // 处理当前节点仅有右子节点的情况
        node = node.right;
        return node;
      } else if (node.right === null) {
        // 处理当前节点仅有左子节点的情况
        node = node.left;
        return node;
      }

      // 第三种情况：处理当前节点有两个子节点的情况

      // 找出当前节点的右子树中最小值，用于替换当前节点
      const aux = this._min(node.right) as Node<T>;
      // 将当前节点的 key 替换为右子树中的最小节点的 key
      node.key = aux.key;
      // 由于当最小节点的 key 赋值给当前节点之后，要将原来的最小值删除
      node.right = this._removeMinNode(node.right);
      return node;
    }
  }
}

删除最小节点

删除最小节点要比删除置顶数据的节点要容易一些，删除最小节点，只需要考虑节点的两种情况：

1. 最小节点为叶子节点，这种情况只需要将最小节点的父节点引用设置为 null 即可。
2. 最小节点存在一个右子节点，那么最小节点的父节点对它的引用，需要改为对它的右子节点的引用。

class BST<T> implements BSTInterface<T> { 

  ...

    removeMin(): Node<T> | null {
    const min = this.min();

    if (min) {
      this._removeMinNode(this._root as Node<T>);
    }

    return min;
  }

  /**
   * 删除以 node 为根的二叉搜索树中的最小节点
   * 返回删除节点后的新的二分搜索树的根
   * @param node
   */
  private _removeMinNode(node: Node<T>): Node<T> | null {
    if (node.left == null) {
      const rightNode = node.right;
      node.right = null;
      this._size--;
      return rightNode;
    } else {
      node.left = this._removeMinNode(node.left);
      return node;
    }
  }
}

删除最大节点

最大节点同样有两种情况：

1. 最大节点为叶子节点，这种情况只需要将父节点对最大节点的引用赋值为 null 即可。
2. 最大节点只有一个左子节点，这种情况只需要将父子节点的引用从指向最大节点改为指向最大节点的左子节点。

class BST<T> implements BSTInterface<T> { 

  ...

    removeMax(): Node<T> | null {
    const max = this.max();

    if (max) {
      this._removeMaxNode(this._root as Node<T>);
    }

    return max;
  }

  private _removeMaxNode(node: Node<T>): Node<T> | null {
    if (node.right === null) {
      const leftNode = node.left;
      node.left = null;
      this._size--;
      return leftNode;
    } else {
      node.right = this._removeMaxNode(node.right);
      return node;
    }
  }
}

参考

• 学习JavaScript数据结构与算法（第3版）—— 第 10 章　树
• 《玩转数据结构》——二分搜索树
• 数据结构与算法之美——24 | 二叉树基础（下）：有了如此高效的散列表，为什么还需要二叉树？