【数据结构】二叉搜索树的功能实现详解

2024-09-03 06:20

本文主要是介绍【数据结构】二叉搜索树的功能实现详解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 二叉搜索树
  • 查找
  • 插入
  • 删除
    • 找到要删除的节点
    • 删除节点
      • 1. 要删除节点的左孩子为空
      • 2. 要删除节点的右孩子为空
      • 3. 要删除的节点的左右孩子都不为空
    • 完整代码

二叉搜索树

二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:

  • 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
  • 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
  • 它的左右子树也分别为二叉搜索树image.png|545

其中序遍历是一颗有序的树

查找

二叉搜索树的查找效率非常高

  • 因为二叉搜索树的左边都比我小,右边都比我大
  • 要找比我小的树,就只需要在左树中找,直接最多可以去掉一半的数据
  • 每次到达一个根节点都可以一次性排除掉最多一半的数据

时间复杂度:

  • 最好情况下: O ( l o g N ) O(logN) O(logN)
  • 最坏情况下: O ( N ) O(N) O(N),单分支,将整棵树遍历完

因为这颗二叉搜索树是由一个一个节点构成的,所以先定义出节点

  • 左孩子
  • 右孩子
  • 节点的值
    并定义出头结点
public class BinarySearchTree {  static class TreeNode {  public int val;  public TreeNode left;  public TreeNode right;  public TreeNode(int val) {  this.val = val;  }   }  public TreeNode root = null;  
}

每次去看一下 curval 和我们要找的 key 的大小关系

  1. 如果 cur.val < key,那么就往右边走
  2. 如果 cur.val > key,那么就往左边走
  3. 如果 cur.val = key,那么就找到了|468
public TreeNode search(int key) {  TreeNode cur = root;  while(cur != null) {  if(cur.val < key) {  cur = cur.right;  } else if (cur.val > key) {  cur = cur.left;  }else  return cur;  }    return null;  
}

插入

所有的插入都是插入到了叶子节点

  1. 原来的树为空,则直接插入

  2. 当树不为空时
    若要找到需要插入到的叶子结点的位置,就需要定位到最后父亲节点的叶子结点为 null 的时候。但当 cur 走到叶子结点的时候,就找不到此叶子结点的父亲节点了,所以需要多一个 parent 节点,用来记录当前的父亲节点,好方便随时可以定位到目标叶子结点的父亲节点,后续通过父亲节点进行赋值操作

public void insert(int key) {  TreeNode node = new TreeNode(key);  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;  }    }    //此循环走完,parent 指向的节点就是需要插入的节点位置的父亲节点  if (parent.val > key) {  parent.left = node;  } else (parent.val < key) {  parent.right = node;  }
}
  • 值相同的时候,不能进行重复插入
  • while 循环结束,cur 指向要插入的叶子结点,parent 指向需要插入的节点的父亲节点
  • 之后对父亲节点和 key 进行比较,选择插入哪一边

删除

删除包含很多种情况

  1. 需要删除的节点的左孩子为空
  2. 需要删除的节点的右孩子为空
  3. 需要删除的节点的左右孩子都不为空

找到要删除的节点

首先需要找到需要删除的节点

public void remove(int key) {  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 {  //此时就是找到了要删除的节点  removeNode(parent,cur);  return;  }    }
}
  • 当执行到 else 的时候,就是找到要删除的节点了
  • 随后完善删除操作==> removeNode

删除节点

1. 要删除节点的左孩子为空

  1. curroot,则 root = cur.right image.png|214

  1. cur 不是 rootcurparent.left,则 parent.left = cur.rightimage.png|297

  1. cur 不是 rootcurparent.right,则 parent.right = cur.rightimage.png|365
// 1.当要删除的节点 cur 的左孩子为空  
if (cur.left == null) {  if (cur == root) {  // 1.1 要删除的 cur 为根节点  root = cur.right;  } else if (cur == parent.left) {  // 1.2 要删除的 cur 是 parent 的左节点  parent.left = cur.right;  } else {  // 1.3 要删除的 cur 是 parent 的右节点  parent.right = cur.right;  }  
}

2. 要删除节点的右孩子为空

  1. curroot,则 root = cur.leftimage.png|208

  1. cur 不是 rootcurparent.left,则 parent.left = cur.leftimage.png|304

  1. cur 不是 rootcurparent.right,则 parent.right = cur.leftimage.png|268
// 2. 要删除的节点 cur 的右孩子为空  
else if (cur.right == null) {  if (cur == root) {  // 2.1 要删除的 cur 是根节点  root = cur.left;  } else if (cur == parent.left) {  // 2.2 要删除的 cur 是 parent 的左节点  parent.left = cur.left;  } else {  // 2.3 要删除的 cur 是 parent 的右节点  parent.right = cur.left;  }  
}

3. 要删除的节点的左右孩子都不为空

需要使用 替换法 进行删除

  1. 在它的右子树中寻找一个最小的节点,用它的值填补到被删除节点中,再来处理该结点的删除问题

    • 因为要删除的节点 cur 左边都比它小,右边都比它大,所以就cur 的右边找到一个最小的节点,然后让目标节点覆盖掉 cur
    • 目标节点不会出现左右孩子都存在的情况。要么两边都为空,要么还存在一个右节点。(既然此节点是最小的,就不可能还有左子树,因为左子树肯定比此节点小)image.png
  2. 在它的左子树中寻找一个最大的节点,用它的值填补到被删除节点中,再来处理该结点的删除问题

    • 此时这个最大值一定是在左树的最右边,意味着它肯定没有右子树

所以找到最小值的特征是:

  • 此节点左子树为空,且一定在 cur 右树最左边
  • 此节点右子树为空,且一定在 cur 左树最右边

寻找右子树的最小值

// 3.1 右数的最小值  
TreeNode t = cur.right;  
TreeNode tp = cur;  
while (t.left != null) {  tp = t;  t = tp.left;  
}  
cur.val = t.val;  
if(t == tp.right) {  
//t 和 tp 在起始步就找到了最小值tp.right = t.right;  
}else{  
//t 和 tp 在继续移动的过程中找到最小值tp.left = t.right;  
}
  • t 是用来定位最小值的,当 t.left == null 的时候,t 就是最小值
  • tp 是用来定位 t 的父节点的,方便后续对节点进行删除(因为节点的删除都要依靠删除节点的父节点进行“改变连接对象”)
  • 在没找到最小节点之前,tpt 一起进行移动
    1. 最开始 tp 在要删除的节点 cur 的位置,tcur 的右节点(起始步)
    2. tp 走到 t 的位置
    3. t 再走向 tp 的左节点(一轮移动结束)
    4. t.left != nulltp 走到 t 的位置
    5. t 再走向 tp 的左节点(一轮移动结束)
  • 如果在起始步就满足 t.left == null 了,则直接进行

完整代码

public void remove(int key) {  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 {  //此时就是找到了要删除的节点  removeNode(parent, cur);  return;  }  }  
}  private void removeNode(TreeNode parent, TreeNode cur) {  // 1.当要删除的节点 cur 的左孩子为空  if (cur.left == null) {  if (cur == root) {  // 1.1 要删除的 cur 为根节点  root = cur.right;  } else if (cur == parent.left) {  // 1.2 要删除的 cur 是 parent 的左节点  parent.left = cur.right;  } else {  // 1.3 要删除的 cur 是 parent 的右节点  parent.right = cur.right;  }  // 2. 要删除的节点 cur 的右孩子为空  } else if (cur.right == null) {  if (cur == root) {  // 2.1 要删除的 cur 是根节点  root = cur.left;  } else if (cur == parent.left) {  // 2.2 要删除的 cur 是 parent 的左节点  parent.left = cur.left;  } else {  // 2.3 要删除的 cur 是 parent 的右节点  parent.right = cur.left;  }  // 3. 要删除的节点的左右孩子都不为空  } else {  // 3.1 右数的最小值  TreeNode t = cur.right;  TreeNode tp = cur;  while (t.left != null) {  tp = t;  t = tp.left;  }  cur.val = t.val;  if(t == tp.right) {  //t 和 tp 在起始步就找到了最小值  tp.right = t.right;  }else{  //t 和 tp 在继续移动的过程中找到最小值  tp.left = t.right;  }  }  
}

这篇关于【数据结构】二叉搜索树的功能实现详解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1132265

相关文章

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3

Python对接支付宝支付之使用AliPay实现的详细操作指南

《Python对接支付宝支付之使用AliPay实现的详细操作指南》支付宝没有提供PythonSDK,但是强大的github就有提供python-alipay-sdk,封装里很多复杂操作,使用这个我们就... 目录一、引言二、准备工作2.1 支付宝开放平台入驻与应用创建2.2 密钥生成与配置2.3 安装ali

Spring Security 单点登录与自动登录机制的实现原理

《SpringSecurity单点登录与自动登录机制的实现原理》本文探讨SpringSecurity实现单点登录(SSO)与自动登录机制,涵盖JWT跨系统认证、RememberMe持久化Token... 目录一、核心概念解析1.1 单点登录(SSO)1.2 自动登录(Remember Me)二、代码分析三、

SQL Server 中的 WITH (NOLOCK) 示例详解

《SQLServer中的WITH(NOLOCK)示例详解》SQLServer中的WITH(NOLOCK)是一种表提示,等同于READUNCOMMITTED隔离级别,允许查询在不获取共享锁的情... 目录SQL Server 中的 WITH (NOLOCK) 详解一、WITH (NOLOCK) 的本质二、工作

PyCharm中配置PyQt的实现步骤

《PyCharm中配置PyQt的实现步骤》PyCharm是JetBrains推出的一款强大的PythonIDE,结合PyQt可以进行pythion高效开发桌面GUI应用程序,本文就来介绍一下PyCha... 目录1. 安装China编程PyQt1.PyQt 核心组件2. 基础 PyQt 应用程序结构3. 使用 Q

springboot自定义注解RateLimiter限流注解技术文档详解

《springboot自定义注解RateLimiter限流注解技术文档详解》文章介绍了限流技术的概念、作用及实现方式,通过SpringAOP拦截方法、缓存存储计数器,结合注解、枚举、异常类等核心组件,... 目录什么是限流系统架构核心组件详解1. 限流注解 (@RateLimiter)2. 限流类型枚举 (

Java Thread中join方法使用举例详解

《JavaThread中join方法使用举例详解》JavaThread中join()方法主要是让调用改方法的thread完成run方法里面的东西后,在执行join()方法后面的代码,这篇文章主要介绍... 目录前言1.join()方法的定义和作用2.join()方法的三个重载版本3.join()方法的工作原

Spring AI使用tool Calling和MCP的示例详解

《SpringAI使用toolCalling和MCP的示例详解》SpringAI1.0.0.M6引入ToolCalling与MCP协议,提升AI与工具交互的扩展性与标准化,支持信息检索、行动执行等... 目录深入探索 Spring AI聊天接口示例Function CallingMCPSTDIOSSE结束语

C语言进阶(预处理命令详解)

《C语言进阶(预处理命令详解)》文章讲解了宏定义规范、头文件包含方式及条件编译应用,强调带参宏需加括号避免计算错误,头文件应声明函数原型以便主函数调用,条件编译通过宏定义控制代码编译,适用于测试与模块... 目录1.宏定义1.1不带参宏1.2带参宏2.头文件的包含2.1头文件中的内容2.2工程结构3.条件编

Python实现批量提取BLF文件时间戳

《Python实现批量提取BLF文件时间戳》BLF(BinaryLoggingFormat)作为Vector公司推出的CAN总线数据记录格式,被广泛用于存储车辆通信数据,本文将使用Python轻松提取... 目录一、为什么需要批量处理 BLF 文件二、核心代码解析:从文件遍历到数据导出1. 环境准备与依赖库