【数据结构】详解二叉搜索树及其实现

前言：

二叉搜索树是红黑树等的前身，掌握其操作和性质很重要。总结自用and分享。

目录

一、基本概念

二、其常见操作及其实现

1.定义节点

2.查找元素 

 3.插入元素

4.删除元素【难点】

5.判断是不是二叉搜索树

 三、性质分析

一、基本概念

        如下所示：对于所有节点都满足该性质：子树上所有节点的值都小于该节点的值。对于每个节点，右子树上所有节点的值都大于该节点的值。每个节点的左子树和右子树也是一个二叉搜索树。

其也叫二叉排序树，对其进行中序遍历可以得到排好序的序列。

二、其常见操作及其实现

1.定义节点

public class BinarySearchTree {
    private TreeNode root = null;//根节点


    // 定义节点
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
}

2.查找元素 

思想：

运用一个递归的思想：

1.先看看根节点是不是该元素，是的话，直接当前节点。

2.若不是，判断其位置，若该元素比根大，那就去右子树找（跳到1）。

3.若该元素比根小，那就去左子树找（跳到1）。

4.若遍历完所有节点都找不到，返回null。

代码实现：

public TreeNode search(int val) {
        TreeNode curRoot = root;//当前的双亲节点
        while (curRoot != null) {
            if (curRoot.val == val) {
                return curRoot;
            } else if (curRoot.val > val) {
                curRoot = curRoot.left;
            } else {
                curRoot = curRoot.right;
            }
        }
        return null;
    }

 3.插入元素

注意：二叉树的插入是不会破坏原有的结构的，插入元素，总是能找到合适的叶子节点插入，你们可以画图感受一下。

思想：

1.若该树为空，直接插入。

2.若树不为空：根据二叉树的性质，找到它的容身之处的双亲节点。

3.找到双亲节点之后，若比双亲节点大，插入其右边，若比双亲节点小，插入其左边。

代码实现：

    // 2.插入元素
    public boolean insert(int val) {

        // 如果根节点为空，直接插入，返回true
        if (root == null) {
            root = new TreeNode(val);
            return true;
        }

        TreeNode cur = root;
        TreeNode parent = null;

        while (cur != null) {
            if (val == cur.val) {
                System.out.println("值为" + val + "的节点已经存在");
                return false;
            } else if (val > cur.val) {
                parent = cur;
                cur = cur.right;
            } else {
                parent = cur;
                cur = cur.left;
            }
        }

        // 抵达该位置时，已经找到合适的插入位置的双亲节点：parent
        // 要判断一下插入哪一边
        if (val > parent.val) {
            parent.right = new TreeNode(val);
        } else {
            parent.left = new TreeNode(val);
        }
        return true;
    }

4.删除元素【难点】

注意：刚说的插入元素不会破坏原有的树结构，但是删除元素就可能不得不破坏原有的树结构了，毕竟要把某个在中间的元素搬走...

a:初步思路：

    先找到该节点和其双亲节点，若找不到该节点，返回false。若找到了该节点，再根据情况进行删除调整。

 public boolean remove(int val) {
        TreeNode cur = root;
        TreeNode parent = null;

        while (cur != null) {
            if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            } else if (cur.val > val) {
                parent = cur;
                cur = cur.left;
            } else {
                //找到要删除的元素和其双亲节点了
                removeNode(parent, cur);
                return true;
            }
        }
        System.out.println("删除失败，没找到值为"+val+"的节点");
        return false;
    }

 b:删除:(难点)

1. 删除叶子节点：直接删除。
2. 删除只有一边子节点的节点：用子节点替代该节点。（可涵盖情况1）
3. 删除有两个子节点的节点【难点所在】：找到该节点的中序后继节点，用它的值替换被删除节点的值，然后删除该中序后继节点，并把该中序后继节点的子节点继承过去。

 再捋一下删除的情况：

     情况1、2： 我们找到了要删除的节点和其双亲节点。上述的情况2是可以包含情况1的：叶子节点也可以视为只有一边子节点（实际是null）的节点，然后子节点（实际是null），替代原本的节点。但是有一种情况我们要特殊处理，那就是要删除的节点是根节点时（此时对parent修改，只是流动了parent，影响不了root），我们需要直接拿到root去修改指向。

      情况3： 删除有两个子节点的节点【难点所在】

      找到要删除节点的右子树的最左节点，我们因为是最左节点，该节点肯定没有左子树了。

        我们把最左节点的值直接覆盖到要删除的节点，原因：最左节点是要删除节点的右子树里最小的，把它放在要删除的节点处，既可以满足，右子树中所有元素比节点大，也可以满足本来左子树中所有元素比节点小。（天然，右子树中任一元素大于左子树中的）

        善后阶段：最左节点的值已经被拿去，应该要删掉。这时候就回到情况1、2的问题了，且最左节点肯定不是头结点，处理起来也更简单。

private void removeNode(TreeNode parent, TreeNode cur) {
        // 情况1：要删除的节点没有左子节点
        if (cur.left == null) {
            // 如果要删除的节点是根节点，则直接将根节点指向其右子节点
            if (cur == root) {
                root = cur.right;
            } else if (cur == parent.left) {
                // 如果要删除的节点是其父节点的左子节点，则更新父节点的左指针
                parent.left = cur.right;
            } else {
                // 如果要删除的节点是其父节点的右子节点，则更新父节点的右指针
                parent.right = cur.right;
            }
        }
        // 情况2：要删除的节点没有右子节点
        else if (cur.right == null) {
            // 如果要删除的节点是根节点，则直接将根节点指向其左子节点
            if (cur == root) {
                root = cur.left;
            } else if (cur == parent.left) {
                // 如果要删除的节点是其父节点的左子节点，则更新父节点的左指针
                parent.left = cur.left;
            } else {
                // 如果要删除的节点是其父节点的右子节点，则更新父节点的右指针
                parent.right = cur.left;
            }
        }
        // 情况3：要删除的节点有左右子节点
        else {
            // 找到要删除节点的右子树中的最左（最小）节点
            TreeNode t = cur.right;
            TreeNode tp = cur;
            while (t.left != null) {
                tp = t;
                t = t.left;
            }
            // 将最左节点的值赋值给要删除的节点
            cur.val = t.val;

            // 删除最左节点，更新其父节点的左指针或右指针
            if (tp.left == t) {
                tp.left = t.right;
            } else {
                tp.right = t.right;
            }
        }
    }

5.判断是不是二叉搜索树

OJ链接

a:带上下界的递归方法：

public boolean isValidBST(TreeNode root) {
        //(,)
        return isValidBST(root, null, null);
    }

    public boolean isValidBST(TreeNode root, Integer left, Integer right) {
        if (root == null) {
            return true;
        }

        if ((left != null && root.val <= left) || (right != null && root.val >= right)) {
            return false;
        }


        return isValidBST(root.left, left, root.val) && isValidBST(root.right, root.val, right);
    }

b：利用二叉搜索树中序遍历是有序的这个性质

//利用二叉树中序遍历是有序的性质
    //左右根
    static Integer pre = null;

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }

        if (!isValidBST(root.left)) return false;

        if (pre != null && root.val <= pre) {
            return false;
        }

        pre = root.val;

        return isValidBST(root.right);

    }

 三、性质分析

        由于二叉搜索树的特点，平均情况下，插入、查找和删除操作的时间复杂度都是 O(log⁡n)。但是，如果二叉搜索树退化成一条链表（例如插入有序数据），最坏情况下，操作时间复杂度会降到 O(n)。为了避免这种情况，实际应用中常使用平衡二叉搜索树（如AVL树、红黑树等）。