BST二叉搜索树

二叉搜索树（BST）

定义

二叉搜索树又叫二叉排序树，相对于普通的二叉树，二叉搜索树规定父节点的左子节点小于父节点，右子节点大于父节点，满足这个条件的二叉树就是二叉搜索树。由于自带顺序这一特性，二叉搜索树在查找元素时的时间复杂度理想情况下可以达到O(logn)，极端情况下才是O(n)，因此二叉查找树主要体现了基础的查找树思路。

插入

在插入一个元素时，首先与根节点比较，元素如果大于根节点，便继续向根节点的右子树移动，如果元素小于根节点，就向根节点左子树移动，并以当前节点为父节点重新计算，直到找到空位以插入。基于这个思路，我们可以通过循环或者递归来实现。

删除

二叉搜索树的删除比较复杂，我们想一下以下三种情况：
1 被删除节点无子节点

33待删除.png

2 被删除节点只有左子树或右子树

45待删除.png
3 被删除节点同时有左右子树
48待删除.png
对于第一种情况，我们可以直接删除该节点；
删除33.png

第二种情况，删除该节点之后，由于节点的左右子树肯定满足该节点所处的条件（大于或小于该节点的父节点），这样删除策略就是直接使用该节点的左子树或右子树替代该节点；

删除45.png
第三种情况，删除掉该节点之后，节点的左右子树要怎么处理？我们应该寻找一个满足该节点条件的叶子节点来替代该节点，从而不改变树的结构。那么如何寻找这样的一个节点呢？这里引入另一个定义：

• 节点的直接前驱和直接后继
  直接前驱指的是在中序遍历中处于节点前一位的节点，直接后继指的是后一位的节点，因为这两个节点和该节点相邻，正好可以用来替代被删除节点。
  经过一番推导（过程略），我们可以知道，左右子树都存在的节点的直接前驱就是节点的左子树的最外层的右节点，直接后继就是节点的右子树节点。通常我们会使用直接前驱的方式来替代该节点，因为如果使用直接后继，会导致右子树结构变动，还需要维护右子树的结构。

  
  删除48.png

实现

public class BinarySearchTree {
    public BinarySearchTree left;
    public BinarySearchTree right;
    public Integer val;

    public BinarySearchTree(BinarySearchTree left, BinarySearchTree right, Integer val) {
        this.left = left;
        this.right = right;
        this.val = val;
    }

    public static void insert(BinarySearchTree root, int x) {
        BinarySearchTree cursor = root;
        BinarySearchTree lp = null;
        BinarySearchTree rp = null;
        while (cursor != null) {
            if (cursor.val < x) {
                lp = cursor;
                cursor = cursor.right;
                rp = null;
            } else {
                rp = cursor;
                cursor = cursor.left;
                lp = null;
            }
        }
        cursor = new BinarySearchTree(null, null, x);
        if (lp != null) {
            lp.right = cursor;
        }
        if (rp != null) {
            rp.left = cursor;
        }
    }

    public static void delete(BinarySearchTree node, int x) {
        if (node == null) {
            return;
        }
        BinarySearchTree cursor = node;
        BinarySearchTree parent = cursor;
        boolean isLeft = false;
        // 找到x所在位置
        while (cursor != null && cursor.val != x) {
            if (cursor.val < x) {
                parent = cursor;
                isLeft = false;
                cursor = cursor.right;
            } else {
                parent = cursor;
                isLeft = true;
                cursor = cursor.left;
            }
        }
        if (cursor != null) {
            // 左子树为空，直接将右子树覆盖待删除节点
            if (cursor.left == null) {
                if (cursor.right != null) {
                    cursor.val = cursor.right.val;
                    cursor.left = cursor.right.left;
                    cursor.right = cursor.right.right;
                } else {
                    if (isLeft) {
                        parent.left = null;
                    } else {
                        parent.right = null;
                    }
                }
            } else {
                // 从待删除节点左子树开始，寻找直接后继
                BinarySearchTree come = cursor.left;
                BinarySearchTree comeParent = cursor;
                while (come.right != null) {
                    comeParent = come;
                    come = come.right;
                }
                // 将直接后继的值赋给待删除节点
                cursor.val = come.val;
                // 如果直接后继没有左子树，直接删除直接后继
                if (come.left == null) {
                    comeParent.right = null;
                } else {
                    // 直接后继左子树不为空，将直接后继的左子树，覆盖直接后继
                    comeParent.right = come.left;
                }
            }
        }
    }
}