二分搜索树

2019-11-08 约 4192 字预计阅读 9 分钟

二分搜索树

二叉查找树（英语：Binary Search Tree），也称为二分搜索树，二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree）也可以简写为 BST，是指一棵空树或者具有下列性质的二叉树：

若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
任意节点的左、右子树也分别为二叉查找树；
没有键值相等的节点。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(logN)。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合，映射等

基本结构

先搭一个基本的架子出来，后面再来慢慢的完善功能

public class BST<E extends Comparable<E>>{
    //TreeNode
    private class Node{
        public E e;
        public Node left;
        public Node right;
        public Node(E e){
            this.e=e;
            left=null;
            right=null;
        }
    }

    private Node root;

    private int size;

    public BST(){
        root=null;
        size=0;
    }

    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return size==0;
    }

    public void add(E e){
        //...
    }

    public boolean contains(E e){
        //...
    }
}

添加

添加函数，时间复杂度O(logN)，只要抓住了它的性质就很好写，画个图描述下这个过程

① 首先和 root 节点 8 比较，比 8 小，所以肯定再 8 的左子树中

② 再和 root 的左子树根节点 5 比较，比 5 大，所以最后肯定插入 5 的右子树中

③ 再和 5 节点的右子树根节点 6 比较，比 6 大，所以最后插入 6 的右子树中

④ 右子树为空，直接插入到 6 的右边

根据上面的流程我们很容易写出代码

public void addLoop(E e){
    if (root==null) {
        size++;
        root=new Node(e);
        return;
    }
    Node temp=root;
    while(temp!=null){
        if (e.compareTo(temp.e)>0) {
            if (temp.right==null) {
                temp.right=new Node(e);
                size++;
                return;
            }
            temp=temp.right;
        }else if (e.compareTo(temp.e)<0) {
            if (temp.left==null) {
                temp.left=new Node(e);
                size++;
                return;
            }
            temp=temp.left;
        }else return; //不能有相等元素
    }
}

这里既然是树结构，用循环似乎有的显得不够优雅😂

所以我们尝试把这个改成递归

public void add2(E e){
    if(root == null){
        root = new Node(e);
        size ++;
    }else add(root, e);
}

// 向以 node 为根的二分搜索树中插入元素 e, 略显繁琐
private void add2(Node node, E e){
    if(e.equals(node.e)) return;
    if(e.compareTo(node.e) < 0 && node.left == null){
        node.left = new Node(e);
        size ++;
        return;
    }
    if(e.compareTo(node.e) > 0 && node.right == null){
        node.right = new Node(e);
        size ++;
        return;
    }
    if(e.compareTo(node.e) < 0)
        add(node.left, e);
    else //e.compareTo(node.e) > 0
    	add(node.right, e);
}

这个递归？？？咋感觉比循环还繁琐🙄

确实，上面这个递归的终止条件太繁琐了，compareTo一共比较了 4 次，有很多重复代码，所以我们还得改改😋

我们让这个add函数有返回值，返回插入后的根节点，这样我们的函数 add(Node node,E e) 定义就变成了 插入元素e到以 node 为根节点的 BST 中，并且返回根节点 ，清楚了递归函数的定义，我们再来写方法就会容易很多

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

//插入元素`e`到 以 `node` 为根节点的 BST 中，并且返回根节点
private Node add(Node node, E e){
    if (node == null) {
        size++;
        return new Node(e);
    }
    if(e.compareTo(node.e) < 0){
        //插入左子树中，并返回根节点，然后接在 node.left
        node.left=add(node.left, e);
    }else if (e.compareTo(node.e) > 0) { //注意不要写 else, 前面没有对相等的元素做判断
        //插入右子树中，并返回根节点，然后接在 node.right
        node.right=add(node.right, e);   
    }
    return node;
}

还是那句话，写递归函数，不要纠结于函数的每一步是如何去进行，如何去得到结果的，从全局出发，只要搞清楚递归函数的定义，按照函数的定义来写代码，最后思考一下边界，最后的代码就一定是正确的！

这个边界的思考，其实也很简单，就比如上面的这个结束条件，我们不用去考虑一步步直到递归终结时是什么情况，我们思考一下极端的边界情况（其实这就是终结的情况），root 为 null，还没有初始化，BST 还是空的，这个时候 add 元素，其实想都不用想，肯定是直接把这个 e 作为根节点返回就 ok 了，所以很自然的就写出了终止条件

查找

查找相比于上面的添加，会简单很多，可以很容易的写出代码

//查询操作
public boolean contains(E e){
    if (e==null) {
        return false;
    }
    return contains(e,root);
}

private boolean contains(E e,Node root){
    if (root==null) {
        return false;
    }
    if (e.compareTo(root.e)==0) {
        return true;
    }
    return e.compareTo(root.e)<0?contains(e,root.left):contains(e,root.right);
}

这里我为了简洁写了三目，不熟悉的可以改成 if，整体时间复杂度依然是O(logN) ，比线性表的查找会快很多！

遍历

老生常谈的话题，这个在我之前的 LeetCode-二叉树里面也做过了，这里再翻出来看看，其实重点是想把后序遍历给搞清楚了，之前一直挺迷糊的

前序遍历

递归写法

//前序遍历，递归
public void preorderTravelRecur(){
    preorderTravel(root);
}

private void preorderTravel(Node root){
    if (root==null) {
        return;
    }
    System.out.print(root.e+" ");
    preorderTravel(root.left);
    preorderTravel(root.right);
}

非递归写法

//前序遍历，非递归实现
public void preorderTravelNoRecur(){
    Stack<Node> stack=new Stack<>();
    Node cur=root;
    while( cur!=null || !stack.isEmpty()){
        while(cur!=null){
            System.out.print(cur.e+" ");
            stack.push(cur);
            cur=cur.left;
        }
        cur=stack.pop();
        cur=cur.right;
    }
}

注意这里并不是经典的前序遍历方式，是按照 “模板” 来的，首先我们考虑栈里面存的是什么，这里的栈里面存的实际上是 左子树的左边 的集合，这里我不知道咋描述，画个图吧

图中绿色部分就是我所说的左子树的左边的集合，整个栈的入栈顺序就是从左往右，从上到下，依次的将这些“左边” 入栈，并且在没有左子树，也就是遍历到叶子节点的时候开始出栈，然后切换成当前出栈的节点的右子树，将右子树的左子树的左边重复前面的过程继续入栈出栈，我们要考虑的就是在什么时候访问节点！

细心的同学肯定已经发现了，其实这里进栈顺序和出栈顺序，分别对应的就是这颗树前序遍历和中序遍历！！！所以我们就只需要在进栈和出栈的时候，进行访问节点的操作，就可以完成前序和后序遍历

中序遍历

递归写法

//中序遍历，递归
public void inorderTravelRecur(){
    inorderTravel(root);
}

private void inorderTravel(Node root){
    if (root==null) {
        return;
    }
    inorderTravel(root.left);
    System.out.print(root.e+" ");
    inorderTravel(root.right);
}

非递归写法

结合上面的分析，我们也可以很容易的得出非递归的中序遍历的写法

//中序遍历，非递归
public void inorderTravelNoRecur(){
    Stack<Node> stack=new Stack<>();
    Node cur=root;
    while( cur!=null || !stack.isEmpty()){
        while(cur!=null){
            stack.push(cur);
            cur=cur.left;
        }
        cur=stack.pop();
        System.out.print(cur.e+" ");
        cur=cur.right;
    }
}

后序遍历

递归写法

//后序遍历，递归
public void postorderTravelRecur(){
    postorderTravel(root);
}

private void postorderTravel(Node root){
    if (root==null) {
        return;
    }
    postorderTravel(root.left);
    postorderTravel(root.right);
    System.out.print(root.e+" ");
}

非递归写法

这里的非递归写法就不一样了，比前两种要复杂

//后序遍历，非递归
public void postorderTravelNoRecur(){
    Stack<Node> stack=new Stack<>();
    Node cur=root,lastNode=null;
    while(cur!=null || !stack.isEmpty()){
        while(cur!=null){
            stack.push(cur);
            cur=cur.left;
        }
        cur=stack.peek();//查看栈顶元素
        //如果右子树为空或者右节点已经访问过，则当前节点出栈，并记录 lastNode
        if (cur.right==null || lastNode==cur.right) { 
            System.out.print(cur.e+" ");
            stack.pop();
            lastNode=cur;
            //为了下一次能直接查看栈顶元素
            //cur 的使命其实已经结束了，cur 和它的孩子都已经访问了，下一次直接从栈顶取，不然就死循环了
            cur=null; 
        }else{
            cur=cur.right;
        }
    }
}

其实不管是什么遍历，对于这个模板来说，栈的轨迹都是一样的，只不过访问节点的时机有所不同，蓝色线条代表审查的顺序，红色辅助的代表出栈部分，右边对应的就是遍历过程中栈的变化，和对应结果的变化，对照这个图再分析下就很清楚了。

如果觉得实在是不好理解也可以换用下面的方式

public void postorderTravelNoRecur2() {
    Stack<Node> stack=new Stack<>();
    stack.push(root);
    Node lastNode=null;
    while(!stack.isEmpty()){
        //取栈顶元素
        Node cur=stack.peek();
        //左右子树都为空，或者上一个访问的节点是当前节点的子节点就输出该节点
        if ( (cur.left==null && cur.right ==null) || 
             (lastNode!=null &&(cur.left==lastNode || cur.right==lastNode))){
            stack.pop();
            System.out.print(cur.e+" ");
            lastNode=cur;
        }else{
            if (cur.right!=null) {
                stack.push(cur.right);
            } if (cur.left!=null) {
                stack.push(cur.left);
            }  
        } 
    }
}

这种方式相比上面就好理解多了，左右子树都为空，或者上一个访问的节点是当前节点的子节点，就可以输出该节点了，注意添加的时候是逆序添加的，这样就可以保证先访问左节点，再访问右节点，最后访问根节点

层次遍历

递归写法

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    helper(res, root, 0);
    return res;
}

private void helper(List<List<Integer>> res, TreeNode root, int depth) {
    if (root == null) return;
    //需要增加一层
    if (res.size() == depth) res.add(new LinkedList<>());
    res.get(depth).add(root.val);
    helper(res, root.left, depth + 1);
    helper(res, root.right, depth + 1);
}

非递归写法

经典的 BFS

//层次遍历
public void levelorderTravel(){
    Queue<Node> queue=new LinkedList<>();
    queue.add(root);
    while(!queue.isEmpty()){
        int count=queue.size();
        while(count>0){
            Node node=queue.poll();
            System.out.print(node.e+" ");
            if (node.left!=null) {
                queue.add(node.left);
            }
            if (node.right!=null) {
                queue.add(node.right);
            }
            count--;
        }
    }
}

其实关于前中后序的遍历方式，还有很多，我这里主要记录的是模板的思路，其实还有一种很🐂🍺的做法，模拟系统栈的方式，具体可以参考我之前的 LeetCode 二叉树这里就不多解释了

取整

向下取整（floor）

public E floor(E e){
    Node node=floor(root,e);
    return node!=null?node.e:null;
}

public Node floor(Node root,E e){
    if (root==null) {
        return null;
    }
    int temp=e.compareTo(root.e);
    if (temp==0) {
        return root;
    }
    if (temp<0) { //root.e > e, 求小于 e 的值，一定在左边
        return floor(root.left,e);
    }
    //tmep>0 e>root.e
    Node node=floor(root.right,e);
    return node!=null?node:root;
}

向上取整（ceiling）

public E ceiling(E e){
    Node node=ceiling(root,e);
    return node!=null?node.e:null;
}

public Node ceiling(Node root,E e){
    if (root==null) {
        return null;
    }
    int temp=e.compareTo(root.e);
    if (temp==0) {
        return root;
    }
    if (temp>0) { //root.e<e, 求的是最后大于 root.e 的元素，一定在右边
        return ceiling(root.right,e);
    }
    //tmep<0 e<root.e
    Node node=ceiling(root.left,e);
    return node!=null?node:root;
}

这两个函数还是挺有用的，比如这个题 220-存在重复元素-III 通过率只有 25%的 mid 题。

获取第 K 大

获取第 k 大（从 0 开始）的元素，如果左子树节点数小于k，则第 k 大的元素肯定在右子树，同时我们可以直接排除size(left)+1 个元素（加上根节点）。

然后直接在右子树中继续搜索 getKth(root.right,k-size(left)-1) ，只有当左子树刚好 k 个元素的时候，根节点就是我们要找的Kth

public E getKth(int k){
    if (k>=size || k<0) {
        return null;
    }
    return getKth(root,k).e;
}

public Node getKth(Node root,int k){
    if (root==null) {
        return root;
    }
    int temp = childSize(root.left);
    if (temp>k) {
        return getKth(root.left,k);
    }
    if (temp<k) {
        return getKth(root.right,k-temp-1);
    }
    return root;
}

这里其实我的实现是有问题的，我的时间复杂度是O(NlogN)！！！！主要是childSize()时间复杂度是 O(N) 不是 O(1)，在《算法 4》中这个实现的时间复杂度就是 O(1)，书上在定义的 Node 的时候给 Node 加了一个 count 属性，用来记录每个节点的子节点数（包括自己），在每次 add 和 delete 的时候动态的维护这个 count，这样最后求子节点数的操作时间复杂度就是 O(1) 的了，那个版本的我也实现了一下，但是我没有在这篇文章中这样写（主要是懒得改），而且这也不是重点，感兴趣可以去看看 BSTWithCount 主要就是要注意操作 count 的时机

这里既然没有 count 数组，那么其实就不应该这样求，应该直接中序遍历，求第 K 大，时间复杂度 O(N)

Rank()

其实是上面的逆过程，如果根节点等于 key，那么直接返回左子树的键总数；如果 key 小于根节点，就继续去左子树中递归找，如果大于根节点，返回size(left)+1加上它在右子树中的rank()

public int getRank(E e){
    return getRank(root,e);
}

public int getRank(Node root,E e){
    if (e.compareTo(root.e)<0) { //e<root.e
        return getRank(root.left,e);
    }
    if (e.compareTo(root.e)>0) {
        return getRank(root.right,e)+childSize(root.left)+1;
    }
    return childSize(root.left);
}

Max&Min

没啥好说的

//求最大值，递归比较优雅
public E getMax(){
    return getMax(root).e;
}

public Node getMax(Node root){
    if (root.right==null) {
        return root;
    }
    return getMax(root.right);
}

//求最小值
public E getMin(){
    return getMin(root).e;
}

public Node getMin(Node root){
    if (root.left==null) {
        return root;
    }
    return getMin(root.left);
}

删除

删除应该来说是 BST 中里面比较复杂的一个操作了，我们先从简单的开始

删除最值

//删除最小的键
public void deleteMin(){
    root=deleteMin(root);
}
//删除 node 为头节点的树中的最小值，并返回头节点
private Node deleteMin(Node node){
    if (node.left==null) {
        return node.right;
    }
    node.left=deleteMin(node.left);
    return node;
}

//删除最大的键
public void deleteMax(){
    root=deleteMax(root);
}

private Node deleteMax(Node node){
    if (node.right==null) {
        return node.left;
    }
    node.right=deleteMax(node.right);
    return node;
}

递归函数定义为删除 node 为头节点的树中的最小值，并返回头节点，删除最小值实际上就是删除二叉树最左边的节点，所以我们递归的删除 node.left 就 ok，当 node.left 为空的时候返回 node.right，这样前面节点的 left 就接在了 node.right 上，就达到了删除的作用

删除任意值

//删除任意的键
public void delete(E e){
    root=delete(root,e);
}

//删除以 node 为首的 BST 中，值为 e 的节点并且返回根节点
private Node delete(Node node,E e){
    if (node==null) {
        return null;
    }
    if (e.compareTo(node.e)>0) { //e>root.e
        node.right=delete(node.right,e);
    }else if (e.compareTo(node.e)<0) {
        node.left=delete(node.left,e);
    }else{ //e==root.e
        if (node.left==null) { //如果没有左子树就返回右子树
            return node.right;
        }
        if (node.right==null) { //如果没有右子树就返回左子树
            return node.left;
        }
        Node delNode=node;
        //有左右子节点都有
        node=getMin(node.right); //用右子树的最小值填补删除的元素的空位
        //删除对应的右子树的最小值，然后连接起来
        node.right=deleteMin(delNode.right);
        node.left=delNode.left;
    }
    return node;
}

这里文字的描述比较无力，画个图就清晰明白了，核心的思想就是利用右子树中的最小值填补待删除节点

当然这里其实也是有坑的，主要就是连最后两句

//删除对应的右子树的最小值，然后连接起来
node.right=deleteMin(delNode.right);
node.left=delNode.left;

这里的两句话是不能交换的，如果我们交换了两句话的位置，那么我们下一步删除最小值就会出现问题，我们希望的是删除右子树中最小的 node 节点，结果你先把待删除节点的 left 接到了 node 的左边，这样的话 node 就不再是 delNode.right 中的最小值，最后结果可能就会成这个样子，成了一个闭环！！！

所以最后的结果肯定是不对的，其实这一点书上并没有提到，我也是在做这道题删除节点的时候写反了，才发现这个问题，感兴趣可以去试试

其实这样的删除时一种很随机的做法，虽然能正确的删除元素，但是并没有考虑树的对称性，关于树的对称性，我们后面再来研究

代码地址

BST.java

BSTTest.java

BSTWithCount.java

目录

二分搜索树

二分搜索树

基本结构

添加

查找

遍历

前序遍历

递归写法

非递归写法

中序遍历

递归写法

非递归写法

后序遍历

递归写法

非递归写法

层次遍历

递归写法

非递归写法

取整

向下取整（floor）

向上取整（ceiling）

获取第 K 大

Rank()

Max&Min

删除

删除最值

删除任意值

代码地址