二叉搜索树的基本操作 || TreeMap和TreeSet介绍

目录

前言：

二叉搜索树的插入

代码实现

二叉搜索树的查找

代码实现

二叉搜索树的删除

代码实现

TreeMap介绍

源码展现

 TreeSet介绍

源码展现

 小结：

---

前言：

😄现在很多地方都需要去查找某个数据，那么查找的效率就显得尤为重要了。二叉搜索树是一颗左孩子比父亲小，右孩子比父亲大的一棵树。那么在这个基础上查找某个数据，一次比较就可以排除一半数据，效率是相当高的。

二叉搜索树的插入

😯拿到一个数据，首先判断根节点是否为空，如果为空就往根节点处插入。否则依次向下比较，比它大就往右走，比它小都往左走。直到走到叶子节点，就可以插入了。这个时候需记录这个叶子节点，然后去判断往右边还是左边插入数据。

代码实现

 public boolean insert(int val) {
        if(root == null) {
            TreeNode newNode = new TreeNode(val);
            root = newNode;
            return true;
        }
        TreeNode cur = root;
        TreeNode prev = null;
        while(cur != null) {
            if(val > cur.val) {
                prev = cur;
                cur = cur.right;
            }else if(val < cur.val) {
                prev = cur;
                cur = cur.left;
            }else {
                return false;
            }
        }
        //最终可能在左面和右面插入
        TreeNode newNode = new TreeNode(val);
        if(val < prev.val) {
            prev.left = newNode;
        }else {
            prev.right = newNode;
        }
        return true;
    }

二叉搜索树的查找

😃定义cur去遍历二叉树。首先判断cur处位置的val值是否和需查找值一致，如果一致则直接返回这个节点，否则就去判断cur该往左还是右走。如果cur为空，则说明二叉树遍历完成，也没有找到目标值，返回null。

代码实现

  public TreeNode Search(int val) {
        TreeNode cur = root;
        while(cur != null) {
            if(val > cur.val) {
                cur = cur.right;
            }else if(val < cur.val) {
                cur = cur.left;
            }else {
                return cur;
            }
        }
        return null;
    }

二叉搜索树的删除

🎈我们可以想到要删除树中的某一个节点，需连将这个节点的上一个节点和下一个节点连接起来。所以定义前后指针prev，cur去遍历树。当cur找到后去删除这个节点。

🎈删除树中的某一个节点，如果这个节点的左右都不为空，或者这个节点的左树为空，又或者这个节点的右树为空。它们的删除方法都不相同。因此我们将这些可能都枚举出来，逐个去判断。

🎈左树为空的情况，如果要删除的节点为根节点，直接调整根节点为它的右子树。如果要删除的节点在上一个节点的右边，直接连接上一个节点的right到这个节点的right。如果要删除的节点在上一个节点的左边，连接上一个节点left到这个节点的right。

🎈右树为空的情况，如果要删除的节点为根节点，直接调整根节点为它的左子树。如果要删除的节点在上一个节点的右边，直接连接上一个节点的right到这个节点的left。如果要删除的节点在上一个节点的左边，连接上一个节点left到这个节点的left。

🎈如果要删除节点的左右都不为空，不论怎样去连接都会打破树的结构，因此提出替罪羊式删除法。在这个节点左树中找到最大值，或者右树中找到最小值，就可以替换这个节点的值，保证这颗树依然维持二叉搜索树的结构特点。那么就只需要删除左树中的最大值或者右树中的最小值（替罪羊）。当在右树中找到最小的值，替换完成后。删除这个节点时，这个节点可能在上一个节点的左边，也可能在右边（右树只有一个节点）。在左边就直接连接上一个节点的left到这个节点right。在右边就直接连接上一个节点right到这个节点的right。

代码实现

public boolean remove(int val) {
        TreeNode cur = root;
        TreeNode prev = null;
        while(cur != null) {
            if(val > cur.val) {
                prev = cur;
                cur = cur.right;
            }else if(val < cur.val) {
                prev = cur;
                cur = cur.left;
            }else {
                removeNode(prev, cur);
                return true;
            }
        }
        return false;
    }
 private void removeNode(TreeNode prev, TreeNode cur) {
        //删除分为三种情况
        //左树为空  右树为空  左右树都不为空
        if(cur.left == null) {
            //可能删除根节点  可能删除prev的右节点  可能删除prev的左节点
            if(cur == root) {
                root = root.right;
            }else if(cur == prev.right) {
                prev.right = cur.right;
            }else {
                prev.left = cur.right;
            }
        }else if(cur.right == null) {
            if(cur == root) {
                root = root.left;
            }else if(cur == prev.right) {
                prev.right = cur.left;
            }else {
                prev.left = cur.left;
            }
 
        }else {
            //替罪羊式删除法
            //左树中找最大的/右树中找最小的
            //就可以替换要被删除的元素，接下来只需删除左面最大或者右面最小的节点
            TreeNode target = cur.right;
            TreeNode targetParent = cur;
            while(target.left != null) {
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;
            //最终要删除的节点可能在targetParent左和右
            if(target == targetParent.left) {
                targetParent.left = target.right;
            }else {
                targetParent.right = target.right;
            }
        }
    }

TreeMap介绍

🪖TreeMap的底层是一颗红黑树，红黑树是建立在二叉搜索树结构上的。由于搜索树在极端情况下它的单分支会很长，这样就会增加查找的效率。在这个基础上提出的AVL树，将它的单分支进行旋转。由于可能旋转的次数会很多，又在这个基础上提出了红黑树。

🪖TreeMap中数据存储，是按照键值对的方式去存储（key - val）。由于搜索树中不会存在相同的数据，即TreeMap中的key是唯一的。如果插入相同的key会更新其原来key的val值，那么相应的key是不可以修改的，但是val值可以修改。

🪖TreeMap是实现map接口的，相对于Iterable接口这个接口是独立的。可以调用entrySet方法将TreeMap中的（key - val）取出来为Entry类型，存储到set集合当中去组织。也可以调用keySet或者values方法可以单独将key或者val取出来，分别存储到set集合或者collection集合当中去组织。

🪖由于TreeMap底层是红黑树，那么它的key是必须具有比较性。如果提供比较器优先调用比较器，否则实现Comparable接口重写compareTo方法。key不能为null，因为null无法比较，否则会抛NullPointerException异常。

源码展现

 

 

 

 TreeSet介绍

🤞TreeSet只存储key。它底层是用TreeMap实现的，只是所有的val值都是Object对象。TreeSet是实现set接口的，它是在Iterable接口下。

🤞那么相应的TreeSet底层也是红黑树，key值也就是唯一的，不可以添加相同的key。它的key也需具有可比较性。TreeSet具有天然去重的功能。

源码展现

 

 

 

 

 小结：

🐵在学习一些集合时，我们在理解的基础上可以去看一些源码，这样也会加深对其的理解性。