[数据结构与算法]二分搜索树与二分查找法

一：树的基本概念

什么是树？

树（Tree）是一种用来模拟具有树状结构性质的数据集合。它是由 n(n > 0) 个有限节点组成的一个具有层次关系的集合。把它叫做“树”的原因，是因为树这种数据结构看起来像一棵倒挂的树，也就是说，它是根朝上，而叶朝下的。

树这种数据结构具有以下的几个特点：

• 每个节点都只有有限个子节点或无子节点
• 没有父节点的节点称为根节点
• 每一个非根节点有且只有一个父节点
• 除了根节点外，每个子节点可以分为多个不相交的子树
• 树里面有没环路（cycle）

树的名词术语

树这种数据结构中有以下几个常用的名词术语：

• 节点的度：一个节点含有的子树的个数称为该节点的度；
• 树的度：一棵树中，最大的节点度称为树的度；
• 叶节点或终端节点：度为零的节点；
• 非终端节点或分支节点：度不为零的节点；
• 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
• 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
• 兄弟节点：具有相同父节点的节点互称为兄弟节点；
• 节点的层次：从根开始定义起，根为第 1 层，根的子节点为第 2 层，以此类推；
• 深度：对于任意节点 n，n 的深度为从根到 n 的唯一路径长，根的深度为 0，有一些书籍中，定义根的深度为 1；
• 高度：对于任意节点 n，n 的高度为从 n 到一片树叶的最长路径长，所有树叶的高度为 0，有一些书籍中，定义树叶的高度为 1；
• 堂兄弟节点：父节点在同一层的节点互为堂兄弟；
• 节点的祖先：从根到该节点所经分支上的所有节点；
• 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
• 森林：由 m（ m >= 0）棵互不相交的树的集合称为森林；

二叉树、满二叉树、完全二叉树与平衡二叉树

二叉树

二叉树（Binary Tree）是树形结构的一个重要分支，其特点为每个节点最多只能有两个子节点，这两个子节点分别称为左孩子与右孩子。

满二叉树

对于一棵二叉树，它的节点要么是叶子节点，要么有两个子节点。这样的一棵树就称为满二叉树。

满二叉树具有这样的一个性质：如果一棵满二叉树的层数为$K$,那么这棵树的节点总数为$2^K?1$。

完全二叉树

若一棵二叉树的深度为 $K$ ,除了第 $K$ 层外，其他层($1$ ~ $K?1$)的节点数均达到了最大的个数，从第 $K$ 层开始，所有的节点都连续地集中在最左边，这样的一棵树就称为完全二叉树。

平衡二叉树

平衡二叉树的这个概念我们可以先看一遍，在学习二分搜索树之后再回过头加深一下理解。

首先，平衡二叉树必须是一棵二分搜索树。它或者是一颗空树，或它的左子树与右子树的高度之差（平衡因子：balance factor）的绝对值不超过 1，且它的左右子树都是一棵平衡二叉树。

二：二分搜索树

什么是二分搜索树（Binary Search Tree）？

首先，二分搜索树是一棵二叉树，并且二分搜索树有以下的两个特点：

• 二分搜索树的节点存储的元素必须具有可比较性。
• 二分搜索树的每个节点的值都要大于其左子树的所有节点的值，且小于其右子树的所有节点的值。

二分搜索树的节点定义如下：

public class Node<E extends Comparable<E>> {
    public E e;
    public Node left;
    public Node right;

    public Node(E e) {
        this.e = e;
        left = null;
        right = null;
    }
}

因为树这个数据结构本身就具有天然的递归性质，所以一棵二分搜索树的每一棵子树也都是二分搜索树。

二分搜索树的基本操作

二分搜索树的定义中，是不包含重复节点的（节点对应的值相等即认为重复），所以，我实现的二分搜索树遵从了原本二分搜索树的定义，即不会有重复的节点。但是，这仅仅是一个设计的问题，如果你想设计一个可以添加重复元素的二分搜索树也是可以的。

向二分搜索树中添加元素

如果当前二分搜索树的根节点为空，那么新插入的节点就会成为根节点。

如果当前二分搜索树的根节点不为空，就让根作为当前比较的节点：新插入的节点与当前节点进行比较；如果值比当前节点小就要“向左走”，如果值比当前节点大就要“向右走”，然后让下一层的节点继续作为当前比较的节点，直至走到应该插入的位置。

下图为在向当前的二分搜索树中添加节点“28”的流程：

Java 代码：

/**
 * @param e 向二分搜索树中添加新的元素
 */
public void add(E e) {
    root = add(e, root);
}

/**
 * @param e    向二分搜索树中新插入的节点
 * @param node 当前比较的节点
 * @return 返回二分搜索树的根节点
 */
private Node add(E e, Node node) {
    if (node == null) {
        size++;
        return new Node(e);
    }
    if (e.compareTo((E) node.e) < 0) {
        node.left = add(e, node.left);
    } else if (e.compareTo((E) node.e) > 0) {
        node.right = add(e, node.right);
    }
    return node;
}

向二分搜索树中查询元素是否存在

向二分搜索树中查询元素的逻辑和添加元素实际上是一样的，我们还是从根出发，让根节点作为当前比较的节点：如果值和当前的节点相等，那么就说明我们找到了该元素；否则，如果值比当前节点小就要“向左走”，如果值比当前节点大就要“向右走”，递归处理我们的算法逻辑。

如果我们走到了叶子节点，仍然没有找到该元素，那么就说明当前的二叉搜索树中没有该元素。

向二分搜索树中查询一个元素的 Java 代码：

/**
 * @param e 查找的元素 e
 * @return 返回当前二分搜索树中是否包含元素 e
 */
public boolean contains(E e) {
    return contains(e, root);
}

/**
 * @param e    查找的元素 e
 * @param node 当前比较的节点
 * @return 返回当前二分搜索树中是否包含元素 e
 */
private boolean contains(E e, Node node) {
    if (node == null) {
        return false;
    }

    if (e.compareTo((E) node.e) == 0) {
        return true;
    } else {
        if (e.compareTo((E) node.e) < 0) {
            return contains(e, node.left);
        } else {
            return contains(e, node.right);
        }
    }
}

向二分搜索树中删除元素

删除二分搜索树中的最大值和最小值

二分搜索树中最小的元素代表的节点就是沿着根“向左走”，“最左”的那个节点；二分搜索树最大的元素代表的节点就是沿着根“向右走”，“最右”的那个节点。

对于上图所示的二分搜索树，最小元素为 “22”，它就是沿着根“向左走”，“最左”的那个节点；最大元素为 “58”，它就是沿着根“向右走”，“最右”的那个节点。

如果“最左的节点”没有右子树，那么我们只需要删除这个节点即可，无需对整棵二分搜索树做任何调整；如果“最左的节点”有右子树，那么我们就将“最左的节点”的右孩子取代这个节点的位置，如下图所示：

这样，我们就完成了删除二分搜索树中最小的那个节点的操作。

Java 代码如下：

/**
  * @return 返回二分搜索树的最小元素
 */
public E minimum() {
    if (size == 0) {
        throw new RuntimeException("BST is empty");
    }
    return (E) minimum(root).e;
}

/**
 * @param node 返回以 node 为根的二分搜索树的最小值所在的节点
 * @return 返回以 node 为根的二分搜索树的最小值所在的节点
 */
private Node minimum(Node node) {
    if (node.left == null) {
        return node;
    }
    return minimum(node.left);
}
/**
 * @return 从二叉搜索树中删除最小值所在的节点，返回最小值
 */
public E removeMin() {
    E ret = minimum();
    root = removeMin(root);
    return ret;
}

/**
 * @param node 删除掉以 node 为根的二分搜索树中的最小节点
 * @return 返回删除节点后新的二分搜索树的根
 */
private Node removeMin(Node node) {
    if (node.left == null) {
        Node rightNode = node.right;
        node.right = null;
        size--;
        return rightNode;
    }
    node.left = removeMin(node.left);
    return node;
}

相同的，删除二分搜索树中最大的那个节点也是类似的思想。如果“最右的节点”没有左子树，那么我们只需要删除这个节点即可，无需对整棵二分搜索树做任何调整；如果“最右的节点”有左子树，那么我们就将“最右的节点”的左孩子取代这个节点的位置，这样就完成了删除二分搜索树中最大的节点的操作。

Java 代码如下：

/**
 * @return 返回二分搜索树的最大元素
 */
public E maximum() {
    if (size == 0) {
        throw new RuntimeException("BST is empty");
    }
    return (E) maximum(root).e;
}

/**
 * @param node 返回以 node 为根的二分搜索树的最大值所在的节点
 * @return 返回以 node 为根的二分搜索树的最大值所在的节点
 */
private Node maximum(Node node) {
    if (node.right == null) {
        return node;
    }
    return maximum(node.right);
}
/**
 * @return 从二叉搜索树中删除最大值所在的节点，返回最大值
 */
public E removeMax() {
    E ret = maximum();
    root = removeMax(root);
    return ret;
}

/**
 * @param node 删除掉以 node 为根的二分搜索树中的最大节点
 * @return 返回删除节点后新的二分搜索树的根
 */
private Node removeMax(Node node) {
    if (node.right == null) {
        Node leftNode = node.left;
        node.left = null;
        size--;
        return leftNode;
    }
    node.right = removeMax(node.right);
    return node;
}

删除二分搜索树中的任意元素

首先我们思考两种情况：

如果我们删除的节点只有左子树没有右子树

那么我们只需要让删除的节点的左孩子取代删除节点的位置即可。

如果我们删除的节点只有右子树没有左子树

那么我们只需要让删除节点的右孩子取代删除节点的位置即可。

但是，如果我们删除的节点既有左子树也有右子树该怎么办呢？

1962 年，一位计算机科学家 Hibbard 提出了一种算法，叫做 Hibbard Deletion，如果我们要删除一个既有左子树也有右子树的节点，首先需要找到待删除节点的后继节点（successor）。

什么是后继节点呢？我们对二叉树进行中序遍历，按照中序遍历的顺序寻找该节点的下一个节点即为该节点的后继节点。

对于二分搜索树而言，待删除节点的后继节点就是该节点右子树“最左的”那个节点，将后继节点替换待删除的节点就完成了删除操作。

除了寻找待删除节点的后继节点，我们还可以寻找待删除节点的前驱节点（precursor），对于二分搜索树而言，待删除节点的前驱节点就是该节点左子树“最右的”那个节点。将前驱节点替换待删除的节点同样是可行的，在这里我就使用后继节点的这个思路了。

Hibbard Deletion 算法如下：

在二分搜索树中删除一个节点的操作 Java 代码如下

public void remove(E e) {
    root = remove(e, root);
}

private Node remove(E e, Node node) {
    if (node == null) {
        return null;
    }
    if (e.compareTo((E) node.e) < 0) {
        node.left = remove(e, node.left);
        return node;
    } else if (e.compareTo((E) node.e) > 0) {
        node.right = remove(e, node.right);
        return node;
    } else {
        if (node.left == null) {
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }
        if (node.right == null) {
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }
        
        // Hibbard Deletion
        Node successor = minimum(node.right);
        Node right = removeMin(node.right);
        Node left = node.left;
        successor.left = left;
        successor.right = right;
        node.left = null;
        node.right = null;
        return successor;
    }
}

我实现的二分搜索树的完整代码请参考文章最后给出的链接。

二分搜索树增删改查操作的复杂度分析

在最理想的情况下，也就是二分搜索树为一棵平衡二叉树时。它的增删改查的时间复杂度均为 $O(logN)$。

但是，很遗憾的，二分搜索树并不是一棵平衡二叉树。

试想一下，当我们将一个递增数组中的元素依次添加到二分搜索树中，此时二分搜索树就会退化为一个链表，那么增删改查的时间复杂度均会退化为 $O(N)$。

为了解决二分搜索树的这一问题，在后面，人们在二分搜索树这一数据结构上不断改进研究出了譬如： AVL 树这种绝对平衡二叉树，和红黑树这种弱平衡二叉树等数据结构。

在后面，我会依次对这些数据结构进行介绍，敬请期待。

三：二分查找法

在我们了解过二分搜索树这样一种数据结构之后，理解二分查找法就不难了。

二分查找法（Binary Search）也被称作折半查找法，它是一种效率较高的查找算法，但是使用二分查找法的前提是待查找的数列必须是一个有序数列。也就是说，排序是二分查找法的前置条件。

二分查找的原理是非常简单的：

我们要在一个有序数组 arr 中寻找一个目标值 target 的位置，首先我们定位到数组最中间的位置，如果我们的目标值 target 比中间的那个数字 v 还要小，我们就在 v 左边部分继续寻找；如果我们的目标值 target 比中间的那个数字 v 还要大，我们就在 v 右边部分继续寻找。很容易地就可以想到，这是其实就是一个递归的过程。

那二分查找法的时间复杂度是多少呢？

我们每一次定位到有序数组的中点，并且让目标值与中点值进行比较，如果找到了我们就直接返回结果，如果没有找到，那目标值不是在以中点值作为划分的左半边就是以中点值作为划分的右半边，换句话说，每一次，我们都可以砍掉一半的数据。所以，二分查找法的时间复杂度实际上就是对有序数组的个数 N 不停地除 2，直至找到目标值的次数，也就是 $O(logN)$。

我们也可以换一种方式进行思考，假设我们所有的数据都分布在二分搜索树中，且我们的二分搜索树是一个绝对平衡的二叉树。我们要查找一个元素的次数最多就是这棵树的高度 h，其中，h 和数据量 N 的关系为：$N=2^h?1$，所以，我们也可以得出二分查找法的时间复杂度为$O(logN)$。

二分查找法的思想看上去非常简单，不过实现起来需要注意很多的细节。值得一提的是，二分查找的思想在 1946 年被 John Mauchly 提出，直至 1962 年，才出现了第一个没有 bug 的二分查找算法的实现，中间整整隔了 16 年 ：）。

二分查找法的实现

二分查找法的 Java 代码 ：

public class BinarySearch {
    private BinarySearch() {
    }


    /**
     * 二分查找的非递归算法：返回 target 在已序数组 data 中的索引，如果没有则返回 -1
     *
     * @param data
     * @param target
     * @param <E>
     * @return
     */
    public static <E extends Comparable<E>> int search(E[] data, E target) {
        int l = 0, r = data.length - 1;

        while (l <= r) {
            int mid = l + ((r - l) >> 1);

            if (target.compareTo(data[mid]) == 0)
                return mid;
            else if (target.compareTo(data[mid]) > 0)
                l = mid + 1;
            else
                r = mid - 1;
        }
        return -1;
    }

    /**
     * 二分查找的递归算法：返回 target 在已序数组 data 中的索引，如果没有则返回 -1
     *
     * @param data
     * @param target
     * @param <E>
     * @return
     */
    public static <E extends Comparable<E>> int searchR(E[] data, E target) {
        return searchR(data, 0, data.length - 1, target);
    }

    private static <E extends Comparable<E>> int searchR(E[] data, int l, int r, E target) {
        if (l > r)
            return -1;

        int mid = l + ((r - l) >> 1);

        if (data[mid].compareTo(target) == 0)
            return mid;
        if (target.compareTo(data[mid]) > 0)
            return searchR(data, mid + 1, r, target);

        return searchR(data, l, mid - 1, target);
    }
}

二分查找算法的实现在现在看来是非常简单的，那么为什么在 1962 年之前，二分查找法的实现是有 bug 的呢？

这里面主要的 bug 在求中值 mid 的写法上。

以前的代码的写法是这样的：

int mid = (l + r) / 2;

在 l 和 r 不越界溢出的情况下，我们无法保证 l + r 是不溢出的。

所以，改进后的代码使用了这样的写法：

// int mid = l + (r - l)/2;
int mid = l + ((r - l) >> 1);

这样，我们就可以保证在 l 和 r 极大的情况下，计算出现数据溢出范围的问题。

四：总结

在这一篇文章中，我介绍了二分搜索树这种数据结构以及它的代码实现，并且还介绍了二分查找算法。大家可以看到，二分查找和二分搜索树这种数据结构在本质上有着千丝万缕的联系。

不过，二分搜索树并不是一棵平衡二叉树，所以在给出的数据极端的情况下，二分搜索树会退化成链表，严重降低其增删改查的性能。

在后面，我还会向大家介绍一些平衡二叉树，届时我们可以一起探究这些平衡二叉树在二叉搜索树的基础上到底做了哪些优化。

本文中使用的代码链接：

https://github.com/jinrunheng/datastructure-and-algorithm/

好啦，至此为止，这一篇文章我就介绍完毕了～欢迎大家关注我的公众号【kim_talk】，在这里希望你可以收获更多的知识，我们下一期再见！