数据结构之：二分搜索树

为什么要研究树结构

为什么要研究树结构？首先因为树在计算机程序中是非常重要的数据结构之一，并且树结构本身是一种天然的组织结构。在很多情况下将数据使用树结构存储后，会发现出奇的高效。甚至有些问题，必须要使用树结构才能够解决。

树这种结构，在我们日常生活中也经常看到，例如我们操作系统的文件夹，公司的部门层级，图书馆书籍分类等：

image.png

可以看到树是一种一对多的数据结构，所以在现实生活中，遇到一对多的问题需要处理时，就可以想到使用到树这种数据结构。我们来举一个例子，公司里某一天CEO要找一个程序员，他只需要到研发部就能找到想要找的人。这是因为公司内部的人员编排都是根据部门层级划分的，然后部门里又规定了哪些人员受谁管理，这种层级划分和人员关系就很好的体现了一个树形的结构，所以我们才能够在公司内快速的找到某个员工。

若公司内的人员编排是线性的，那么在最坏的情况下就需要找遍整个公司的员工才能找出来想要找的人。就像我们要在数组中找一个元素，而这个元素刚好在数组的末尾，若我们在不知道索引的情况下，就需要遍历整个数组才能够找到该元素。可以看到在同一问题下这两种结构的对比，树结构的效率是要高得多的，这也是我们为什么要学习树的原因。

树结构有很多中，常见的有：

• 二分搜索树
• 线段树
• Trie
• B+树
• AVL
• 红黑树

---

二分搜索树基础

在介绍二分搜索树之前我们先来看二叉树，二叉树是最基本的树形结构，二叉树由一个根节点和多个子节点组成，包括根节点在内的每个节点最多拥有左右两个子节点，俗称左孩子和右孩子。树和链表一样也是动态的数据结构：

image.png
image.png
image.png
image.png
image.png

二分搜索树在二叉树的基础上增加了一些规则：

image.png
image.png

我们先来编写二分搜索树节点的结构以及二分搜索树基础的属性和方法，代码如下：

/**
 * @author 01
 * @program Data-Structure
 * @description 二分搜索树-存储的数据需具有可比较性，所以泛型需继承Comparable接口
 * @create 2018-11-13 17:02
 * @since 1.0
 **/
public class BinarySearchTree<E extends Comparable<E>> {
    /**
     * 二分搜索树节点的结构
     */
    private class Node {
        E e;
        Node left;
        Node right;

        public Node() {
            this(null, null, null);
        }

        public Node(E e) {
            this(e, null, null);
        }

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

    /**
     * 根节点
     */
    private Node root;

    /**
     * 表示树里存储的元素个数
     */
    private int size;

    /**
     * 获取树里的元素个数
     *
     * @return 元素个数
     */
    public int size() {
        return size;
    }

    /**
     * 树是否为空
     *
     * @return 为空返回true，否则返回false
     */
    public boolean isEmpty() {
        return size == 0;
    }
}

---

向二分搜索树中添加元素

我们的二分搜索树不包含重复元素，如果想让树包含重复元素的话，也很简单，只需要改变定义为：左子树小于等于节点；或者右子树大于等于节点。

二分搜索树添加元素的非递归写法，和链表很像，只不过链表中不需要与节点进行比较，而树则需要比较后决定是添加到左子树还是右子树。

具体的实现代码如下：

/**
 * 向二分搜索树中添加一个新元素e
 *
 * @param e 新元素
 */
public void add(E e) {
    if (root == null) {
        // 根节点为空的处理
        root = new Node(e);
        size++;
    } else {
        add(root, e);
    }
}

/**
 * 向以node为根的二分搜索树中插入元素e，递归实现
 *
 * @param node
 * @param e
 */
private void add(Node node, E e) {
    // 递归的终止条件
    if (e.equals(node.e)) {
        // 不存储重复元素
        return;
    } else if (e.compareTo(node.e) < 0 && node.left == null) {
        // 元素e小于node节点的元素，并且node节点的左孩子为空，所以成为node节点的左孩子
        node.left = new Node(e);
        size++;
        return;
    } else if (e.compareTo(node.e) > 0 && node.right == null) {
        // 元素e大于node节点的元素，并且node节点的右孩子为空，所以成为node节点的右孩子
        node.right = new Node(e);
        size++;
        return;
    }

    if (e.compareTo(node.e) < 0) {
        // 元素e小于node节点的元素，往左子树走
        add(node.left, e);
    } else {
        // 元素e大于node节点的元素，往右子树走
        add(node.right, e);
    }
}

---

改进添加操作：深入理解递归终止条件

上面所实现的往二叉树里添加元素的代码虽然是没问题的，但是还有优化的空间。一是在add(E e)方法中对根节点做了判空处理，与后面的方法在逻辑上有些不统一，实际上可以放在后面的方法中统一处理；二是add(Node node, E e)方法中递归的终止条件比较臃肿，可以简化。

优化后的实现代码如下：

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

/**
 * 向以node为根的二分搜索树中插入元素e，精简后的递归实现
 *
 * @param node
 * @param e
 * @return 返回插入新节点后二分搜索树的根节点
 */
private Node add2(Node node, E e) {
    // 递归的终止条件
    if (node == null) {
        // node为空时必然是可以插入新节点的
        size++;
        return new Node(e);
    }

    if (e.compareTo(node.e) < 0) {
        // 元素e小于node节点的元素，往左子树走
        node.left = add2(node.left, e);
    } else if (e.compareTo(node.e) > 0) {
        // 元素e大于node节点的元素，往右子树走
        node.right = add2(node.right, e);
    }
    
    // 相等什么也不做
    return node;
}

• 修改递归的终止条件后，我们只需要在节点为空时，统一插入新节点，不需要再判断左右子节点是否为空。这样选择合适的终止条件后，多递归了一层但减少很多不必要的代码

---

二分搜索树的查询操作

有了前面的基础后，通过递归实现二分搜索树的查询操作就很简单了，只需要比较元素的大小，不断地递归就能找到指定的元素。代码如下：

/**
 * 查看二分搜索树中是否包含元素e
 */
public boolean contains(E e) {
    return contains(root, e);
}

/**
 * 查看以node为根节点的二分搜索树中是否包含元素e，递归实现
 */
private boolean contains(Node node, E e) {
    if (node == null) {
        return false;
    }

    if (e.compareTo(node.e) == 0) {
        return true;
    } else if (e.compareTo(node.e) < 0) {
        // 找左子树
        return contains(node.left, e);
    }
    
    // 找右子树
    return contains(node.right, e);
}

---

二分搜索树的前序遍历

什么是遍历操作：

• 遍历操作就是把所有节点都访问一遍，使得可以对所有节点元素进行操作。在线性结构下，遍历是极其容易的，一个循环就解决了。但是在树结构下就稍微有些麻烦了，因为对于树的遍历操作，两棵子树都要顾及

二叉树的遍历方式主要有这么几种：前序遍历、中序遍历、后序遍历以及层序遍历。本小节将要演示的是前序遍历，所谓前序遍历就是先遍历根节点，然后再遍历左子树和右子树。前序遍历是最自然、最常用的遍历方式。

前序遍历使用递归实现起来非常的简单，代码如下：

/**
 * 二分搜索树的前序遍历
 */
public void preOrder() {
    preOrder(root);
}

/**
 * 前序遍历以node为根的二分搜索树，递归实现
 */
private void preOrder(Node node) {
    if (node == null) {
        return;
    }

    // 先遍历根节点
    System.out.println(node.e);

    // 然后遍历左子树和右子树
    preOrder(node.left);
    preOrder(node.right);
}

---

二分搜索树的中序遍历和后序遍历

了解了前序遍历后，中序遍历和后序遍历就很简单了，无非就是换了个顺序。其中中序遍历就是先遍历左子树，然后遍历根节点，再遍历右子树。所以中序遍历的这个“中序”就体现在了根节点是在左右子树的中间进行遍历的。具体的实现代码如下：

/**
 * 二分搜索树的中序遍历
 */
public void inOrder() {
    inOrder(root);
}

/**
 * 中序遍历以node为根的二分搜索树，递归实现
 */
private void inOrder(Node node) {
    if (node == null) {
        return;
    }

    // 先遍历左子树
    inOrder(node.left);
    // 然后遍历根节点
    System.out.println(node.e);
    // 最后遍历右子树
    inOrder(node.right);
}

• 二分搜索树的中序遍历的特性是可以按照元素从小到大的顺序访问节点，将遍历过程输出就可以看到是有序的

同样的，后序遍历也是换了个顺序，是先遍历左子树，然后遍历右子树，再遍历根节点。具体的实现代码如下：

/**
 * 二分搜索树的后序遍历
 */
public void postOrder() {
    postOrder(root);
}

/**
 * 后序遍历以node为根的二分搜索树，递归实现
 */
private void postOrder(Node node) {
    if (node == null) {
        return;
    }

    // 先遍历左子树
    postOrder(node.left);
    // 然后遍历右子树
    postOrder(node.right);
    // 最后遍历根节点
    System.out.println(node.e);
}

• 后序遍历通常用于需要先处理左右子树，最后再处理根节点的场景，例如为二分搜索树释放内存（C++）

---

二分搜索树前序遍历的非递归实现

虽然使用递归实现对树的遍历会比较简单，但通常在实际开发中并不会太多的去使用递归，一是怕数据量大时递归深度太深导致栈溢出，二是为了减少递归函数调用的开销。中序遍历和后序遍历的非递归实现，实际应用不广，所以本小节主要演示一下前序遍历的非递归实现。

前序遍历的非递归实现思路有好几种，这里主要介绍一种递归算法转非递归实现的比较通用的思路。理解这种思路后我们也可以将其应用到其他的递归转非递归实现的场景上，这种方法就是自己用额外的容器模拟一下系统栈。具体的代码实现如下：

/**
 * 二分搜索树的非递归前序遍历实现
 */
public void preOrderNR() {
    // 使用 java.util.Stack 来模拟系统栈
    Stack<Node> stack = new Stack<>();
    // 前序遍历所以先将根节点压入栈
    stack.push(root);
    while (!stack.isEmpty()) {
        // 将当前要访问的节点出栈
        Node cur = stack.pop();
        System.out.println(cur.e);

        if (cur.right != null) {
            // 由于栈的特性是后入先出，所以这里是右子树先入栈
            stack.push(cur.right);
        }
        if (cur.left != null) {
            stack.push(cur.left);
        }
    }
}

以这样一颗树为例，简单描述下以上代码的执行过程：

image.png

1. 首先根节点入栈
2. 进入循环，栈顶元素出栈，输出28
3. 当前出栈元素的右节点不为空，将右节点30压入栈中
4. 当前出栈元素的左节点不为空，将左节点16压入栈中
5. 此时栈不为空，继续循环，栈顶元素出栈，输出16（后进先出）
6. 当前出栈元素的右节点不为空，将右节点22压入栈中
7. 当前出栈元素的左节点不为空，将左节点13压入栈中
8. 继续循环，栈顶元素出栈，输出13
9. 当前出栈元素的右节点为空，什么都不做
10. 当前出栈元素的左节点为空，什么都不做
11. 继续循环，栈顶元素出栈，输出22
12. 重复第9、10步
13. 继续循环，栈顶元素出栈，输出30
14. 当前出栈元素的右节点不为空，将右节点42压入栈中
15. 当前出栈元素的左节点不为空，将左节点29压入栈中
16. 继续循环，栈顶元素出栈，输出29
17. 重复第9、10步
18. 继续循环，栈顶元素出栈，输出42
19. 重复第9、10步
20. 此时栈中没有元素了，为空，跳出循环
21. 最终的输出为：28 16 13 22 30 29 42

---

二分搜索树的层序遍历

了解了前中后序遍历，接下来我们看看二分搜索树的层序遍历。所谓层序遍历就是按照树的层级自根节点开始从上往下遍历，通常根节点所在的层级称为第0层或第1层，我这里习惯称之为第1层。如下图所示：

image.png

• 当遍历第1层时，访问到的是28这个根节点；遍历第2层时，访问到的是16以及30这个两个节点；遍历第3层时，则访问到的是13、22、29及42这四个节点

可以看出层序遍历与前中后序遍历不太一样，前中后序遍历都是先将其中一颗子树遍历到底，然后再返回来遍历另一颗子树，其实这也就是所谓的深度优先遍历，而层序遍历也就是所谓的广度优先遍历了。

通常层序遍历会使用非递归的实现，并且会使用一个队列容器作为辅助，所以代码写起来与之前的非递归实现前序遍历非常类似，只不过容器由栈换成了队列。具体的代码实现如下：

/**
 * 二分搜索树的层序遍历实现
 */
public void levelOrder() {
    Queue<Node> queue = new LinkedList<>();
    // 根节点入队
    queue.add(root);
    while (!queue.isEmpty()) {
        // 将当前要访问的节点出队
        Node cur = queue.remove();
        System.out.println(cur.e);

        // 左右节点入队
        if (cur.left != null) {
            queue.add(cur.left);
        }
        if (cur.right != null) {
            queue.add(cur.right);
        }
    }
}

以上面的那棵树为例，我们也来分析下层序遍历代码的执行过程：

1. 首先根节点入队
2. 进入循环，队头元素出队，输出28
3. 当前出队元素的左节点不为空，将左节点16入队
4. 当前出队元素的右节点不为空，将右节点30入队
5. 此时队列不为空，继续循环，队头元素出队，输出16（先进先出）
6. 当前出队元素的左节点不为空，将左节点13入队
7. 当前出队元素的右节点不为空，将右节点22入队
8. 继续循环，队头元素出队，输出30
9. 当前出队元素的左节点不为空，将左节点29入队
10. 当前出队元素的右节点不为空，将右节点42入队
11. 继续循环，队头元素出队，输出13
12. 当前出队元素的左节点为空，什么都不做
13. 当前出队元素的右节点为空，什么都不做
14. 继续循环，队头元素出队，输出22
15. 重复第12、13步
16. 继续循环，队头元素出队，输出29
17. 重复第12、13步
18. 继续循环，队头元素出队，输出42
19. 重复第12、13步
20. 此时栈中没有元素了，为空，跳出循环
21. 最终的输出为：28 16 30 13 22 29 42

广度优先遍历的意义：

• 更快的找到问题的解
• 常用于算法设计中：最短路径

---

删除二分搜索树的最大元素和最小元素

二分搜索树的删除操作是相对比较复杂的，所以我们先来解决一个相对简单的任务，就是删除二分搜索树中的最大元素和最小元素。由于二分搜索树的特性，其最小值就是最左边的那个节点，而最大元素则是最右边的那个节点。

以下面这棵二分搜索树为例，看其最左和最右的两个节点，就能知道最小元素是13，最大元素是42：

image.png

再来看一种情况，以下这棵二分搜索树，往最左边走只能走到16这个节点，往最右边走只能走到30这个节点，所以最大最小元素不一定会是叶子节点：

image.png

• 在这种情况下，删除最大最小元素时，由于还有子树，所以需要将其子树挂载到被删除的节点上

我们先来看看如何找到二分搜索树的最大元素和最小元素。代码如下：

/**
 * 获取二分搜索树的最小元素
 */
public E minimum() {
    if (size == 0) {
        throw new IllegalArgumentException("BST is empty!");
    }

    return minimum(root).e;
}

/**
 * 返回以node为根的二分搜索树的最小元素所在节点
 */
private Node minimum(Node node) {
    if (node.left == null) {
        return node;
    }

    return minimum(node.left);
}

/**
 * 获取二分搜索树的最大元素
 */
public E maximum() {
    if (size == 0) {
        throw new IllegalArgumentException("BST is empty!");
    }

    return maximum(root).e;
}

/**
 * 返回以node为根的二分搜索树的最大元素所在节点
 */
private Node maximum(Node node) {
    if (node.right == null) {
        return node;
    }

    return maximum(node.right);
}

然后再来实现删除操作，代码如下：

/**
 * 删除二分搜索树中的最大元素所在节点，并返回该元素
 */
public E removeMax() {
    E ret = maximum();
    root = removeMax(root);
    return ret;
}

/**
 * 删除以node为根的二分搜索树中的最大节点
 * 返回删除节点后新的二分搜索树的根
 */
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;
}

/**
 * 删除二分搜索树中的最小元素所在节点，并返回该元素
 */
public E removeMin() {
    E ret = minimum();
    root = removeMin(root);
    return ret;
}

/**
 * 删除以node为根的二分搜索树中的最小节点
 * 返回删除节点后新的二分搜索树的根
 */
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;
}

---

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

有了上面的基础后，就应该对实现删除二分搜索树的任意元素有一定的思路了。首先，我们来看看在实现过程中会遇到的一些情况，第一种情况就是要删除的目标节点只有一个左子树，例如删除下图中的58：

image.png

• 在这种情况下，只需要将左子树挂到被删除的目标节点上即可，与删除最大元素的基本逻辑类似

第二种情况与第一种情况相反，就是要删除的目标节点只有一个右子树：

image.png

• 同样的，把右子树挂到被删除的目标节点上即可，与删除最小元素的基本逻辑类似

第三种情况是要删除的目标节点是一个叶子节点，这种情况直接复用以上任意一种情况的处理逻辑即可，因为我们也可以将叶子节点视为有左子树或右子树，只不过为空而已。

比较复杂的是第四种情况，也就是要删除的目标节点有左右两个子节点，如下图所示：

image.png

对于这种情况，我们得把58这个节点下的左右两颗子树融合在一起，此时就可以采用1962年，Hibbard提出的Hibbard Deletion方法解决。

首先，我们将要删除的这个节点称之为 ，第一步是从 的右子树中找到最小的节点 ，这个 就是 的后继了。第二步要做的事情就很简单了，将 从原来的树上摘除并将 的右子树指向这个删除后的右子树，然后再将 的左子树指向 的左子树，最后让 的父节点指向 ，此时就完成了对目标节点 的删除操作。如下图：

image.png

具体的实现代码如下：

/**
 * 从二分搜索树中删除元素为e的节点
 */
public void remove(E e) {
    root = remove(root, e);
}

/**
 * 删除以node为根的二分搜索树中值为e的节点，递归实现
 * 返回删除节点后新的二分搜索树的根
 */
private Node remove(Node node, E e) {
    if (node == null) {
        return null;
    }

    if (e.compareTo(node.e) < 0) {
        // 要删除的节点在左子树中
        node.left = remove(node.left, e);
        return node;
    } else if (e.compareTo(node.e) > 0) {
        // 要删除的节点在右子树中
        node.right = remove(node.right, e);
        return node;
    }

    // 找到了要删除的节点
    // 待删除的节点左子树为空的情况
    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;
    }

    // 待删除的节点左右子树均不为空的情况
    // 找到比待删除节点大的最小节点，即待删除节点右子树的最小节点
    Node successor = minimum(node.right);
    // 用这个节点替换待删除节点的位置
    // 由于removeMin里已经维护过一次size了，所以这里就不需要维护一次了
    successor.right = removeMin(node.right);
    successor.left = node.left;

    return successor;
}