数据结构之Map/Set讲解+硬核源码剖析（一）-阿里云开发者社区

💕"活着是为了活着本身而活着"💕

作者：Mylvzi

文章主要内容：数据结构之Map/Set讲解+硬核源码剖析

一.搜索树

1.概念

二叉搜索树又叫二叉排序树，他或者是一颗空树，或者是具有以下性质的树

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

简单来说，二叉搜索树上存储结点的值满足以下条件:

left < root < right

注意：二叉搜索树中不能存在两个相同的值

2.二叉搜索树的操作及其实现

前提准备

static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    private TreeNode root = null;

1.查询操作(search)

根据二叉搜索树的性质很容易实现查询的操作

代码实现：

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

2.插入操作(insert)

让cur走到合适的位置，再去判断parent.val 与 val的关系，进行插入

画图分析：

代码实现：

// insert
    public boolean insert(int val) {
        TreeNode newNode = new TreeNode(val);
        // 空树直接插入
        if (root == null) {
            root = newNode;
            return true;
        }
        // 保留cur的根节点
        TreeNode parent = null;
        TreeNode cur = root;
        while(cur != null) {
            parent = cur;
            if(cur.val < val) {
                cur = cur.right;
            } else if(cur.val > val){
                cur = cur.left;
            }else {
                // 二叉搜索树中不能存在两个相同的数字
                return false;
            }
        }
        // 此时cur就是要插入的位置
        if(parent.val < val) {
            parent.right = newNode;
        }else {
            parent.left = newNode;
        }
        return true;
    }

3.删除操作(remove)

如果你要删除的cur的结点只有一个子节点，此时删除十分容易

但是如果你想要删除的结点有两个子节点，处理稍微麻烦，因为在你删除cur结点之后，还要保证剩下的结点也满足二叉搜索树的性质，这里采用“替罪羊”法解决删除拥有两个子节点的结点

思路分析：

我现在想要删除90这个结点，但是删除之后谁来替代这个结点呢？

根据二叉搜索树的性质，90看作根节点，则他一定比左树的所有结点的值大，比右树所有结点的值小

我们需要找一个合理的结点去替换90，替换之后仍要满足二叉搜索树的性质，这个合理的结点可以通过两个方法实现

找左树的最大值

找右树的最小值

现在以找右树的最小值为例演示

代码实现

public void remove(int val) {
        TreeNode parent = null;
        TreeNode cur = root;
        while(cur != null) {
            parent = cur;
            if (cur.val < val) {
                cur = cur.right;
            } else if (cur.val > val) {
                cur = cur.left;
            }else {
                removeNode(parent,cur);
                return;
            }
        }
    }
    private void removeNode(TreeNode parent, TreeNode cur) {
        // 注意此时cur就是我要删除的数据
        // cur的左树为空
        if(cur.left == null) {
            if (cur == root) {
                root = cur.right;
            } else if (cur == parent.left) {
                parent.left = cur.right;
            }else {
                parent.right = cur.right;
            }
        } else if (cur.right == null) {
         // cur的右树为空
            if (cur == root) {
                root = cur.left;
            } else if (cur == parent.left) {
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        }else {// 都不等于Null
            // 找右树的最小值
            // 使用替罪羊法
/*            TreeNode targetParent = cur;
            TreeNode target = cur.right;
            // 找右树的最小值  直到某个结点的left为null  则此节点就是右树最左边的结点  也就是右树的最小值
            while (target.left != null) {
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;
            if (target == targetParent.left) {
                targetParent.left = target.right;
            }else {
                targetParent.right = target.right;
            }*/
            // 求左树的最大值
            TreeNode tp = cur;
            TreeNode t = cur.left;
            while (t.right != null) {
                tp = t;
                t = t.right;
            }
            // 此时t就是左树的最大值
            cur.val = t.val;
            // 重写链接
            if (t == tp.left) {
                tp.left = t.left;
            }else {
                tp.right = t.left;
            }
        }
    }

3.性能分析

对于二叉搜索树来说，进行插入/删除操作都要先进行查询，所以二叉搜索树的性能取决于查询的效率最好情况是二叉树是一颗完全二叉树最坏情况则是二叉树是一颗单分支的二叉树

问题：如果是单分支的情况，二叉搜索树的效率会变得很低，如何解决这种问题呢？

4.和 java 类集的关系

TreeMap 和 TreeSet 即 java 中利用搜索树实现的 Map 和 Set；实际上用的是红黑树，而红黑树是一棵近似平衡的二叉搜索树，即在二叉搜索树的基础之上 + 颜色以及红黑树性质验证，关于红黑树的内容后序再进行讲解。

二.搜索

1.概念和场景

Map和Set是一种专门用来进行“搜索”的数据结构/容器，其搜索效率取决于其具体实现的子类

我们之前其实也学过搜索

1.直接遍历最粗暴的搜索方法时间复杂度0(N)

2.二分查找需要序列是有序的时间复杂度O(logN)

上述查找适合静态的查找，即在查找的过程中不会进行插入和删除的操作，但是现实中的很多查找都需要动态的进行插入和删除，比如：

1.根据学号查成绩

2.根据通讯录名字查找电话号

3.根据身高找女朋友(bushi)

......

在查找的过程中可能会出现插入和删除的操作，Map和Set就是用于动态的插入和删除的搜索容器

2.搜索的模型

搜索的方式其实有两种，一种是直接在一大堆数据中寻找，另一种是根据对应关系进行查找（比如你需要先找到通讯录的名字，才能根据通讯录的名字找到你要寻找的手机号），我们一般把搜索的数据称为关键字Key，key对应的称为值Value，将其称之为Key-value的键值对

1. 纯 key 模型(找有没有)

在词典中找单词

2. Key-Value 模型(找对应关系)

梁山好汉的江湖绰号：每个好汉都有自己的江湖绰号

学号对应着你的名字

而Map中存储的是Key-Value 模型，Set中存储的是纯 key 模型

三.Map的使用

先放一张Java中和数据结构有关的类的图

1.概念

Map是一个接口类，不能直接实例化对象，如果要使用，需要根据实现他的类来实例化具体的对象，比如TreeMap(底层是红黑树)和HashMap(底层是哈希表)

2.常用方法

1.put

在Map中添加key与value的映射关系

// 根据实现Map的类TreeMap来实例化一个对象
        Map<String,Integer> map = new TreeMap<>();
        // Put方法
        // 设置  单词--出现的次数  这样的一个key与value的映射
        map.put("apple",14);
        map.put("bank",15);
        map.put("cat",17);

注意：

1.我们知道，TreeMap的底层是一颗红黑树，存储的时候是使用结点来存储元素的，它实际上存储的是Key-Value的映射关系，实际上Map中存在一个内部类Map.Entry,用于表示映射关系

2.既然TreeMap是一种红黑树，那他在存入数据的时候必然要排序，排序的根据是Key

2.get方法

存在两个get方法但都是为了返回key对应的value值

System.out.println(map.get("apple"));// 输出14
        System.out.println(map.get("bank"));// 输出15
        System.out.println(map.get("cat"));// 输出17
        // get时进行判断 如果Map中含有传入的key就返回其value  没有则返回其默认值(解某些题很有用)
        System.out.println(map.getOrDefault("apple", 100));// 输出14  因为Map中含有apple
        System.out.println(map.getOrDefault("Dog", 100));// 输出100  因为Map中不含有Dog

数据结构之Map/Set讲解+硬核源码剖析（二）+https://developer.aliyun.com/article/1413571

数据结构之Map/Set讲解+硬核源码剖析（一）

一.搜索树

1.概念

2.二叉搜索树的操作及其实现

前提准备

1.查询操作(search)

2.插入操作(insert)

3.删除操作(remove)

3.性能分析

4.和 java 类集的关系

二.搜索

1.概念和场景

2.搜索的模型

三.Map的使用

1.概念

2.常用方法

1.put

在Map中添加key与value的映射关系

注意：

2.get方法

热门文章

最新文章

相关课程

相关电子书