删除方法二叉搜索树

2024-04-23

我正在尝试为我一直在研究的 BST 结构实现一个删除方法。下面是查找、插入和删除方法的代码:

public class BST {
    BSTNode root = new BSTNode("root");

    public void insert(BSTNode root, String title){
        if(root.title!=null){

            if(title==root.title){
                //return already in the catalog
            }
            else if(title.compareTo(root.title)<0){

                if(root.leftChild==null){
                    root.leftChild = new BSTNode(title);
                }
                else{
                    insert(root.leftChild,title);
                }
            }
            else if(title.compareTo(root.title)>0){
                if(root.rightChild==null){
                    root.rightChild = new BSTNode(title);
                }
                else{
                    insert(root.rightChild,title);
                }
            }
        }
    }

    public void find(BSTNode root, String title){
        if(root!= null){
            if(title==root.title){
                //return(true);
            }
            else if(title.compareTo(root.title)<0){
                find(root.leftChild, title);
            }
            else{
                find(root.rightChild, title);
            }
        }
        else{
            //return false;
        }
    }

    public void remove(BSTNode root, String title){
        if(root==null){
            return false;
        }
        if(title==root.title){
            if(root.leftChild==null){
                root = root.rightChild;
            }
            else if(root.rightChild==null){
                root = root.leftChild;
            }
            else{
                //code if 2 chlidren remove
            }
        }
        else if(title.compareTo(root.title)<0){
            remove(root.leftChild, title);
        }
        else{
            remove(root.rightChild, title);
        }
    }
}

有人告诉我可以使用插入方法来帮助我使用删除方法,但我只是不知道如何获取最小/最大元素,然后用该值替换我要删除的元素,然后递归删除我采用了替换值的节点,同时仍然保持 O(logn) 复杂度。当我对这个问题感到头疼时,有人有任何想法或我错过的明显漏洞,或者有任何其他有用的东西吗?

编辑: 我使用答案的想法来提出这个,我相信这会起作用,但我收到一个错误,我的方法(不仅仅是删除)必须返回字符串,这是代码的样子,我认为这是返回语句??

public String remove(BSTNode root, String title){
            if(root==null){
                return("empty root");
            }
            if(title==root.title){
                    if(root.leftChild==null){
                            if(root.rightChild==null){
                                    root.title = null;
                                    return(title+ "was removed");
                            }
                            else{
                            root = root.rightChild;
                            return(title+ "was removed");
                            }
                    }
                    else if(root.rightChild==null){
                            root = root.leftChild;
                            return(title+ "was removed");
                    }
                    else{
                            String minTitle = minTitle(root);
                            root.title = minTitle;
                            remove(root.leftChild,minTitle);
                            return(title+ "was removed");
                    }
            }
            else if(title.compareTo(root.title)<0){
                    remove(root.leftChild, title);
            }
            else{
                    remove(root.rightChild, title);
            }
    }

public void remove (String key, BSTNode pos)
    {
        if (pos == null) return;
        if (key.compareTo(pos.key)<0)
            remove (key, pos.leftChild);
        else if (key.compareTo(pos.key)>0)
            remove (key, pos.rightChild);
        else {
            if (pos.leftChild != null && pos.rightChild != null)
            {
                /* pos has two children */
                BSTNode maxFromLeft = findMax (pos.leftChild); //need to make a findMax helper 
                //"Replacing "  pos.key " with " maxFromLeft.key
                pos.key = maxFromLeft.key;
                remove (maxFromLeft.key, pos.leftChild);
            }
            else if(pos.leftChild != null) {
                /* node pointed by pos has at most one child */
                BSTNode trash = pos;
                //"Promoting " pos.leftChild.key " to replace " pos.key
                pos = pos.leftChild;
                trash = null;
            }
            else if(pos.rightChild != null) {
                /* node pointed by pos has at most one child */
                BSTNode trash = pos;
                /* "Promoting " pos.rightChild.key" to replace " pos.key */
                pos = pos.rightChild;
                trash = null;
            }
            else {
                pos = null;
            }
        }
    }

This is the remove for an unbalanced tree. I had the code in C++ so I have quickly translated. There may be some minor mistakes though. Does the tree you are coding have to be balanced? I also have the balanced remove if need be. I wasn't quite sure based on the wording of your question. Also make sure you add a private helper function for findMax()

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

删除方法二叉搜索树 的相关文章

  • 更改启动 Java 运行时后 IntelliJ IDEA 无法在 Ubuntu 上启动

    之前 我的 IntelliJ 运行得很好 但我使用的是 java 6 所以我的项目无法使用 gradle 运行 我用命令将java切换到版本8sudo update alternatives config java 我检查了java ver
  • Spring JDBC 模板。如何获取pl/sql脚本的结果变量

    我正在使用 NamedParameterJdbcTemplate 来运行 pl sql 脚本 但我不知道如何获取out变量的值 id out 提前致谢 String script declare begin if myFunc id in
  • 中断并标签,“标签 MyLabel 丢失”

    我有这样的代码 if condition1 break MyLabel while true some code here MyLabel if condition2 break more code here 我收到此错误 标签 MyLab
  • 有没有更简单的方法来分割/重建字符串?

    目前我正在使用String split 像这样 String tmp props get i getFullName split String name for int j 1 j lt tmp length j if j gt 1 nam
  • 像 Google Play 商店一样在垂直 RecyclerView 中动态不同图像水平 RecyclerView

    我一直在关注这个教程 http android pratap blogspot co za 2015 12 horizo ntal recyclerview in vertical html http android pratap blog
  • 模式更新后 jOOQ 生成的类的运行时验证?

    我用org jooq util DefaultGenerator在构建过程中生成 jOOQ 类来表示我的数据库模式 当应用程序运行时 架构预计会在应用程序不知情的情况下发生更改 此类更改可能与已生成的代码兼容 也可能不兼容 如何在运行时检测
  • 在 json 中解析尾随字符

    我正在尝试检查 json 是否有效 并且我遇到了奇怪的行为 当我将一些字符附加到可解析的 json 时 jackson 和 gson 都会解析它 并且它们会忽略尾随字符 我想检查 json 是否严格有效 请帮忙 我尝试了几个标志mapper
  • 始终等待页面加载到 PageObjects 上

    因此 当出现问题时 我只是创建了一个简单的 selenium JBehave 代码 我将首先发布简化的代码 然后稍后解释我的问题是什么 所以这里我们有一个简单的 AbstractClass 它将在我的 PageObjects 上继承 此类仅
  • Android:TelephonyManager 类

    我不明白为什么 API 文档中这么写TelephonyManager类是public 但是当我尝试创建一个实例时 它说它不是公共类 并且无法从包中访问 我看到它也说使用Context getSystemService Context TEL
  • Eclipse 无法识别 persistence.xml 的内容

    我在 eclipse 中收到以下错误 persistence xml 文件没有可识别的内容 我的 persistence xml 文件在我的应用程序中工作得很好 但 eclipse 一直给我这个错误 我在移动文件并使用 m2eclipse
  • SSLContext 初始化

    我正在看JSSE参考指南 我需要获取一个实例SSLContext为了创建一个SSLEngine 所以我可以使用它Netty以启用安全性 获取实例SSLContext I use SSLContext getInstance 我看到该方法被重
  • 合并和颜色样式不适用于 Apache POI excel 2003 格式

    在 Apache POI 中 我为某些单元格应用了一些样式并合并了这些单元格 当我在 2010 年或 2007 年打开时 它工作正常 但在 2003 年 格式样式消失了 每次保存 2003 Excel 文件之前都会弹出兼容性检查对话框 请参
  • ThreadPoolExecutor 和队列

    我以为使用线程池执行器 http docs oracle com javase 6 docs api java util concurrent ThreadPoolExecutor html我们可以提交Runnables 要在以下位置执行B
  • 如何在 QueryDSL 中选择文字

    我目前正在开发一个使用 queryDSL 和 hibernate 的项目 其中它需要一个选择文字 按照发布的示例here https stackoverflow com questions 18691317 querydsl how to
  • java中永远不会出现的异常

    我为点和向量编写一个类 我想用它们来计算向量的点和范数 这些是点类和向量类 public class Point public float x y public class MyVector public Point start end 我
  • “强制更新快照/版本” - 这是什么意思

    在 Maven 项目中 选择 更新项目 时 有一个名为 强制更新快照 版本 的选项 它有什么作用 强制更新快照 版本 就像运行以下命令 mvn U install U 也可以用作 update snapshot 看here http boo
  • 在Java内存管理中,“PS”代表什么?

    每当我看到 Java 中对内存的引用时 各种空格总是以 PS 为前缀 PS 是什么意思 它开始困扰我 到目前为止我唯一的猜测是 泳池空间 但这将是多余的 例子 PS伊甸园空间 PS 幸存者空间 PS 终身空间 老一代 PS Perm Gen
  • 空检查时可能未初始化错误

    我正在检查变量是否已初始化 但此时 netbeans 给了我variable reader might not have been initialized警告 我该如何解决 抑制这个问题 这是我的代码 摘要 final Reader rea
  • java中什么是静态接口?

    我正在阅读Map Entry界面 当我注意到它是一个static界面 我不太明白什么是静态接口 它与常规接口有什么不同 public static interface Map Entry
  • 将 SQL 数据中的一行映射到 Java 对象

    我有一个 Java 类 其实例字段 以及匹配的 setter 方法 与 SQL 数据库表的列名相匹配 我想优雅地从表中获取一行 到 ResultSet 中 并将其映射到此类的实例 例如 我有一个 Student 类 其中包含实例字段 FNA

随机推荐

  • 单击元素以外的任意位置以使用 if 语句隐藏它

    解决方案如下 我已经阅读了这里有关这个概念的大多数问题 但我似乎无法让它与 if 语句一起使用 有什么帮助吗 JSFiddle http jsfiddle net 2udYp button click function div fadeTo
  • 如何通过 Swift 包管理器在 Xcode 中安装包

    我正在 Xcode 中开发一个项目 并尝试安装和使用加密货币Swift https github com krzyzanowskim CryptoSwift通过 Swift 包管理器进行包 我读了文档 https swift org pac
  • CMake:不支持的 GNU 版本 - 不支持高于 8 的 gcc 版本

    在降级我的 GCC 之前 我想知道是否有一种方法可以确定我的机器中的哪些程序 框架或依赖项将被破坏 以及是否有更好的方法来安装 openpose 例如 更改 CMake 中的某些内容 有没有办法可以解决这个问题 而无需更改我的系统 GCC
  • 同时使用 :nth-child 和 :nth-last-child

    我做不到 nth child and nth last child伪类同时工作 效果很好 突出显示前 3 个要素 a li nth child n 3 background fbfcc8 效果很好 突出显示最后 3 个元素 b li nth
  • Android:如何以原始尺寸显示图像

    我从字节数组创建位图图像并将其显示在 ImageView 中 这android layout width and android layout heightImageView 的设置为wrap content 并且android scale
  • 通过属性和正文指定 JSTL 值之间的区别

    我试图弄清楚 JSTL 的这两种用途之间是否存在功能差异
  • 电话号码的 jQuery 输入掩码

    我希望用户的输入自动填充电话号码的标点符号 以便看起来像这样 xxx xxx xxxx 这是我的 HTML 代码 div class form group div
  • UIManagedDocument 迁移数据模型

    我正在开发一个 iPhone 应用程序 它使用UIManagedDocument并将其文档存储在 iCloud 上 一切都工作正常 直到我更改了我的核心数据模型 方案 添加了新的模型版本 就像我在过去几周内多次所做的那样 我添加了一个新属性
  • 如何使用python Bottle框架获取客户端IP地址

    我需要使用 python 的客户端 IP 地址 我已经尝试过下面的代码 但它在服务器中不起作用 from socket import gethostname gethostbyname ip gethostbyname gethostnam
  • 任务并行不稳定,有时使用 100% CPU

    我目前正在测试 C 的 Parallel 一般来说 它工作得很好 并且使用并行比普通的 foreach 循环更快 然而 有时 比如五分之一 我的 CPU 会达到 100 使用率 导致并行任务非常慢 我的 CPU 设置是 i5 4570 和
  • R:评估字符串

    事实证明需要定义一个函数eval string它评估一个字符串 就像它是一个表达式 调用 一样 例如 如果 string lt cyl 6 disp gt 200 我想要 eval string string mtcars 相当于 eval
  • 捕获 json.net 序列化错误

    我正在使用 dotnet core 2 2 开发 Web api 我们希望捕获序列化异常并返回 400 badRequest 以与验证错误 422UnprocessableEntity 区分开 我们尝试创建一个异常处理程序 public v
  • Spring data JPA和hibernate分离实体传递以持久化ManyToMany关系

    我正在尝试保留一个与已保留的其他对象具有多对多关系的对象 这是我的持久化对象 它们已经持久化在数据库中 这是一个 MySql Product Entity Table name PRODUCT public class Product pr
  • Mat-table 排序演示不起作用

    我正在尝试获取mat table排序在本地工作 虽然我可以让数据按预期显示 但单击标题行不会像在线示例那样进行排序 根本没有发生任何事情 我正在尝试让这个演示在本地运行 https material angular io component
  • 仅当通过 AWS CLI 调用 Lambda 时,目标才有效

    我有一个 hello world 测试 Lambda 配置为 触发 API网关 目的地 亚马逊 SQS 一个队列表示成功 另一个队列表示失败 import json def lambda handler event context prin
  • 如何在flyway创建的postgresql jdbc连接上设置时区?

    我有一个 postgresql 数据库 我使用 Flyway 将脚本部署到该数据库 我使用 Maven Flyway 插件启动针对目标数据库的数据库构建 在该构建中 我有一些脚本可以执行以下操作 create table my table
  • 在 OpenGL 中移动相机时出现故障

    我正在为 iPhone 编写一个基于图块的游戏引擎 除了以下故障之外 它基本上可以正常工作 基本上 相机将始终将玩家保持在屏幕中央 并且它会移动以正确跟随玩家并在静止时正确绘制所有内容 然而 当玩家移动时 玩家行走的表面瓷砖会出现故障 如下
  • Rails 嵌套单一资源路由

    我有一个简单的用户模型 带有单个嵌套的配置文件资源 因此在我的routes rb 中我有 resources users do resource profile only gt edit update show end 这会生成预期的路线
  • Octave/Matlab:向向量添加新元素

    有一个向量x我必须添加一个元素 newElem 有什么区别吗 x end 1 newElem and x x newElem x end 1 newElem更稳健一些 x x newElem 仅当x是行向量 如果它是列向量x x newEl
  • 删除方法二叉搜索树

    我正在尝试为我一直在研究的 BST 结构实现一个删除方法 下面是查找 插入和删除方法的代码 public class BST BSTNode root new BSTNode root public void insert BSTNode