【数据结构】Set和Map（常用方法、手动实现）_set map

目录

一、基本概念

二、二叉搜索树

三、手动实现

总结

---

一、基本概念

        Map和set是一种专门用来进行搜索的容器或者数据结构，其搜索的效率与其具体的实例化子类有关。Set我们可以理解为集合，Map我们可以理解为字典。其中Set继承自collection接口，Map独立存在。Set中的基本元素为Key。Map中的基本元素为Key-value对。无论在Set还是在Map中，Key的值都不允许重复。

        Map和Set可以通过什么来实现呢？我们也可以通过List来实现，但是我们发现效率太低，于是我们引出两种经典的数据结构以实现Set和Map。分别是二叉搜索树（Binary Search Tree）和哈希表（Hash Table）。其中二叉搜索树我们比较熟悉。

Set接口：

对于Set的两种实现方式比较

Map接口：

对于Map的两种实现方式的比较

二、二叉搜索树

二叉搜索树满足如下性质：

        1、若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

        2、 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

        3、它的左右子树也分别为二叉搜索树

三、手动实现

        我们自定义一个TreeNode类方便我们手动实现，我们只是对一些简单的基础功能进行实现,实现的结果如下：

package set_map.set.treeSet;
 
public class TreeNode {
    int key;
    TreeNode left;
    TreeNode right;
 
    public TreeNode(int key) {
        this.key = key;
    }
 
    @Override
    public String toString() {
        return "TreeNode{" +
                "key=" + key +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
}

package set_map.set.treeSet;
 
public class BSTree {
    private TreeNode root=null;
 
    public boolean contains(int dest){
        TreeNode cur=root;
        while (cur!=null){
            if(cur.key==dest){
                return true;
            }else if(cur.key<dest){
                cur=cur.right;
            }else{
                cur=cur.left;
            }
        }
        return false;
    }
 
 
    //给定顺序不同，得到的搜索树的结构也不同
    public boolean add(int dest){
        TreeNode treeNode = new TreeNode(dest);
        TreeNode parent=null;//定义一个节点用于记录双亲结点
 
        if(root==null){
            root=treeNode;
            return true;
        }
 
        TreeNode cur=root;
        while(cur!=null){
            if(cur.key==dest){
                return false;
            }else if(dest<cur.key){
                parent=cur;
                cur=cur.left;
            }else {
                parent=cur;
                cur=cur.right;
            }
        }
        //此时到了null的位置，是插入的时候了
        if(dest<parent.key){
            parent.left=treeNode;
        }else {
            parent.right=treeNode;
        }
        return true;
    }
    public boolean remove(int key){
        TreeNode parent=null;
        TreeNode cur=root;
        while(cur!=null){
            if(cur.key==key){
                deleteKey(parent,cur,key);
                return true;
            }else if(key< cur.key){
                parent=cur;
                cur=cur.left;
            }else{
                parent=cur;
                cur=cur.right;
            }
        }
        return false;
    }
 
    private void deleteKey(TreeNode parent,TreeNode node, int key) {
        if(node.left==null){
            if(node==root){
                root=root.right;
            }else if(node==parent.left){
                parent.left=node.right;
            }else{
                parent.right=node.right;
            }
        }else if(node.right==null){
            if(node==root){
                root=root.left;
            }else if(node==parent.left){
                parent.left=node.left;
            }else {
                parent.left=node.left;
            }
        }else{
            replaceDelete(parent,node);
        }
    }
 
    private void replaceDelete(TreeNode parent, TreeNode node) {
        TreeNode canparent=node;
        TreeNode candidate =node.left;
        while (candidate.right!=null){
            canparent=candidate;
            candidate=candidate.right;
        }
        //将值进行替换
        node.key= candidate.key;
        //删除候选人的节点
        if(canparent==node){
            canparent.left=candidate.left;
        }else {
            canparent.right=null;
        }
    }
 
    public static void main(String[] args) {
        int[] keys={9,7,13,21,5,8,16,32,4,0,1,6,2,3};
        BSTree bsTree = new BSTree();
        for (int key : keys) {
            bsTree.add(key);
        }
        System.out.println(true);
        int[] re={2,6,7,13,9};
        for (int i : re) {
            bsTree.remove(i);
        }
        System.out.println(true);
    }
 
}

总结

        这些方法一定要牢记于心。