删除方法二叉搜索树

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(使用前将#替换为@)

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

随机推荐

  • 单击元素以外的任意位置以使用 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