数据结构之：二分搜索树-低调大师

数据结构之：二分搜索树

2021-01-15 730

为什么要研究树结构

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

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

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

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

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

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

二分搜索树基础

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

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

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

/**
 * @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);
        }
    }
}

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

首先根节点入栈
进入循环，栈顶元素出栈，输出28
当前出栈元素的右节点不为空，将右节点30压入栈中
当前出栈元素的左节点不为空，将左节点16压入栈中
此时栈不为空，继续循环，栈顶元素出栈，输出16（后进先出）
当前出栈元素的右节点不为空，将右节点22压入栈中
当前出栈元素的左节点不为空，将左节点13压入栈中
继续循环，栈顶元素出栈，输出13
当前出栈元素的右节点为空，什么都不做
当前出栈元素的左节点为空，什么都不做
继续循环，栈顶元素出栈，输出22
重复第9、10步
继续循环，栈顶元素出栈，输出30
当前出栈元素的右节点不为空，将右节点42压入栈中
当前出栈元素的左节点不为空，将左节点29压入栈中
继续循环，栈顶元素出栈，输出29
重复第9、10步
继续循环，栈顶元素出栈，输出42
重复第9、10步
此时栈中没有元素了，为空，跳出循环
最终的输出为：28 16 13 22 30 29 42

二分搜索树的层序遍历

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

当遍历第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);
        }
    }
}

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

首先根节点入队
进入循环，队头元素出队，输出28
当前出队元素的左节点不为空，将左节点16入队
当前出队元素的右节点不为空，将右节点30入队
此时队列不为空，继续循环，队头元素出队，输出16（先进先出）
当前出队元素的左节点不为空，将左节点13入队
当前出队元素的右节点不为空，将右节点22入队
继续循环，队头元素出队，输出30
当前出队元素的左节点不为空，将左节点29入队
当前出队元素的右节点不为空，将右节点42入队
继续循环，队头元素出队，输出13
当前出队元素的左节点为空，什么都不做
当前出队元素的右节点为空，什么都不做
继续循环，队头元素出队，输出22
重复第12、13步
继续循环，队头元素出队，输出29
重复第12、13步
继续循环，队头元素出队，输出42
重复第12、13步
此时栈中没有元素了，为空，跳出循环
最终的输出为：28 16 30 13 22 29 42

广度优先遍历的意义：

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

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

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

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

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

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

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

/**
 * 获取二分搜索树的最小元素
 */
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：

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

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

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

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

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

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

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

具体的实现代码如下：

/**
 * 从二分搜索树中删除元素为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;
}

微信关注我们

原文链接：https://blog.51cto.com/zero01/2592656

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

Wine 6.0 正式版发布：支持 Linux 运行 Windows 应用，PE 格式核心模块 ...

1月19日消息外媒 Windows Central 报道，Wine 最近收到了更新，改善了在 Linux 系统上运行 Windows 应用的体验。该更新以 Wine 6.0 的形式出现，根据其完整的发布说明，包括了超过 8300 项更改。 IT之家获悉，Wine 是一个兼容性层，允许你在 Linux 系统上运行成千上万的 Windows 应用程序。Wine 目前支持超过 27000 个 Windows 应用和游戏，不过值得注意的是，有些游戏需要特殊配置。热门支持的应用和游戏包括 Office、Adobe Photoshop 和《魔兽世界》。新发布的 6.0 版本有数千项改变，但 Wine 网站强调了一些最大的改进： PE 格式的核心模块 WineD3D 的 Vulkan 后端。 DirectShow 和 Media Foundation 支持。文本控制台重新设计。 Wine 6.0 的完整发布说明中称，核心 DLLs，包括 NTDLL、KERNEL32、GDI32 和 USER32 现在以 Portable Executable（PE）格式构建。因此，人们应该看到某些拷贝保护方案的...

2021-01-19

677

云计算成为大势所趋，这一点已经毋庸置疑。中桥调研咨询近期对中国企业级用户（调查样本：企业规模在1000人以上）的调查数据显示，在受访者中，有70%的用户表示未来两年将选择混合云作为企业IT的典型形态；有近8%的用户选择所有应用上公有云；同时，有85%的用户将是否能跨核心-边缘-云实现企业级的一致性作为选择云平台最重要的考核因素。在数字化转型和“新基建”下，云原生应用加速创新，数据从成本变资产，以及资源变动能，这是企业级用户上云最重要的市场驱动力。但传统的企业级用户与互联网公司不同，他们普遍拥有正运行在已有数据中心的核心业务系统，很难“重打鼓，另开张”地构建云平台，而混合云则成为这些企业向云计算平滑演进的首选平台。近日，戴尔科技集团与中桥调研咨询联合举办了《云计算发展新趋势，重塑企业级云平台》在线研讨会，并邀请信达期货总经理助理（信达期货前CIO）王海平一起，通过在线“云对话”，共同探讨“新基建”下企业级云平台的形态和价值。云计算对于传统企业级用户意味着什么？相对于互联网公司与生俱来的云原生来说，传统的企业级用户多年积累建设的IT资源和业务流程经不起推倒重来，那么这些企业在数字化转...

2021-01-20

678

资源下载

更多资源

腾讯云软件源

为解决软件依赖安装时官方源访问速度慢的问题，腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构，目前腾讯云软件源站支持公网访问和内网访问。

Nacos

Nacos /nɑ:kəʊs/ 是 Dynamic Naming and Configuration Service 的首字母简称，一个易于构建 AI Agent 应用的动态服务发现、配置管理和AI智能体管理平台。Nacos 致力于帮助您发现、配置和管理微服务及AI智能体应用。Nacos 提供了一组简单易用的特性集，帮助您快速实现动态服务发现、服务配置、服务元数据、流量管理。Nacos 帮助您更敏捷和容易地构建、交付和管理微服务平台。

Sublime Text

Sublime Text具有漂亮的用户界面和强大的功能，例如代码缩略图，Python的插件，代码段等。还可自定义键绑定，菜单和工具栏。Sublime Text 的主要功能包括：拼写检查，书签，完整的 Python API ， Goto 功能，即时项目切换，多选择，多窗口等等。Sublime Text 是一个跨平台的编辑器，同时支持Windows、Linux、Mac OS X等操作系统。

WebStorm

WebStorm 是jetbrains公司旗下一款JavaScript 开发工具。目前已经被广大中国JS开发者誉为“Web前端开发神器”、“最强大的HTML5编辑器”、“最智能的JavaScript IDE”等。与IntelliJ IDEA同源，继承了IntelliJ IDEA强大的JS部分的功能。