二叉查找树（Binary Search Trees，BST）数据结构详解

一、二叉查找树（BST）的简介

在之前的博客中，我们已经介绍了二叉树这种数据结构。二叉树的应用很广泛，也有很多变种，这里介绍的是二叉查找树（Binary Search Tree,BST）。二叉查找树是一种特殊的二叉树结构，它改善了二叉树的查找效率，二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为 O(\log n)。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、多重集、关联数组等。

简单来说，二叉查找树是一种二叉树，但是它规定了一种顺序，使得其查找、插入的效率更高。其特点如下：
对于任意一个节点 n，其左子树（left subtree）下的每个后代节点（descendant node）的值都小于节点 n 的值；
其右子树（right subtree）下的每个后代节点的值都大于节点 n 的值。

如下图所示，是一个二叉查找树的例子：

根据维基百科的定义，在计算机科学中，二叉查找树（BST），有时称为有序二叉树，是特定类型的容器：在内存中存储“项目”（例如数字，名称等）的数据结构。它们允许快速查找，添加和删除项目，并且可以用于实现动态项目集，或者允许通过其密钥查找项目的查找表格（例如，通过名称查找人员的电话号码）。

二、二叉查找树（BST）的复杂度

二叉查找树将其键保持在排序顺序中，以便查找和其他操作可以使用二叉搜索的原则：当在树中查找键（或插入新键的位置）时，它们从树的根节点开始遍历直到叶子节点，与存储在树的节点中的密钥进行比较，并在比较的基础上决定继续在左或右子树中搜索。平均而言，这意味着每次比较都允许操作跳过大约一半的树，因此每次查找，插入或删除都需要与树中存储的项目数的对数成比例的时间。这比在（未排序的）数组中按键查找项目所需的线性时间要好得多，但比哈希表上的相应操作要慢。

二叉查找树的插入和查找复杂度都是O(\log n)，但是当树不平衡的时候，它的复杂度最坏可以是O(n)。

三、二叉查找树（BST）的操作

树的操作主要分成三种，即查找、插入和删除操作。

3.1、二叉树的查找过程

二叉查找树的过程从根节点开始，如果树为空则返回null，表示没有找到。

将根节点的键值和待查值比较，如果节点值较大，则在树的左子树中进行，如果节点值较小，则在右子树继续查找，如果相等，则返回节点的位置。

3.2、二叉树的插入过程

插入过程也类似，从根节点开始，如果树为空，则将当前元素作为根节点。

如果待插入元素小于根节点，则将元素插入左子树中，如果大于根节点的值，则插入右子树中。

3.3、二叉树的删除过程

删除的结点为X，这里删除较为复杂分为三种情况

如果待删除的结点为叶子结点，此时可直接删除。

如果待删除的结点只有一个孩子结点，左孩子或者右孩子。

如果待删除的结点既有左孩子又有右孩子，这种情况最为复杂；一般思路，用待删除结点右子树中的键值最小的结点替代要删除的结点键值，然后删除右子树中键值最小的结点。注意，右子树最小的结点一定不含左子树，所以删除的这个键值最小的结点一定是叶子结点或者只有右子树的结点。

四、二叉查找树（BST）的Java实现

定义一个二叉查找树需要定义两个类，一个是二叉查找树本身的类，还要定义一个树的节点类，因为查找和插入都是针对节点进行的。

package com.huawei.machinelearning.data.structure;
/**
 * Binary Search Tree Implementation
 * Created by d00454735 on 2018/10/25.
 */
// 定义二叉查找树
public class BST {
  private BSTNode root;
  public static void main(String[] args) {
    BST tree = new BST();
    tree.put("f", "eff");
    tree.put("c", "sea");
    tree.put("a", "aye");
    tree.put("e", "eee");
    tree.put("i", "eye");
    tree.put("h", "aitch");
    tree.put("z", "zed");
    Object str = tree.get("i");
    System.out.println("before updated:" + str);
    tree.put("i", "eye updated");
    str = tree.get("i");
    System.out.println("after updated:" + str);
  }
  // 插入操作
  public void put(String key, Object value) {
    if (root == null) {
      root = new BSTNode(key, value);
    } else {
      root.put(key, value);
    }
  }
  // 查找操作
  public Object get(String key) {
    return root == null ? null : root.get(key);
  }
}
// 定义查找树的节点
class BSTNode {
  private String key;       // 节点的键
  private Object value;     // 节点的值
  private BSTNode left, right;    // 左子节点和右子节点
  // 构造方法，定义一个节点的时候要给出节点的键和值
  public BSTNode(String key, Object value) {
    this.key = key;
    this.value = value;
  }
  // 插入操作
  public void put(String key, Object value) {
    if (key.compareTo(this.key) < 0) {
      if (left != null) {
        left.put(key, value);
      } else {
        left = new BSTNode(key, value);
      }
    } else if (key.compareTo(this.key) > 0) {
      if (right != null) {
        right.put(key, value);
      } else {
        right = new BSTNode(key, value);
      }
    } else {
      //update this one
      this.value = value;
    }
  }
  // 查找操作
  public Object get(String key) {
    if (this.key.equals(key)) {
      return value;
    }
    if (key.compareTo(this.key) < 0) {
      return left == null ? null : left.get(key);
    } else {
      return right == null ? null : right.get(key);
    }
  }
}