《Java初阶数据结构》----10.＜Map和Set---TreeSet和TreeMap&HashSet和HashMap ＞

用户11288958

发布于 2024-09-24 15:12:06

760

发布于 2024-09-24 15:12:06

前言：

大家好，我目前在学习java。我准备利用这个暑假，来复习之前学过的内容，并整理好之前写过的博客进行发布。如果博客中有错误或者没有读懂的地方。热烈欢迎大家在评论区进行讨论！！！喜欢我文章的兄弟姐妹们可以点赞，收藏和评论。如果感觉有所收获可以关注我呦。我会持续更新滴，望支持！！！！！！一起加油呀！！！！

语言只是工具。

决定你好不好找工作的是你的能力！！！！

学历本科及以上就够用了！！！！！！！！

本篇博客会讲解 Map/Set 及实际实现类 HashMap/TreeMap/HashSet/TreeSet 的使用 HashMap 和 HashSet 背后的数据结构哈希表的原理和简单实现

我们在回顾一下在JavaSE最后一篇说的集合类这个图。今天我们要详细讲的就是

TreeSet和TreeMap还有HashSet和HashMap

TreeSet和TreeMap其底层是一个红黑树。而红黑树的本质其实就是一颗特殊的二叉搜索树。

一、二叉搜索树（二叉排序树）

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

图示：

当我们对二叉搜索树进行中序遍历的时候。我们发现此时是有序的，中序（左根右）遍历结果。 0,1,2,3,4,5,6,7,8,9 如上就是一颗二叉搜索树。

1.1二叉搜索树的查找

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

定义一个当前节点等于root。在cur不为null的情况下。 ①如果要找的值小于于根节点。那么就进入左节点再去查找。 ②如果要找的值大于根节点。那么就进入右节点再去查找。找的值等于当前节点的值返回true。如果当cur为null没找到的话返回false。 我们可以看出查找的效率是很高的

1.2二叉树的插入

注：二叉搜索树的插入只会插入进叶子节点。

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

        if(root == null){
            root = new TreeNode(val);
            return true;
        }
        while (cur != null){
            if(cur.val < val){
                parent = cur;
                cur = cur.right;
            } else if (cur.val > val) {
                parent = cur;
                cur = cur.left;
            }else {
                return false;
            }
        }
        TreeNode node = new TreeNode(val);
        if(val < parent.val){
            parent.left = node;
        }else {
            parent.right = node;
        }
        return true;
    }

1.若根节点为空，那么直接新建一个节点存入val值，令root＝node。 2.如果跟节点不为空。我们想找到合适的位置插入，那么就跟查找类似。需要比较插入的值，与根节点比较。 ①如果插入的值小于根节点。那么进入左子树 ②如果插入的值大于根节点。那么进入右子树直到找到一个节点为空（cur == null时），那么此时。就可以插入这个节点。新建一个节点，放入val值。令当前空节点为新建节点。但是存在一个问题。我们需要连接节点，因此还需要知道插入位置的父亲节点才能进行插入因此我们需要多定义一个parent节点。每次cur节点移动的之前，令parent = cur。

1.3二叉树的删除（难点）

设待删除结点为 cur, 待删除结点的双亲结点为 parent。

分以下三种情况进行删除

1. cur.left == null

1. cur 是 root，则 root = cur.right
2. cur 不是 root，cur 是 parent.left，则 parent.left = cur.right
3. cur 不是 root，cur 是 parent.right，则 parent.right = cur.right

2. cur.right == null

1. cur 是 root，则 root = cur.left
2. cur 不是 root，cur 是 parent.left，则 parent.left = cur.left
3. cur 不是 root，cur 是 parent.right，则 parent.right = cur.left

3. cur.left != null && cur.right != null

需要使用替换法进行删除，即在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题

    public void 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;
            }
        }
    }

// 删除的逻辑 removeNode(parent,cur);

// 该元素不在二叉搜索树中
        if(null == cur){
            return false;
       }
 
        /*
        根据cur的孩子是否存在分四种情况
        1. cur左右孩子均不存在
        2. cur只有左孩子
        3. cur只有右孩子
        4. cur左右孩子均存在
       看起来有四种情况，实际情况1可以与情况2或者3进行合并，只需要处理是那种情况即可
        除了情况4之外，其他情况可以直接删除
        情况4不能直接删除，需要在其子树中找一个替代节点进行删除
        */
        // 请同学们根据上课掌握内容，完成删除的关键部分代码
        return true;
   }
}

代码后续会补充完整，并进行分析。