13.数据结构：二分搜索树

大家好，我是王有志。

好久不见，不知道大家这个十一假期过得怎么样？有没有做好迎接7个工作日的准备呢？

接下来就开始我们今天的主题吧，第一个二叉树的应用--二分搜索树。

认识二分搜索树

二分搜索树是二叉树中最简单的应用，除了二叉树的特性外，还具有以下特点：

• 左子树的节点均小于根节点
• 右子树的节点均大于根节点
• 所有子树也都是二分搜索树

如下就是一棵二分搜索树：

二分搜索树.png

相较于二叉树的“毫无章法”而言，二分搜索树是“有序”的。在上图这种“分布均匀”的二分搜索树中查找元素消耗的时间是远低于链表等线性结构的。

实现二分搜索树

这里使用一个比较简单的接口来实现二分搜索树：

public interface Tree<E extends Comparable<E>> {

    /**
     * 树的大小
     * @return
     */
    int size();

    /**
     * 树是否为空
     * @return
     */
    boolean isEmpty();

    /**
     * 添加元素
     * @param element
     */
    void add(E element);

    /**
     * 是否包含元素
     * @param element
     * @return
     */
    boolean contains(E element);
  
    /**
     * 删除节点
     * @param element
     * @return
     */
    void remove(E element);

接口的声明中添加了泛型，要求必须继承Comparable接口，是为了比较元素的大小，以实现二分搜索树的“有序”。

定义树的节点：

@Getter
@Setter
public class TreeNode<E extends Comparable<E>> {

    private E element;

    private TreeNode<E> left;

    private TreeNode<E> right;

    public TreeNode(E element) {
        this.element = element;
    }
}

这里使用了Lombok，不喜欢lombok的话，手动实现Getter和Setter即可。不过我觉得合理的使用并不会产生太多的影响，而且会让代码变得更加简洁。

声明二分搜索树：

public class BinarySearchTree<E extends Comparable<E>> implements Tree<E> {

    /**
     * 二分搜索树的大小
     */
    int size;

    /**
     * 二分搜索树的根节点
     */
     TreeNode<E> root;

    // 此处省略方法
}

特别说明：在下面实现的二分搜索树中，左子节点是小于等于根节点的。

添加元素

二分搜索树中添加元素不需要指定位置，添加方法要根据父节点的“大小”自动的添加到合适位置。

知道了上面的内容后，我脑海里复现的想法是，从根节点出发逐个查找，直到找到合适的位置后添加元素。假设我们向如下的二叉树中添加数字28：

迭代添加.png

首先和根节点56比较，接着根据二分搜索树的特点，与左子树的根节点比较，之后依次向下比较，最后添加到节点35的左子节点上。

我们尝试使用代码来翻译这个过程，当然要记得对空树这种边界情况进行处理：

@Override
public void add(E element) {
    TreeNode<E> newestNode = new TreeNode<>(element);
    if(this.root == null) {
        this.root = newestNode;
    } else {
        // 遍历二分搜索树，添加元素
    }
    this.size++;
}

接着写核心代码，就是空出来else分支的部分--遍历二分搜索树，添加元素。

首先我们回忆一下，在链表中实现指定位置插入元素时，首先要做的是找到直接前驱节点，二分搜索树中也是类似的，如果将比较的路径串联起来，何尝不是一个链表呢？只不过在二分搜索树中需要比较大小。

代码就非常简单了：

TreeNode<E> parentNode = this.root;
while (parentNode != null) {
    if (element.compareTo(parentNode.getElement()) > 0) {
        if (parentNode.getRight() == null) {
            parentNode.setRight(newestNode);
            break;
        }
        parentNode = parentNode.getRight();
    } else {
        if (parentNode.getLeft() == null) {
            parentNode.setLeft(newestNode);
            break;
        }
        parentNode = parentNode.getLeft();
    }
}

将两部分代码合并起来，就实现了向二分搜索树中添加元素的方法。但是有点“难看”啊，有没有什么“好看”的方式呢？

递归实现

上面是适合人脑的方式，并不一定适合电脑，为了让电脑能够看懂写起来多少是有些费力的，那么什么是适合电脑的方式呢？

没错，还是递归。我们再重复下递归是如何解决问题的，不断地拆分问题，逐个解决后合并。

另外，树中很重要的一个特点是任何一个节点都可以看做是树，空也是树。

这个问题中，除了需要考虑根节点为空的边界情况外，还要考虑到最后合适的位置一定是空，遇到这两种情况时，就可以直接创建新的节点了。

我们尝试着写一段代码：

public void add(E element) {
    add(this.root, element);
}

private void add(TreeNode<E> node, E element) {
    if(node == null) {
        this.size++;
        new TreeNode<>(element);
    }
}

代码是一目了然了，不过问题是虽然创建了新节点，但要怎么关联到树上？

我们来改写下代码，先试着解决空树时如何关联的问题：

public void add(E element) {
    this.root = add(this.root, element);
}

private TreeNode<E> add(TreeNode<E> node, E element) {
    if(node == null) {
        this.size++;
        return new TreeNode<>(element);
    }
}

接着我们处理非空树的情况，非空树时我们要做的是拆分问题，并关联新的节点。代码如下：

if (element.compareTo(node.getElement()) > 0) {
    node.setRight(add(node.getRight(), element));
} else {
    node.setLeft(add(node.getLeft(), element));
}

将两部分合并起来，最后将根节点返回即可。完整的代码如下：

public void add(E element) {
    this.root = add(this.root, element);
}

private TreeNode<E> add(TreeNode<E> node, E element) {
    if(node == null) {
        this.size++;
        return new TreeNode<>(element);
    }
    if (element.compareTo(node.getElement()) > 0) {
        node.setRight(add(node.getRight(), element));
    } else {
        node.setLeft(add(node.getLeft(), element));
    }
    return node;
}

包含元素

接着实现判断二分搜索树中是否包含元素的方法，有了前面的经验，我们直接上递归。

思想也很简单，根据二分搜索树的特点，不断拆分出子树比较大小，找到符合的元素返回即可。代码如下：

public boolean contains(E element) {
    return contains(this.root, element);
}

private boolean contains(TreeNode<E> node, E element) {
    if (node == null) {
        return false;
    }  
    if (element.compareTo(node.getElement()) > 0) {
        return contains(node.getRight(), element);
    } else if (element.compareTo(node.getElement()) < 0) {
        return contains(node.getLeft(), element);
    } else {
        return true;
    }
}

删除元素

回到第一张图，如果要删除树中的叶子节点，直接删除即可，如果要删除元素75，相信你也可以想到，可以将元素80作为元素69的左子节点。

但是，如果要删除元素69呢？你会怎么做？

将元素60或者元素75移上来作为根节点，再重新排列子树？这种方式也未尝不可，但是需要移动比较多的元素，效率肯定是差强人意了。

如果要尽可能少的移动元素，那么接替根节点的应该是最接近元素69的，在元素69的两棵子树中，谁最接近呢？元素63和元素73。

Hibbard Deletion

如果想到了这里，那么恭喜你，这是计算机科学家Thomas Hibbard在1962年提出提出的Hibbard Deletion。

有能力的小伙伴可以点开链接看看埃默里大学对Hibbard Deletion的研究，不过它的核心思想就一句话：

swap the node to be deleted with its successor.

将需要删除的节点与后继节点进行交换。这里说的后继节点是二分搜索树中大于该元素，且最接近该元素的节点。

方法我们有了，接下来我们需要做一些准备工作。

还是以删除元素69为例，我们如何找到它的后继节点元素73呢？很简单，它是以元素75为根节点的子树中的最小值，我们只需要实现一个二分搜索树查找最小值的方法即可。

查找最小/最大元素

思想是很简单的，传入一棵二叉搜索树，找到最左侧的节点即可。特别强调，最左侧的节点可以不是叶子节点，另外二分搜索树中最小元素所在的节点要么是叶子节点，要么只有右子树。。

还是用递归实现：

private TreeNode<E> minNode(TreeNode<E> node) {
    if (node.getLeft() == null) {
        return node;
    }
    return minNode(node.getLeft());
}

那么我们也可以为二分搜索树添加外部可以使用的查找最小元素的方法：

public E min() {  
    if (isEmpty()) {  
        return null;  
    }  
    return minNode(this.root).getElement();  
}

相信你可以很轻松的写出查找最大元素的方法。

找到了最小元素，接着要做的就是替换掉待删除的节点，同时记得要删除原来子树上的最小元素。那么我们还需要一个删除最小元素的方法。

删除最小/最大元素

同样的，传入一棵子树，找到其最左侧的节点，然后删除即可。

删除最小节点.png

这棵树中最小元素是35，要删除元素35就要移动元素47，可以将元素47作为元素49的左子节点，接替元素35的位置。

借鉴我们递归实现添加元素的思想，删除元素35即删除以元素35为根节点的左子树的根节点，此时子树的新根节点是元素47。

代码就呼之欲出了：

private TreeNode<E> removeMin(TreeNode<E> node) {
    if(node.getLeft() == null) {
        TreeNode<E> rightChild = node.getRight();
        node.setRight(null);
        return rightChild;
    }
    node.setLeft(removeMin(node.getLeft()));
    return node;
}

接着我们完善一下，为二分搜索树添加外部可以使用的删除最小元素的方法：

public E removeMin() {
    E e = min();
    this.root = removeMin(this.root);
    return e;
}  
  
private TreeNode<E> removeMin(TreeNode<E> node) {
    if (node.getLeft() == null) {
        TreeNode<E> rightChild = node.getRight();
        node.setRight(null);
        this.size--;
        return rightChild;
    }  
    node.setLeft(removeMin(node.getLeft()));
    return node;
}

同样的，我们也可以添加删除最大元素的方法。

删除任意元素

到目前为止，我们已经找到了子树中最小元素，并且也删除了最小元素，看起来前期准备工作已经完成了，接着我们开始实现删除二分搜索树中的任意元素。

我们来看，无论是Hibbard Deletion，还是完全重新排列子树，其核心都是重新构建以待删除元素为根节点的子树。

那么我们只需要重新构建这棵子树就可以了。首先，依旧是处理空树这种边界情况：

private TreeNode<E> remove(TreeNode<E> node, E element) {
    if (node == null) {
        return null;
    }
    // 递归
}

接着我们来处理两种元素不相等的情况，也是进入递归的情况，并做好与树的关联：

if (element.compareTo(node.getElement()) > 0) {
    node.setRight(remove(node.getRight(), element));
    return node;
} else if (element.compareTo(node.getElement()) < 0) {
    node.setLeft(remove(node.getLeft(), element));
    return node;
}

最后要处理的是值相等的情况--重新构建子树，不过此时有3种情况。

右子树为空，删除根节点后，将左子树作为新的子树返回：

if (node.getRight() == null) {
    TreeNode<E> leftChild = node.getLeft();
    node.setLeft(null);
    return leftChild;
}

左子树为空，删除根节点后，将右子树作为新的子树返回：

if (node.getLeft() == null) {
    TreeNode<E> rightChild = node.getRight();
    node.setRight(null);
    return rightChild;
}

最后就是左右子树均不为空的情况，按照Hibbard Deletion的思想，新的根节点是待删除节点的后继节点，这里就用上了之前实现的查找最小元素和删除最小元素的方法了。

我们把以元素69为根节点的子树单独拆出来，根节点的替代者是元素73，首先查找到右子树最小元素73（查找最小元素），然后断开与元素75的联系（删除最小元素），接着构建元素73的左右子树，左子树就是元素69的左子树，右子树是删除最小元素后元素69的右子树，最后只需要断开元素69与左右子树的联系即可。

删除任意元素.png

那么代码就非常简单了：

TreeNode<E> nextNode = minNode(node.getRight());
nextNode.setRight(removeMin(node.getRight()));
nextNode.setLeft(node.getLeft());
node.setLeft(null);
node.setRight(null);
return nextNode;

最后我们合并所有的部分，完整的代码如下：

private TreeNode<E> remove(TreeNode<E> node, E element) {
    if (node == null) {
        return null;
    }
    if (element.compareTo(node.getElement()) > 0) {
        node.setRight(remove(node.getRight(), element));
        return node;
    } else if (element.compareTo(node.getElement()) < 0) {
        node.setLeft(remove(node.getLeft(), element));
        return node;
    } else {
        if (node.getRight() == null) {
            TreeNode<E> leftChild = node.getLeft();
            node.setLeft(null);
            this.size--;
            return leftChild;
        }
        if (node.getLeft() == null) {
            TreeNode<E> rightChild = node.getRight();
            node.setRight(null);
            this.size--;
            return rightChild;
        }
        TreeNode<E> nextNode = minNode(node.getRight());
        nextNode.setRight(removeMin(node.getRight()));
        nextNode.setLeft(node.getLeft());
        node.setLeft(null);
        node.setRight(null);
        return nextNode;
    }
}

再添加上我不可以使用的方法：

public void remove(E element) {
    this.root = remove(this.root, element);
}

好了，到目前为止删除元素的方法就完成了。

结语

今天我们一起认识了二分搜索树的特性，二分搜索树是在二叉树的基础上添加了“排序”的特性，使其变得“有序”。接着我们一起实现了自己的二分搜索树，核心方法通过递归实现，不知道有没有再次加深你对递归的理解？

你以为这就完了吗？其实还遗留了3点。

首先是二分搜索树的优势在哪？核心方法的时间复杂度如何？为什么用二分搜索树而不是链表？留给大家思考。

其次是二分搜索树的遍历，虽然可以照搬二叉树的遍历，不过动手写一写，看一看输出的结果，你会有新的发现。

最后就是，文章中出现的二分搜索树节点的分布都很均匀，如果添加元素的顺序是：[28, 35, 47, 49, 53, 56, 58, 60, 63, 69, 73, 75, 80]，那么这棵二分搜索树还具有它的特性吗？

练习

• 计算二分搜索树核心方法的时间复杂度
• 实现二分搜索树的前中后序遍历
• 通过迭代的方式实现核心方法

简单

• 108.将有序数组转换为二叉搜索树
• 剑指Offer 54.二叉搜索树的第k大节点

中等

• 95.不同的二叉搜索树 II
• 96.不同的二叉搜索树
• 98.验证二叉搜索树
• 99.恢复二叉搜索树
• 235.二叉搜索树的最近公共祖先
• 450.删除二叉搜索树中的节点
• 剑指Offer 36.二叉搜索树与双向链表

本篇内容的代码仓库：Gitee代码仓库

递归实现的二分搜索树：BinarySearchTree.java
迭代实现的二分搜索树：BinarySearchTreeIterator.java

代码有疏漏的地方，还希望大家指正。截止到这篇文章发出来时，迭代实现应该还没有写完，我实在是太懒了。

---

好了，今天就到这里了，Bye~~