• 一文搞懂——搜索树

    目录

    1.搜索树的定义

    2.插入操作

    3.查找操作

    4.删除操作

    5.性能分析

    6.完整代码

    二叉搜索树又称为二叉排序树，它具有以下性质 

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

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

    3.它的左右子树也为二叉搜索树

    以下就是一个二叉搜索树，每个节点的左节点小于父亲节的，右节点大于父亲节点。

    1.搜索树的定义

    1. class Node{
    2.     public int val;
    3.     public Node left;
    4.     public Node right;
    5.     public Node(int val){
    6.         this.val = val;
    7.     }
    8. }

    2.插入操作

            首先判断根节点是否为空，为空直接添加，不为空的话就利用“每个节点的左节点小于父亲节的，右节点大于父亲节点”这个特点进行判断，并进行插入。

    1. public boolean insert(int v){
    2.         if(root == null){
    3.             root = new Node(v);
    4.             return true;
    5.         }
    6.         Node parent = null;
    7.         Node cur = root;
    8.         while(cur != null){
    9.             if(cur.val > v){
    10.                 parent = cur;
    11.                 cur = cur.left;
    12.             }else if (cur.val == v){
    13.                 return false;//不能有相同的数据
    14.             }else {
    15.                 parent = cur;
    16.                 cur = cur.right;
    17.             }
    18.         }
    19.         Node node = new Node(v);
    20.         if(parent.val > v){
    21.             parent.left = node;
    22.         }else if(parent.val < v){
    23.             parent.right = node;
    24.         }
    25.         return true;
    26.     }

    3.查找操作

            对于某个元素的查找，利用“每个节点的左节点小于父亲节的，右节点大于父亲节点”，进行判断，直至找到目标节点。

    1. public Node Serach(int v){
    2.         Node cur = root;
    3.         while(cur != null) {
    4.             if (cur.val > v) {
    5.                 cur = cur.left;
    6.             } else if (cur.val == v) {
    7.                 return cur;
    8.             } else {
    9.                 cur = cur.right;
    10.             }
    11.         }
    12.         return null;
    13.     }

    4.删除操作

    删除操作情况及其复杂。

            设待删除结点为 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
            需要使用替换法 进行删除，即在它的右子树中寻找中序下的第一个结点 ( 关键码最小 ) ，用它的值填补到被删除节点中，再来处理该结点的删除问题。 
    1. public void remove(int v){
    2.             Node cur = root;
    3.             Node parent = null;
    4.             while(cur != null){
    5.                 if(cur.val == v){
    6.                     removeNode(cur,parent);
    7.                     break;
    8.                 }else if(cur.val > v){
    9.                     parent = cur;
    10.                     cur = cur.left;
    11.                 }else {
    12.                     parent = cur;
    13.                     cur = cur.right;
    14.                 }
    15.  
    16.             }
    17.         }
    18.         public void removeNode(Node cur,Node parent){
    19.             if(cur.left == null){
    20.                 if(cur == root){
    21.                     root = cur.right;
    22.                 }else if(cur == parent.left){
    23.                     parent.left = cur.right;
    24.                 }else{
    25.                     parent.right = cur.right;
    26.                 }
    27.             }else if(cur.right == null){
    28.                 if(cur == root){
    29.                     root = cur.left;
    30.                 }else if(cur == parent.left){
    31.                     parent.left = cur.left;
    32.                 }else {
    33.                     parent.right = cur.left;
    34.                 }
    35.             }else {
    36.                 Node targetParent = cur;
    37.                 Node target = cur.right;
    38.                 while(target.left != null){
    39.                     targetParent = target;
    40.                     target = target.left;
    41.  
    42.                 }
    43.                 cur.val = target.val;
    44.                 if(target == targetParent.left){
    45.                     targetParent.left = target.right;
    46.                 }else {
    47.                     targetParent.right = target.right;
    48.                 }
    49.  
    50.             }
    51.         }

    5.性能分析

            插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
            对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
            最优情况：二叉搜索树为完全二叉树，其平均比较次数为 log(2)(N);
            最差情况：二叉搜索树为单支树，其平均比较次数为 N/2。

    6.完整代码

    1. //节点定义
    2. class Node{
    3.     public int val;
    4.     public Node left;
    5.     public Node right;
    6.     public Node(int val){
    7.         this.val = val;
    8.     }
    9. }
    10. public class BinarySearchTree {
    11.     public Node root = null;
    12.  
    13.     //搜索操作
    14.     public Node Serach(int v){
    15.         Node cur = root;
    16.         while(cur != null) {
    17.             if (cur.val > v) {
    18.                 cur = cur.left;
    19.             } else if (cur.val == v) {
    20.                 return cur;
    21.             } else {
    22.                 cur = cur.right;
    23.             }
    24.         }
    25.         return null;
    26.     }
    27.  
    28.     //插入操作
    29.     public boolean insert(int v){
    30.         if(root == null){
    31.             root = new Node(v);
    32.             return true;
    33.         }
    34.         Node parent = null;
    35.         Node cur = root;
    36.         while(cur != null){
    37.             if(cur.val > v){
    38.                 parent = cur;
    39.                 cur = cur.left;
    40.             }else if (cur.val == v){
    41.                 return false;//不能有相同的数据
    42.             }else {
    43.                 parent = cur;
    44.                 cur = cur.right;
    45.             }
    46.         }
    47.         Node node = new Node(v);
    48.         if(parent.val > v){
    49.             parent.left = node;
    50.         }else if(parent.val < v){
    51.             parent.right = node;
    52.         }
    53.         return true;
    54.     }
    55.  
    56.         //删除操作
    57.         public void remove(int v){
    58.             Node cur = root;
    59.             Node parent = null;
    60.             while(cur != null){
    61.                 if(cur.val == v){
    62.                     removeNode(cur,parent);
    63.                     break;
    64.                 }else if(cur.val > v){
    65.                     parent = cur;
    66.                     cur = cur.left;
    67.                 }else {
    68.                     parent = cur;
    69.                     cur = cur.right;
    70.                 }
    71.  
    72.             }
    73.         }
    74.  
    75.         //删除操作的具体实现
    76.         public void removeNode(Node cur,Node parent){
    77.             if(cur.left == null){
    78.                 if(cur == root){
    79.                     root = cur.right;
    80.                 }else if(cur == parent.left){
    81.                     parent.left = cur.right;
    82.                 }else{
    83.                     parent.right = cur.right;
    84.                 }
    85.             }else if(cur.right == null){
    86.                 if(cur == root){
    87.                     root = cur.left;
    88.                 }else if(cur == parent.left){
    89.                     parent.left = cur.left;
    90.                 }else {
    91.                     parent.right = cur.left;
    92.                 }
    93.             }else {
    94.                 Node targetParent = cur;
    95.                 Node target = cur.right;
    96.                 while(target.left != null){
    97.                     targetParent = target;
    98.                     target = target.left;
    99.  
    100.                 }
    101.                 cur.val = target.val;
    102.                 if(target == targetParent.left){
    103.                     targetParent.left = target.right;
    104.                 }else {
    105.                     targetParent.right = target.right;
    106.                 }
    107.  
    108.             }
    109.         }
    110.  
    111. //中序遍历
    112.     public void inOrder(Node root){
    113.         if(root == null) return;
    114.         inOrder(root.left);
    115.         System.out.print(root.val+" ");
    116.         inOrder(root.right);
    117.     }
    118. }
    测试用例： 
    1. public static void main(String[] args) {
    2.         int[] array = {10,8,19,3,9,4,7};
    3.         BinarySearchTree binarySearchTree = new BinarySearchTree();
    4.         for (int i = 0;i < array.length;i++){
    5.             binarySearchTree.insert(array[i]);
    6.         }
    7.         binarySearchTree.inOrder(binarySearchTree.root);
    8.  
    9.         System.out.println();
    10.         Node node = binarySearchTree.Serach(8);
    11.         System.out.println(node.val);
    12.  
    13.         binarySearchTree.insert(15);
    14.         binarySearchTree.inOrder(binarySearchTree.root);
    15.  
    16.         System.out.println();
    17.         binarySearchTree.remove(9);
    18.         binarySearchTree.inOrder(binarySearchTree.root);
    19.  
    20.     }

    运行结果：

     

  • 相关阅读:
    .NET混合开发解决方案7 WinForm程序中通过NuGet管理器引用集成WebView2控件
    网络安全漏洞分析之远程代码执行
    Linux 学习笔记(5-6)
    QClipboard
    Qt之Windows Server 2012 R2不支持openssl
    Linux 网络之ss
    远程工作面临减薪，该何去何从？谷歌员工陷入焦虑
    wininet,winhttp,xmlhttprequest,各版本区别 《转》
    mac系统安装搭载Windows系统虚拟机方法教程
    mysql中的三大日志
  • 原文地址：https://blog.csdn.net/m0_57950108/article/details/127776071