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

前言：

语言只是工具。

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

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

---

 

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

TreeSet和TreeMap还有HashSet和HashMap 

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

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

图示：

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

 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.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;
            }
        }
    }

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

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

1.4 性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。 对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度 的函数，即结点越深，则比较次数越多。 但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

 最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：logN

最差情况下，二叉搜索树退化为单支树，其平均比较次数为：N/2

问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，都可以是二叉搜索树的性能最佳？ 

这就引入了TreeMap 和 TreeSet 。

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

本节先讲这么多，由于时间关系，后续会继续更新这篇文章。