第 2 节 二分搜索树（Binary Search Tree）

• 实现查找表，可以通过“普通数组”、“顺序数组”、“二分搜索树”来实现。其中，最有效的方式就是实现二分搜索树。这是因为：

BST 是一种能够将链表插入的灵活性和有序数组查找的高效性结合起来的数据结构。

BST 的定义如下：

一棵二叉搜索树（BST）首先是一棵二叉树，其中每个结点都含有一个可以比较的键（对于 Java 语言来说，就是实现了 Comparable 接口的对象）以及相关联的值，且每个结点的键都大于其左子树中的任意结点的键而小于右子树中任意结点的键。

理解 BST 的定义是理解关于 BST 操作的基础。

• 二分搜索树很适合用于实现“查找表”或者“字典”这种数据结构。
• 二分搜索树不一定是一棵完全二叉树。
• 以左右孩子为根的子树仍为二分搜索树；任一结点的键大于左子树中的所有结点的键，小于右子树中的所有结点的键；
• 我个人认为：理解二分搜索树的性质，应该通过二分搜索树的定义，以及接下来我们对二分搜索树的一些操作，看看我们对二分搜索树中的数据进行"增删改查"的时候，是如何去维护"二分搜索树"的性质的。
• 我一开始在学习"二分搜索树"的时候，有一些混淆的概念如下：

1、"二分搜索树"首先是"二叉树"，有了"搜索"两个字，对结点的键值就有要求了，这个结点的键值要可比较，并且还要按照符合二分搜索树的性质来组织结构，在做 LeetCode 上的问题的时候，一定要看清楚题目中给出的条件包不包含"搜索"两个字； 2、"二分搜索树"和"堆"："最大堆"只要求父结点不小于子结点就可以了，但是"二分搜索树"就完全不一样了；另外，"堆"可以用数组来表示，因为"堆"是"完全二叉树"，而"二分搜索树"是动态的树形结构，这是由它们的性质决定的，"堆"的操作其实比 BST 少（"堆"有自己适用的场合），BST 能够帮助我们完成很多事情。

初始化 BST：

public class BST {

    // 使用内部类来表示结点
    private class Node {

        // 为了说明算法，我们将 key 设置成易于比较的 int 类型，设计成实现了 Comparable 接口的对象是更标准的做法
        private int key;
        private int value;
        private Node left;
        private Node right;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
            this.left = null;
            this.right = null;
        }

    }

    // 节根点
    private Node root;

    // 二分搜索树中的结点个数
    private int count;

    // 默认构造一棵空的二分搜索树
    public BST() {
        root = null;
        count = 0;
    }

    // 返回二分搜索树的结点个数
    public int size() {
        return count;
    }

    // 返回二分搜索树是否为空
    public boolean isEmpty() {
        return count == 0;
    }
}

查阅资料，如何借助二分搜索树实现以下函数：min、max、floor、ceil、rank、select。二分搜索树还可以回答很多数据之间的关系的问题。

---

作者：liweiwei1419 链接：https://suanfa8.com/binary-search-tree/introduction 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。