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

登神长阶

 第八神装 TreeSet

   第九神装  TreeMap

目录

💉 一.二叉搜索树

🩸1. 定义

💊2. 基本操作

🩹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中，我们可以这样定义一个二叉搜索树：

  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. 如果插入点非空，则递归地在相应子树中进行插入操作。

    

    代码: 

     /**
         * 插入一个元素
         * @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。

    

    代码

     //查找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