二叉搜索树的各项基本操作

此文的前置算法知识

• 链表与数组
• 递归
• 二叉树

什么是二叉搜索树

在讲二叉搜索树的特性之前，我们先来看看几个二叉树的基本概念：

• 子树（subtree）：想必学过二叉树的都会非常熟悉根结点（root）这个概念，但是比根节点更为重要的是子树（subtree）的概念。通常我们会说任意一个二叉树节点都有可能有 0 ～ 2 个节点，这两个节点分别是左节点（left node）和右节点（right node），这样的说法会让你失去对整体的意识，从而在递归实现的时候出现思维上的麻烦。更好一点的方式是 把左右节点替换成左右子树，既然是树，那么也就有根节点，也就有着和当前主树一样的性质，在当前主树上用的任何操作也能够原封不动地作用在子树上以达到相同的效果，从而递归就很完美地运用到了树的遍历和各项操作上。理解了子树的概念，也就很自然地看懂了树上的递归
• 高（height）：任意节点的高是其到叶子节点的 最长 距离。叶子节点的高是 0，除了叶子节点本身，任意节点都有可能到达多个叶子节点，因此也就有多条路径，其中最长的那条就是该节点 高（height）。一棵树的高就是该树的根节点的高。
• 深度（depth）：和高相反，表示的是节点到根节点的距离。根节点的深度是 0，因为任意节点都有唯一一条到根节点的路径（反之亦然），因此任意节点就有唯一确定的深度

懂了上面这些东西，我们再回过头来看二叉搜索树。从名称来看，二叉搜索树比二叉树多了个 “搜索” 二字，想必它的特性也跟搜索相关。没错，二叉搜索树能够让你在接近 O(logN) 的时间里进行查找操作。那它是如何做到的呢？

二叉搜索树的定义是，根节点（或任意节点）的左子树中的所有节点上的元素值均小于该节点上的元素值，右子树中所有节点上的元素值均大于该节点上的元素。从这个定义我们不难看出，二叉搜索树的结构是由它上面存放的元素的值来决定的，而其上的搜索也是通过比较元素的值的大小来实现的

基本操作

查找

当我们在一个树上查找某个元素或是判断某个元素是否存在时，我们可以从上到下对这棵树进行遍历，但是和普通的二叉树遍历不同的是，我们可以通过要找的元素的值的大小来决定遍历的走向。如果要找的元素值比当前节点上的元素值大，那么我就可以排除左子树，只在右子树上继续寻找；如果要找的元素值比当前节点上的元素值小，那么我就可以排除右子树，只在左子树上继续寻找。这样子的思想其实非常类似于 二分查找，只是这里的左右子树中的节点数量并不一定相等。于是我们可以得到下面的代码：

private boolean contains(AnyType x, BinaryNode<AnyType> t) {
  if (t == null) {
    return false;
  }

  int compareResult = x.compareTo(t.element)
  
  // 如果当前要找的元素值比当前节点小，则在当前节点的左子树中继续寻找
  if (compareResult < 0) {
    return contains(x, t.left); 
  }
  // 如果当前要找的元素值比当前节点大，则在当前节点的右子树中继续寻找
  else if (compareResult > 0) {
    return contains(x, t.right);
  }

  // 当前节点上的元素值就是要找的元素值，返回 true
  return true;
}

你可能已经发现了，这个算法的时间复杂度其实是和树的深度相关的。一般情况下来，深度是远远小于一个树上的节点的，如果说是平衡二叉树，那么其深度会是 log(N) 其中 N 是节点的总数。关于平衡二叉树，我们后面会有专门的文章对其进行阐述

插入

如果你把二叉搜索树看做是一个存储结构，那么这个结构势必就会有插入和删除的功能。如果不考虑树的平衡性，那么插入其实只需要先查找，如果该元素不存在，上面的查找算法会遍历到一个空的节点，那么这个节点就是我们需要插入的位置，所以插入只需要在查找的基础上做个修改即可：

private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t) {
  if (t == null) {
    return new BinaryNode<>(x, null, null);
  }

  int compareResult = x.compareTo(t.element);

  if (compareResult < 0) {
    t.left = insert(x, t.left);
  } else if (compareResult > 0) {
    t.right = insert(x, t.right);
  }

  return t;
}

时间复杂度和查找时的一样。但是因为我们可能插入一个新的树节点，树的结构可能会发生改变，因而我们需要对树的信息进行更新

查找最值

很多时候，我们都需要知道一个数据结构中存储的最大最小值。由于二叉搜索树的结构，这再明显不过了，最左边的节点上存放的是最小的元素，最右边的节点上存放的是最小的元素。只需简单的判断加遍历即可

private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t) {
  if (t != null)
    while (t.left != null)
      t = t.left;

  return t;
}

private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t) {
  if (t != null)
    while (t.right != null)
      t = t.right;

  return t;
}

删除

这一项操作可能是所有基本操作中最难的，难点在于我们不但需要把节点删除，还需要维持搜索树的结构。这里我们可以根据要删除的节点的子树情况，分情况考虑：

• 如果要删除的节点是叶子节点，这种情况最为简单，直接删除即可
• 如果要删除的节点有一颗子树，那么可以把该节点删除，然后把该子树的根节点移至被删除的节点的位置。这里实现起来只需要改变被删除的节点的父节点的指向即可
• 最难的可能就是 当删除节点有两颗子树 的情况。如果不考虑树的平衡性，我们其实可以通过替换的方式来实现。比如在右子树中找到最小的节点，然后将被删除节点上的值替换为该节点的值，并将该节点在右子树中删除，由于二叉搜索树的特性，这个节点只会有 0 ～ 1 个子树，因此按照上面的两种情况删除即可。在左子树中找最大的节点也是同理

private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t) {
  if (t == null) {
    return null;
  }

  int compareResult = x.compareTo(t.element);

  if (compareResult < 0) {
    t.left = remove(x, t.left);
  } else if (compareResult > 0) {
    t.right = remove(x, t.right);
  }

  // 被删除的节点有两个子树
  if (t.left != null && t.right != null) {
    // 在右子树中找到最小的节点，并将其元素值覆盖到被删除的节点上
    t.element = findMin(t.right).element;
    // 将右子树的最小节点删除
    t.right = remove(t.element, t.right);
  }
  // 被删除的节点有 1 个或没有子树
  else {
    t = (t.left != null) ? t.left : t.right;
  }

  return t;
}

总结

二叉搜索树的特性决定了它的使用方式，可以看到，它的任意操作时间复杂度均为 O(logN)。当然，这个复杂度是基于二叉搜索树是平衡的这么一个假设。上面的操作实现其实都是最为简单的，我们并没有考虑去维持二叉搜索树的平衡性，因为这并不是简简单单几行代码就能实现的，维持平衡需要其他的算法辅助。但是，通过观察，我们也可以知道，上面的所有操作中只有插入和删除两个操作会对二叉搜索树的平衡性产生影响，而二叉搜素树的结构也是会由插入或删除的元素的值以及先后次序来决定，极端情况下，二叉搜索树会变成一个类似链表的结构，这样任意操作的时间复杂度会退回 O(N)，也就是常规二叉树的操作复杂度