一文搞懂——搜索树

小灰灰 2024-04-01 16:48 149阅读 0赞

目录

1.搜索树的定义

2.插入操作

3.查找操作

4.删除操作

5.性能分析

6.完整代码

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

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

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

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

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

0741d2a1f38e4477a5e5fd406b950c32.png

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

  2. cur 是 root ，则 root = cur.right

  3. cur 不是 root ， cur 是 parent.left ，则 parent.left = cur.right

  4. cur 不是 root ， cur 是 parent.right ，则 parent.right = cur.right

  5. cur.right == null

  6. cur 是 root ，则 root = cur.left

  7. cur 不是 root ， cur 是 parent.left ，则 parent.left = cur.left

  8. cur 不是 root ， cur 是 parent.right ，则 parent.right = cur.left

  9. cur.left != null && cur.right != null

    需要使用替换法 进行删除，即在它的右子树中寻找中序下的第一个结点 ( 关键码最小 ) ，用它的值填补到被删除节点中，再来处理该结点的删除问题。

    public void remove(int v){

    1.         Node cur = root;
    2.         Node parent = null;
    3.         while(cur != null){
    4.             if(cur.val == v){
    5.                 removeNode(cur,parent);
    6.                 break;
    7.             }else if(cur.val > v){
    8.                 parent = cur;
    9.                 cur = cur.left;
    10.             }else {
    11.                 parent = cur;
    12.                 cur = cur.right;
    13.             }
    15.         }
    16.     }
    17.     public void removeNode(Node cur,Node parent){
    18.         if(cur.left == null){
    19.             if(cur == root){
    20.                 root = cur.right;
    21.             }else if(cur == parent.left){
    22.                 parent.left = cur.right;
    23.             }else{
    24.                 parent.right = cur.right;
    25.             }
    26.         }else if(cur.right == null){
    27.             if(cur == root){
    28.                 root = cur.left;
    29.             }else if(cur == parent.left){
    30.                 parent.left = cur.left;
    31.             }else {
    32.                 parent.right = cur.left;
    33.             }
    34.         }else {
    35.             Node targetParent = cur;
    36.             Node target = cur.right;
    37.             while(target.left != null){
    38.                 targetParent = target;
    39.                 target = target.left;
    41.             }
    42.             cur.val = target.val;
    43.             if(target == targetParent.left){
    44.                 targetParent.left = target.right;
    45.             }else {
    46.                 targetParent.right = target.right;
    47.             }
    49.         }
    50.     }

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;
  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.     }
  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.     }
  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.                 }
  72.             }
  73.         }
  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;
  100.                 }
  101.                 cur.val = target.val;
  102.                 if(target == targetParent.left){
  103.                     targetParent.left = target.right;
  104.                 }else {
  105.                     targetParent.right = target.right;
  106.                 }
  108.             }
  109.         }
  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);
  9.         System.out.println();
  10.         Node node = binarySearchTree.Serach(8);
  11.         System.out.println(node.val);
  13.         binarySearchTree.insert(15);
  14.         binarySearchTree.inOrder(binarySearchTree.root);
  16.         System.out.println();
  17.         binarySearchTree.remove(9);
  18.         binarySearchTree.inOrder(binarySearchTree.root);
  20.     }

运行结果：

74d3413e640b4dc78ba06a6112bb2c03.png

发表评论

表情：
评论列表 （有 0 条评论，149人围观）

还没有评论，来说两句吧...

相关阅读

    相关 一文搞懂static（一）

    一、聊一聊static与JVM Java 把内存分为栈内存和堆内存，其中栈内存用来存放一些基本类型的变量、数组和对象的引用，堆内存主要存放一些对象。在 JVM 加载一个类的

    怼烎@怼烎@/ 0 赞/ 192 阅读

    相关 一文搞懂ThreadPoolExecutor

    前言 线程池是Java中使用较多的并发框架，合理使用线程池，可以：降低资源消耗，提高响应速度，提高线程的可管理性。 本篇文章将从线程池简单原理，线程池的创建，线程池执行

    迈不过友情╰迈不过友情╰/ 0 赞/ 186 阅读

    相关 一文搞懂 Raft 算法

    一文搞懂Raft算法 正文 raft是工程上使用较为广泛的强一致性、去中心化、高可用的分布式协议。在这里强调了是在工程上，因为在学术理论界，最耀眼的还是大名鼎鼎的Pax

    不念不忘少年蓝@不念不忘少年蓝@/ 0 赞/ 425 阅读

    相关 一文搞懂DDD

    最近看了很多和DDD相关的内容，这篇文章对DDD做一个总结，希望可以通过这篇文章不但知道什么是DDD，而且还可以知道如何实施DDD 一、什么是DDD DDD（领域驱动设

    ゝ一世哀愁。ゝ一世哀愁。/ 0 赞/ 315 阅读