• Java——二叉搜索树


    概念

    可以是一颗空树,其每一个节点的左孩子一定比该节点的val值小,右孩子一定比该节点val值小。
    这样的话,当我们中序遍历这个二叉树时,就可以得到升序的序列了

    查找操作

    由于二叉搜索树的独特的性质,因此在查找某一个元素的时间复杂度是o(log N),我们可以定义一个cur的节点从根开始遍历,如果cur节点的值比要找的值小就往cur的右子树走,反之则往cur的左子树走
    具体代码实现如下:

    public TreeNode search(int key){
        TreeNode cur = root;
        while(cur != null){
            if(cur.val == key){
                return cur;
            } else if(cur.val < key){
                cur = cur.right;
            } else {
                cur = cur.left;
            }
        }
        return null;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    插入操作

    当该树为空树时,那么我们直接让root变成要插入的节点即可
    若该树不是空树,那么由于二叉树的性质,我们要插入的节点一定是位于叶子节点上的,那么我们直接进行遍历操作,使cur到一个特定的分支,然后根据叶子节点的val大小确定是插入到叶子节点的左还是右。

    需要注意的是,由于cur回遍历到null,因此需要parent存储cur遍历到null时的前一个节点的位置,以方便于插入操作

    具体代码实现:

    public boolean insert(int key){
       TreeNode node = new TreeNode(key);
       if(root == null){
           root = node;
           return true;
       }
       TreeNode cur = root;
       TreeNode parent = null;
       while(cur != null){
           if(cur.val < key){
               parent = cur;
               cur = cur.right;
           } else if(cur.val > key){
               parent = cur;
               cur = cur.left;
           } else {
               return false;
           }
       }
       if(parent.val > key){
           parent.left = node;
       } else {
           parent.right = node;
       }
       return true;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    删除操作

    由于二叉树的独特的性质,因此当删除任意一个节点时会影响整个树的结构,因此需要分情况进行讨论,以下讨论cur是要删除的节点,root是根节点,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
      方法一:cur的值和cur的左子树的最大值进行交换,然后将左子树的最大值所在节点进行删除,由于是最大值,因此一定该节点没有右孩子,因此可以按照上面的方法进行删除
      方法二:和上述方法类似,不过是找的cur的右子树中的最小值,然后交换该节点和cur节点的val值,由于是最小值,因此一定没有左孩子,因此还是用上述方法删除

    代码实现:

    public void remove(int key){
       TreeNode cur = root;
       TreeNode parent = cur;
       while(cur != null){
           if(cur.val == key){
               removeNode(cur,parent);
               return;
           } else if(cur.val < key){
               parent = cur;
               cur = cur.right;
           } else {
               parent = cur;
               cur = cur.left;
           }
       }
    
    }
    
    private void removeNode(TreeNode cur, TreeNode parent) {
       if(root == null){
           return;
       }
       if(cur.left == null){
           if(cur == root){
               root = root.right;
           } else if(cur == parent.left){
               parent.left = cur.right;
           } else {
               parent.right = cur.right;
           }
       } else if (cur.right == null){
           if(cur == root){
               root = root.left;
           } else if(cur == parent.left){
               parent.left = cur.left;
           } else {
               parent.right = cur.left;
           }
       } else {
           TreeNode target = cur.right;
           TreeNode targetParent = cur;
           while(target.left != null){
               targetParent = target;
               target = target.left;
           }
           cur.val = target.val;
           if(targetParent.left == target){
               targetParent.left = target.right;
           } else {
               targetParent.right = target.right;
           }
       }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53

    总结

    虽然二叉树看起来搜索效率很高,可以达到log N,但是如果这棵树建的不好,有可能成了一颗单分支的树,因此搜索效率会大大减少,因此我们平时用的就是红黑树——即一颗平衡的二叉搜索树,在之后的章节会进行讲解。

  • 相关阅读:
    python环境移植,制作可以移植的python环境
    C语言经典算法学习-4
    之所以选择天津工业大学,因为它是双一流、报考难度适宜,性价比高!天津工业大学计算机考研考情分析!
    Java的接口以及接口与抽象类区别
    redux-获取导航标题案例(+react-intl 国际化)
    入门力扣自学笔记118 C++ (题目编号1413)
    点成方案丨点成生物PCR实验解决方案
    二、MyBatis-Plus 主键策略
    全球与中国无线上网卡和行业市场需求及投资前景分析报告2022-2028年
    【Java数据结构】详解Stack与Queue(四)
  • 原文地址:https://blog.csdn.net/m0_60867520/article/details/125890316