数据结构-Java Map 和 Set-1-阿里云开发者社区

数据结构-Java Map 和 Set-1

2024-05-23 27

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 数据结构-Java Map 和 Set

前言

Set接口是继承与Collection的，而Map是独立的一个接口。

其中Set的实现类有：

TreeSet
HashSet

Map实现的类有：

HashMap
TreeMap

（HashSet和HashMap底层是一个哈希表，TreeSet和TreeMap底层是一棵搜索树（红黑树））

TreeMap和TreeSet，即java中利用搜索树实现的Map和Set，实际上应用的就是红黑树，而红黑树是一棵近似平衡的二叉搜索树（在二叉搜索树的基础上+上颜色以及红黑树性质的验证）

搜索树

定义树：

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

概念

二叉搜索树，也被称为二叉排序树（可能为一棵空树），具备以下性质：

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

二叉搜索树

中序遍历二叉搜索树，得到的结果是一组有序的数据。

查找

如上图，首先假设上图的二叉树已经存在，且根节点为root，要查找的值为val，如果root为空就返回null，定义一个cur节点来遍历这棵树，如果root.val > val，根据二叉搜索树的性质，就去root结点的左子树去找，否则就去右子树找，如果找到了（cur.val == val），就然后cur结点，直到cur == null，就返回空的结点。

/**
    *  查找二叉搜索树val的值
    *  val
    *
    */
    public TreeNode find(int val) {
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val == val) {
                return cur;
            } else if (cur.val < val) {
                cur = cur.right;
            } else {
                cur = cur.left;
            }
        }
        return null;
 
    }

插入

搜索树满足概念中性质a,b,c三点，如果要插入一个val。值首先定义一个cur节点，如果root == null就 new一个值为val的节点newNode，并将root置为这个节点（root == newNode）

如果root != null，就进行搜索，如果root.val > val，就去左边继续搜索，如果root.val < val就去右边搜索。如果当前cur结点的左和右都为null，则直接比较插入即可。

例如在上图中插入6，12 > 6，就去12的左树插入，12的左树的根值为5 < 6，所以去5这个节点的右树插入，其右树跟为9 > 6，又因为val为9这个结点的左和右都为null。所以直接在这个结点的左侧插入。

// 不使用parent结点
public void insert1(int val) {
        if (root == null) {
            root = new TreeNode(val);
            return;
        }
        TreeNode newNode = new TreeNode(val);
        TreeNode cur = root;
        while (cur.left != null && cur.right != null) {
            if (newNode.val > cur.val) {
                cur =cur.right;
            }else {
                cur =cur.left;
            }
        }
        if (newNode.val > cur.val) {
            cur.right = newNode;
        }else {
            cur.left = newNode;
        }
    }

当然也可以使用parent结点来记录cur的上一个结点，如果cur == null的时候，就可以找到cur的上一个结点parent，并在parent这个结点上插入。

public void insert2(int val) {
        if (root == null) {
            root = new TreeNode(val);
            return;
        }
        TreeNode newNode = new TreeNode(val);
        TreeNode cur = root;
        TreeNode parent = null;
        while (cur != null) {
            parent = cur;
            if (cur.val < val) {
                cur =cur.right;
            }else {
                cur = cur.left;
            }
        }
        if (parent.val < val) {
            parent.right = newNode;
        }else {
            parent.left = newNode;
        }
    }

删除

二叉搜索树

如何删除

设cur节点为当前要删除的节点，parent为cur结点的父节点。

如果 cur.left == null。

a.cur == root && root.left == null ，则root = cur.right。

b.cur != root && cur == parent.left ，则 parent.left = cur.right

c.cur != root && cur == parent.right，则 parent.right = cur.right

如果cur.right == null，则原理同上。

cur == root，则root = root.left
cur != root && cur == parent.left，则 parent.left = cur.left
cur != root && cur == parent.right，则 prent.right = cur.left

图略

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

某个二叉搜索树

假设有这样一棵二叉搜索树。root为根节点，cur为当前将要被删除的节点。

该如何删除？

需要使用替换法进行删除，即在它的右子树中寻找中序下的第一个结点(值最小)，用它的值填补到被

删除节点中，再删除这个最小值节点即可。

首先，你需要找出cur节点和cur的父节点：

实现

public void remove(int val) {
    TreeNode cur = root;
    TreeNode parent = null;
    while(cur != null){
        if (cur.val == val) {
            removeNode(parent, cur);
            break;
        }else if (cur.val > val) {
            parent = cur;
            cur = cur.left;
        }else {
             parent = cur;
            cur = cur.right;   
        }
    }
}

然后需要在cur的右树里面找到其最小值，这个最小值无非就是cur的右子树的第一个结点，或者是右子树上左树的最左的一个端点。找到这个节点之后，将其删除。

然后综上所述的cur.left == null 或者 cur.right == null的情况来完成removeNode这个方法；

private void removeNode(TreeNode parent, TreeNode cur) {
        // 要删除的节点的左子树为空
        if (cur.left == null) {
            if (cur == root) {
                root = cur.right;
            }else if (parent.left == cur) {
                parent.left = cur.right;
            }else {
                parent.right = cur.right;
            }
        // 要删除的节点的右子树为空
        }else if (cur.right == null) {
            if (cur == root) {
                root = cur.left;
            }else if (parent.left == cur) {
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        }else/* suggests that:cur.left != null && cur.right != null */ {
            TreeNode target = cur.right;
            TreeNode targetParent = cur;
            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;
            }
        }
    }