Java 【数据结构】 TreeSet&TreeMap（二叉搜索树详解）【神装】

🩹3. 插入操作

🩼4. 查找操作

🩺5. 删除操作*

🩻6. 遍历操作

🪒7.性能分析

🪥二.TreeSet

🧽1. 定义

🧻 2.操作

🪣3. Set主要特性

🫧4. TreeSet的内部实现

🛒5. 应用场景

🧯三.TreeMap

🧹1.定义

🪤2.操作

🧷3.Map的主要特性

🧿4. TreeMap的内部实现

🪬5.应用场景

🗿四.总结与反思

💉 一.二叉搜索树

首先我们要知道TreeSet/TreeMap底层都采用的都是一种二叉搜索树（也叫自平衡二叉树），因此我们先来了解一下二叉搜索树。

对于他的学习若之前没有了解的可以参考：Java 【数据结构】二叉树（Binary_Tree）【神装】

🩸1. 定义

二叉搜索树（Binary Search Tree，简称BST），是一种特殊的二叉树，它具有以下性质：

每个节点都有一个键（Key）和两个指向其他节点的指针（左子指针和右子指针）。
任意节点的左子树中的所有键都小于该节点的键。
任意节点的右子树中的所有键都大于该节点的键。
左右子树也都是二叉搜索树。
不存在键值相等的节点。
$Java 【数据结构】 TreeSet&TreeMap（二叉搜索树详解）【神装】,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,操作,没有,程序,第3张$
在Java中，我们可以这样定义一个二叉搜索树：
```
public class BinarySearchTree {
    private class Node {
        int val;
        Node left;
        Node right;
        
        Node(int val) {
            this.val = val;
            left = null;
            right = null;
        }
    }
    
    private Node root;
    
    // 构造函数、插入方法、查找方法、删除方法等...
}
```
💊2. 基本操作
二叉搜索树支持以下基本操作：
- 插入（Insert）：向树中插入一个新节点，保持树的二叉搜索性质。
- 查找（Search）：在树中查找一个特定的节点。
- 删除（Delete）：从树中删除一个节点，并保持树的二叉搜索性质。
- 遍历（Traverse）：对树进行遍历，常用的遍历方式有前序、中序和后序遍历。
  接下来我们详细介绍一下它的各个操作，因为后续二叉树本身是数据结构中一个很关键的知识点，像红黑树，AVL树等等，我们需要牢牢掌握！
  🩹3. 插入操作
  插入操作的步骤如下：
  1. 创建新节点。
  2. 比较新节点的键与根节点的键：
    - 如果新节点的键小于根节点的键，则将新节点插入到根节点的左子树中。
    - 如果新节点的键大于根节点的键，则将新节点插入到根节点的右子树中。
  3. 如果插入点是空，则直接在新位置插入新节点。
  4. 如果插入点非空，则递归地在相应子树中进行插入操作。
  $Java 【数据结构】 TreeSet&TreeMap（二叉搜索树详解）【神装】,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,操作,没有,程序,第4张$
  代码:
```
 /**
     * 插入一个元素
     * @param key
     */
    public void insert(int key) {
        TreeNode node=new TreeNode(key);
        //若该搜索树为空，则直接作为根节点；
        if (root==null){
            root=node;
        }
        TreeNode cur=root;
        TreeNode parent=null;
        while(cur!=null){
            if (cur.keykey){
                parent = cur;
                cur=cur.left;
            }else{
                return ;
            }
        }
        if (parent.key>key){
            parent.left=node;
        }else{
            parent.right=node;
        }
    }
```
  🩼4. 查找操作
  查找操作的步骤如下：
  1. 从根节点开始比较。
  2. 如果查找的键小于当前节点的键，则递归地在左子树中查找。
  3. 如果查找的键大于当前节点的键，则递归地在右子树中查找。
  4. 如果找到节点，则返回该节点。
  5. 如果没有找到，则返回null。
  $Java 【数据结构】 TreeSet&TreeMap（二叉搜索树详解）【神装】,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,操作,没有,程序,第5张$
  代码
```
 //查找key是否存在
    public TreeNode search(int key) {
        TreeNode cur =root;
        while(cur!=null){
            if (cur.keykey){
                cur=cur.left;
            }else{
                return cur;
            }
        }
        return null;
    }
```
  🩺5. 删除操作*
  设待删除结点为 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
  - 需要使用替换法进行删除，即在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题
    代码
```
//删除key的值
    public boolean remove(int key) {
        TreeNode cur =root;
        TreeNode parent=null;
        while(cur!=null){
            if (cur.key>key){
                parent=cur;
                cur=cur.left;
            }else if (cur.key
```