二叉搜索树 【数据结构】

二叉搜索树是一种特殊的二叉树

左子树中的值都小于根节点，右子树中的值都大于根节点
故：中序遍历结果就会得到一个有序序列

最大的特点：就是能够高效的进行查找元素
查找过程类似于二分查找：先从根节点出发开始比较，看待查找元素是小于根节点还是大于根节点，进一步决定是去左子树中找，还是右子树
查找的时间复杂度：O(N) (单支树)

解决方案：采取更加平衡的二叉搜索树，AVL树(绝对平衡)，红黑树

1.插入元素

其实和查找非常相似，需要先找到待插入元素的合适位置
若树为空树，直接插入为根节点即可

对于二叉搜索树来说，插入元素的时候，元素都是被插入到叶子节点上的

2.查找元素

也很简单，简单画图理解即可~

3.删除元素

需要考虑很多种不同的情况：

• 情况1：待删除元素是父节点的左子树
  且，待删除元素左子树为空，右子树非空

直接让父节点的左子树，指向待删除元素的右子树即可

• 情况2：待删除元素是父节点的右子树
  待删除元素的左子树为空，右子树非空

直接让父节点的右子树，指向待删除节点的右子树即可

• 情况3：待删除元素是父节点的左子树
  待删除元素左子树非空，右子树为空

直接将父节点的左子树，指向待删除结点的左子树即可

• 情况4：待删除元素是父节点的右子树
  待删除元素左子树非空，右子树为空

直接将父节点的右子树，指向待删除结点的左子树即可

• 情况5：待删除元素是父节点的左子树
  待删除元素左 / 右子树均非空

• 情况6：待删除元素是父节点的右子树
  待删除元素左 / 右子树均非空

代码实现：

public class BinarySearchTree {
    public static class Node{
        int key;
        Node left;
        Node right;

        public Node(int key) {
            this.key = key;
        }
    }
    // 根节点  root 为null，表示为空树
    private Node root = null;

    //查找操作
    public Node find(int key){
        // 查找 key 是否存在
        // 若存在，返回对应的Node
        // 若不存在，返回null
        Node cur = root;
        while (cur != null){
            if(key < cur.key){
                //此时去左子树中找
                cur = cur.left;
            }
            else if(key > cur.key){
                // 此时去右子树找
                cur = cur.right;
            }
            else{
                // 找到了
                return cur;
            }
        }
        // key 不存在
        return null;
    }

    //插入操作
    public boolean insert(int key){
        // 二叉搜索树中 是不允许存在相同 key 的元素的
        // 若新插入的 key 重复，就插入失败，返回 false
        // 插入成功 返回 true

        // 空树判断
        if(root == null){
            root = new Node(key);
            return true;
        }
        //先找到合适的位置,再去插入元素
        Node cur = root;
        // 让 parent 始终指向 cur 的父节点
        Node parent = null;
        while (cur != null){
            if(key < cur.key){
                parent = cur;
                cur = cur.left;
            }
            else if(key > cur.key){
                parent = cur;
                cur = cur.right;
            }
            else{
                // 某个元素和待插入元素值相同
                return false;
            }
        }
        // 循环结束，cur 指向 null
        // 当前元素就要插到 parent 子树的位置上
        if(key < parent.key){
            parent.left = new Node(key);
        }
        else{
            parent.right = new Node(key);
        }
        return true;
    }

    //删除操作
    public boolean remove(int key){
        // 先找到 待删除节点的位置,再进行删除
        // 找到待删除元素后，再来判断是那种情况
        Node cur = root;
        Node parent = null;
        while (cur != null){
            if(key < cur.key){
                parent = cur;
                cur = cur.left;
            }
            else if(key > cur.key){
                parent = cur;
                cur = cur.right;
            }
            else{
                // 找到了 待删除元素,就是 cur 指向的元素
                removeNode(parent,cur);
                return true;
            }
        }
        return false;
    }
    private void removeNode(Node parent, Node cur) {
        // 1.待删除元素左子树为空
        if(cur.left == null){
            //1.1 若要删除节点为 root
            if(cur == root){
                root = cur.right;
            }
            //1.2 cur 是 parent 的左子树
            else if(cur == parent.left){
                parent.left = cur.right;
            }
            //1.3 cur 是 parent 的右子树
            else{
                parent.right = cur.right;
            }
        }
        // 2.待删除元素右子树为空
        else if(cur.right == null){
            //2.1 若要删除节点为 root
            if(cur == root){
                root = cur.left;
            }
            //2.2 cur 是 parent 的左子树
            else if(cur == parent.left){
                parent.left = cur.left;
            }
            //2.3 cur 是 parent 的右子树
            else{
                parent.right = cur.left;
            }
        }
        // 3.待删除节点有两个子树
        else{
            // ①找到右子树的最小元素 / 左子树的最大元素(替罪羊)
            Node goatParent = cur;
            Node scapeGoat = cur.right;
            while (scapeGoat.left != null){
                goatParent = scapeGoat;
                scapeGoat = scapeGoat.left;
            }
            // 当循环结束时，scapeGoat 指向了右子树中的最小值
            // ②将找到的元素，赋值给待删除节点
            cur.key = scapeGoat.key;
            // ③删除替罪羊节点
            // 替罪羊节点一定没有左子树
            if(scapeGoat == goatParent.left){
                goatParent.left = scapeGoat.right;
            }
            else{
                goatParent.right = scapeGoat.right;
            }
        }
    }
}

插入测试：

public static void main(String[] args) {
    BinarySearchTree tree = new BinarySearchTree();
    tree.insert(9);
    tree.insert(5);
    tree.insert(2);
    tree.insert(7);
    tree.insert(3);
    tree.insert(6);
    tree.insert(8);
    //为了查看树的结构，可以打印树的先序和中序遍历结果
    tree.preOrder(tree.root);
    System.out.println();
    tree.inOrder(tree.root);
}

// 先序遍历
public void preOrder(Node root){
    if(root == null){
        return;
    }
    System.out.print(root.key + " ");
    preOrder(root.left);
    preOrder(root.right);
}
// 中序遍历
public void inOrder(Node root){
    if(root == null){
        return;
    }
    inOrder(root.left);
    System.out.print(root.key + " ");
    inOrder(root.right);
}

输出结果：

根据先 、中序遍历结果，来还原二叉树，得到：

调试代码：

得到的结果和我们图上还原的结果一样