首页
学习
活动
专区
圈层
工具
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

为什么此代码用于删除BST中的节点,而不是删除使其为0的节点

BST(二叉搜索树)是一种特殊的二叉树结构,其中每个节点的左子树中的值都小于该节点的值,而右子树中的值都大于该节点的值。删除BST中的节点是一种常见的操作,可以通过以下步骤完成:

  1. 首先,需要找到要删除的节点。从根节点开始,比较要删除的节点的值与当前节点的值。如果要删除的节点的值小于当前节点的值,则继续在左子树中查找;如果要删除的节点的值大于当前节点的值,则继续在右子树中查找;如果要删除的节点的值等于当前节点的值,则找到了要删除的节点。
  2. 找到要删除的节点后,需要考虑三种情况进行处理: a. 如果要删除的节点是叶子节点(没有子节点),则可以直接删除该节点。 b. 如果要删除的节点只有一个子节点,则可以将该子节点替换为要删除的节点。 c. 如果要删除的节点有两个子节点,则需要找到该节点的后继节点(即右子树中最小的节点),将后继节点的值复制到要删除的节点中,然后删除后继节点。
  3. 删除节点后,需要保持BST的性质。如果删除的节点是根节点,则可以直接删除;否则,需要将删除节点的父节点指向删除节点的子节点。

为什么此代码用于删除BST中的节点,而不是删除使其为0的节点?

这个问题的前提是要删除BST中的节点,而不是将节点的值设置为0。删除节点是指从BST中完全删除该节点及其子树,而不仅仅是将节点的值设置为0。这是因为BST的目的是维护有序性,删除节点后需要保持BST的有序性。如果只是将节点的值设置为0,那么BST的结构将被破坏,无法保证节点的有序性。

因此,删除BST中的节点是指完全删除该节点及其子树,而不仅仅是将节点的值设置为0。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

LeetCode 450: 删除二叉搜索树中的节点 Delete Node in a BST

题目: 给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。...另外二叉搜索树的中序遍历结果为从小到大顺序排列的; 删除节点如果不是叶子节点时, 则应把该节点的值替换为其右子树中最小的一个节点值 (删除节点的后驱节点); 删除节点如果不是叶子节点且无右子树时, 则应把该节点的值替换为其左子树中最大的一个节点值...(删除节点的前驱节点), 并在子树中递归删除刚刚替换的节点 你会发现, 二叉搜索树最小节点为该树的最左叶子; 最大节点为该树的最右叶子, 即: 如果 key > root.val,说明要删除的节点在右子树...如果该节点不是叶子节点且有右节点,则用它的后继节点的值替代 root.val = successor.val,然后删除后继节点。...如果该节点不是叶子节点且只有左节点,则用它的前驱节点的值替代 root.val = predecessor.val,然后删除前驱节点。

1.2K20
  • 删除链表中的节点 两行代码实现

    题目描述 请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点。传入函数的唯一参数为 要被删除的节点 。...提示: 链表至少包含两个节点。 链表中所有节点的值都是唯一的。 给定的节点为非末尾节点并且一定是链表中的一个有效节点。 不要从你的函数中返回任何结果。...\*/ class Solution { public void deleteNode(ListNode node) { } } 解题思路 如果我们要删除第二个的节点...,我们**1.首先要把第三个的节点的值赋值给第二个的节点**,**2.然将第二个节点的next指针指向第四个节点**,这样就实现了删除 [在这里插入图片描述] [在这里插入图片描述] 实现代码 **本题是编写一个函数...,传入值为要删除的节点,用两行代码即可实现** /\*\* \* Definition for singly-linked list. \* public class ListNode {

    42120

    删除链表中的节点 两行代码实现

    题目描述 请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点。传入函数的唯一参数为 要被删除的节点 。...提示: 链表至少包含两个节点。 链表中所有节点的值都是唯一的。 给定的节点为非末尾节点并且一定是链表中的一个有效节点。 不要从你的函数中返回任何结果。...} * } */ class Solution { public void deleteNode(ListNode node) { } } 解题思路 如果我们要删除第二个的节点...,我们1.首先要把第三个的节点的值赋值给第二个的节点,2.然将第二个节点的next指针指向第四个节点,这样就实现了删除 ?...实现代码 本题是编写一个函数,传入值为要删除的节点,用两行代码即可实现 /** * Definition for singly-linked list.

    57432

    导师计划--数据结构和算法系列(上)

    pop() pop方法用于删除并返回数组的最后一个元素。 shift() shift方法可以删除数组的第一个元素。...向一个栈插入新元素称作进栈、入栈或压栈,这是将新元素放在栈顶元素上面,使之成为新的栈顶元素。 从一个栈删除元素又称为出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。...二叉查找树,也称二叉搜索树或二叉排序树,是一种特殊的二叉树,相对值较小的值保存在左节点中,较大的值保存在右节点中。二叉查找树特殊的结构使它能够快速的进行查找、插入和删除数据。...node.right = this.removeNode(node.right, tempNode.data); // 删除指定节点的下的最小值,也就是置其为空...A,替换待删除节点值,并删除节点A【上面的示例代码中就是这种方案】 删除两个节点的图解如下: 图 图由边的集合及顶点的集合组成。

    17010

    野生前端的数据结构基础练习(7)——二叉树

    中的一个,度为0的节点称为叶节点。...具体使用场景的例子包括:先序遍历时,可以用于查看树结构,中序遍历,可以用于显示排序结果,后序遍历,可用于计算目录内文件占用的数据大小。...删除节点 TIP:主要注意删除同时包含左右孩子节点的节点时逻辑,由BST插入的规则可以知道,节点右子树中所有的节点都是大于当前节点值的,所以右子树中找出的最小值是大于当前节点左子树上所有值的,所以将其上浮至当前待删除节点位置...计数 三.课后习题(书中第十节习题) 为BST增加一个新方法,返回BST中节点个数。 为BST增加一个新方法,返回BST中边的个数。 为BST类增加一个新方法max( ),返回最大值。...根据遍历序还原二叉树 【先序+中序】或者【后序+中序】都可以还原出唯一的二叉树,只根据【先序+后序】还原出的二叉树不是唯一的(感兴趣的可以看看这篇《 为什么只给出前序和后序,不能唯一确定一个二叉树 》)

    71720

    【算法】论平衡二叉树(AVL)的正确种植方法

    额, 就是我上次不是种二叉查找树嘛(见上面的链接),发现大多数二叉树都长的比较好,但总有那么那么几颗长势很不如人意,我对此感到很疑惑(大家思考一下这是为什么) 直到——  看门的李大爷给我送过来了一包树种...向上取整) rank(获取给定key的排名) select(根据排名获得给定key) 而动态方法则会修改树中结点, 并进一步影响二叉树的结构 put (插入键值对) delete(删除键值对) BST的动态方法可能会修改二叉树的结构...这种旋转在整个平衡化过程中可能进行一次或多次 3.且是从失去平衡的最小子树根结点开始的(即离插入结点最近的、平衡因子超过1的祖先结点) 右旋操作 右旋操作过程:使结点3位置“下沉”,而结点2位置“上浮”...结点2位置“下沉”, 而结点4位置上浮,反转当前结点和它右儿子的父子关系(2和4), 使2结点变成4结点的左儿子。 2. 同时断裂结点3和结点4间的链接, 转接到结点2中(处理拖油瓶结点) ?...删除方法比较复杂,在看代码前可以先看下对二叉查找树中put方法的解析 二叉查找树的delete方法 平衡查找树的delete方法   /**    * @description: 返回最小键    *

    85620

    【算法】论平衡二叉树(AVL)的正确种植方法

    额, 就是我上次不是种二叉查找树嘛(见上面的链接),发现大多数二叉树都长的比较好,但总有那么那么几颗长势很不如人意,我对此感到很疑惑(大家思考一下这是为什么) 直到——  看门的李大爷给我送过来了一包树种...向上取整) rank(获取给定key的排名) select(根据排名获得给定key) 而动态方法则会修改树中结点, 并进一步影响二叉树的结构 put (插入键值对) delete(删除键值对) BST的动态方法可能会修改二叉树的结构...这种旋转在整个平衡化过程中可能进行一次或多次 3.且是从失去平衡的最小子树根结点开始的(即离插入结点最近的、平衡因子超过1的祖先结点) 右旋操作 右旋操作过程:使结点3位置“下沉”,而结点2位置“上浮”...结点2位置“下沉”, 而结点4位置上浮,反转当前结点和它右儿子的父子关系(2和4), 使2结点变成4结点的左儿子。 2. 同时断裂结点3和结点4间的链接, 转接到结点2中(处理拖油瓶结点) ?...删除方法比较复杂,在看代码前可以先看下对二叉查找树中put方法的解析 二叉查找树的delete方法 平衡查找树的delete方法   /**    * @description: 返回最小键    *

    1K110

    BST(二叉搜索排序树)类模板的实现

    由于二叉树的递归定义,使得在二叉树中许多操作中可以以递归的方式书写操作,代码更加浅显易懂。...重点条件:左子树中的所有节点的数据域都小于或等于根节点的数据域,而右子树中的所有节点的数据域都大于等于根节点的数据域。根据这个特点,BST树的中序遍历是一个由小到大的顺序序列。...根据这个特点,BST树中最左边的节点的数据域一定是BST的最小值,而BST树中最右边的节点的数据域一定是BST的最大值。...而删除任意一个节点可以归结为以下三类: (1)一个节点有右子树,而没有左子树。 (2)一个节点有左子树,而没有右子树。 (3)一个节点既有左子树又有右子树。...=NULL){ root = deleteMin(root); } } //删除BST树中数据域为value的节点,即删除二叉树中的任意节点 void remove(T value){

    40110

    【图解数据结构】二叉查找树

    如果比根结点值大,则说明特定值在根结点右子树上,继续在右子节点执行此操作;如果比根结点值小,则说明特定值在根结点左子树上,继续在左子节点执行此操作。...如果到执行完成都没有找到和特定值相等的节点值,那么二叉查找树中没有包含此特定值的节点。...这里我们需要了解一下后继节点的定义。 一个节点的后继节点是指,这个节点在中序遍历序列中的下一个节点。相应的,前驱节点是指这个节点在中序遍历序列中的上一个节点。...后继节点不是删除节点的子节点 ? 后继节点38是删除节点37右子树的最左侧节点。...后继节点不是删除节点的子节点且有子节点 ? 这种情况和上一种情况相似,唯一的区别是后继节点有子节点(注意肯定是右子节点)。

    51720

    红黑树深入剖析及Java实现

    如果待删除的节点不是叶子节点,则先找到待删除节点的中序遍历的后继节点,用该后继节点的值替换待删除的节点的值,然后删除后继节点。 ?...BST存在的问题 BST存在的主要问题是,数在插入的时候会导致树倾斜,不同的插入顺序会导致树的高度不一样,而树的高度直接的影响了树的查找效率。...RBTree的查找操作 RBTree的查找操作和BST的查找操作是一样的。请参考BST的查找操作代码。...RBTree的删除操作 删除操作首先需要做的也是BST的删除操作,删除操作会删除对应的节点,如果是叶子节点就直接删除,如果是非叶子节点,会用对应的中序遍历的后继节点来顶替要删除节点的位置。...删除后就需要做删除修复操作,使的树符合红黑树的定义,符合定义的红黑树高度是平衡的。 删除修复操作在遇到被删除的节点是红色节点或者到达root节点时,修复操作完毕。

    1.3K30

    「数据结构与算法Javascript描述」二叉树

    选择树而不是那些基本的数据结构,是因为在二叉树上进行查找非常快(而在链表上查找则不是这样),为二叉树添加或删除元素 也非常快(而对数组执行添加或删除操作则不是这样)。 1....树可以分为几个层次,根节点是第 0 层,它的子节点是第 1 层,子节点的子节点是第 2层,以此类推。树中任何一层的节点可以都看做是子树的根,该子树包含根节点的子节点,子节点的子节点等。...后序遍历先访问叶子节点,从左子树到右子树,再到根节点。 需要中序遍历的原因显而易见,但为什么需要先序遍历和后序遍历就不是那么明显了。我们先来实现这三种遍历方式,在后续中再解释它们的用途。...中序遍历的代码如下: function inOrder(node) { if (node !...从 BST 中删除节点的第一步是判断当前节点是否包含待删除的数据,如果包含,则删除该节点;如果不包含,则比较当前节点上的数据和待删除的数据。

    54820

    数据结构简单复习

    目录 环形队列的插入、删除原理 BST(二叉查找树) 遍历二叉树 哈夫曼树 大/小顶堆 存储序列 左孩子右兄弟树与森林 快速排序 归并排序 堆排序 闭哈希、开哈希 2-3树 深度优先与广度优先 最短路径长度与最小代价生成树...插入 先判断队列是否已满,如果还没满,rear=(rear+1)%n 删除 先判断队列是否为空,如果不为空,front=(front+1)%n BST(二叉查找树) BST上节点的左孩子的值总是小于该结点...遍历二叉树 先序遍历( Preorder traversal ) 第一次访问根结点,然后总是先访问左子树后访问右子树(等左子树访问完,而不是访问了左孩子马上访问右孩子) 中序遍历( Inorder traversal...需要注意的是,一定要递归地找到“最左的”左子树再访问。中序遍历是从叶子结点或叶子结点的父节点(当叶子结点的父节点没有左孩子时)开始的。...递归地选择、更新,我们会得到离A第n近的点,直至得到所有点离A的最短路径。 该算法中数组D可以是一个小顶堆,这样的改进使迪杰斯特拉算法在稀疏图中的复杂度降低(Theta约等于VlogV)。

    98420

    数据结构基础温故-4.树与二叉树(中)

    在上一篇中,我们了解了树的基本概念以及二叉树的基本特点和代码实现,还用递归的方式对二叉树的三种遍历算法进行了代码实现。但是,由于递归需要系统堆栈,所以空间消耗要比非递归代码要大很多。...但是,对于某些问题,如果不使用递归,那将是极端难看的代码。   (2)循环算法:   ①优点:速度快,结构简单。   ②缺点:并不能解决所有的问题。有的问题适合使用递归而不是循环。...而每当循环一次就会从stackIn中出栈一个元素,并压入stackOut中,那么这时stackOut中的出栈顺序则变成了左孩子->右孩子->根节点的顺序,也就符合了后序遍历的规则。...4.2 老节点的移除   二叉查找树的删除过程相比插入过程要复杂一些,这里主要分三种情况进行处理: Scene1.节点p为叶子节点:直接删除该节点,再修改其父节点的指针(注意分是根节点和不是根节点),...Scene2.节点p为单支节点(即只有左子树或右子树):让p的子树与p的父亲节点相连,再删除p即可;(注意分是根节点和不是根节点两种情况),如图b; ?

    58610

    数据结构小记【PythonC++版】——BST树篇

    ~来个复杂点的热热身~ 该BST树的中序遍历结果:7 15 17 22 27 30 45 60 75 注意,BST树的结构不是一次性立即生成的,而是基于查找过程逐渐生成的。...在查找过程中,当树中的节点元素不等于被查找值时,才进行插入节点的操作。 使用二叉查找树的好处 如果BST树是一棵平衡二叉树,那么在BST树上进行插入和删除操作的速度会很快。...使用二叉查找树的缺点 BST树的最终形状依赖于插入操作的顺序,导致BST树可以退化成单链表(如果单调递减式的插入元素),后面会讲到AVL树,可以规避此缺点。...插入节点: 1.先执行查找操作,来确定新节点的位置。 2.确认位置后,插入新节点,新节点成为叶子节点。 删除节点: 从BST树删除节点时,我们关心的是保持树的其余节点以正确的顺序排列。...三,BST树的代码实现 代码样例中的BST树采用的是链式存储实现,代码中节点的初始化和一般的二叉树代码类似,由数据域、左指针、右指针构成。

    39420

    原创 | 手把手刷二叉搜索树(第二期)

    删除二叉搜索树中的节点(Medium) 701.二叉搜索树中的插入操作(Medium) 700.二叉搜索树中的搜索(Easy) 98.验证二叉搜索树(Medium) 我们前文 手把手刷二叉搜索树(第一期...的每个节点应该要小于右边子树的所有节点,下面这个二叉树显然不是 BST,因为节点 10 的右子树中有一个节点 6,但是我们的算法会把它判定为合法 BST: 出现问题的原因在于,对于每一个节点root...root.left, target) || isInBST(root.right, target); } 这样写完全正确,但这段代码相当于穷举了所有节点,适用于所有普通二叉树。...因为删除节点的同时不能破坏 BST 的性质。有三种情况,用图片来说明。 情况 1:A恰好是末端节点,两个子节点都为空,那么它可以当场去世了。...因为具体应用中,val域可能会是一个复杂的数据结构,修改起来非常麻烦;而链表操作无非改一改指针,而不会去碰内部数据。

    31730

    红黑树深入剖析及Java实现

    如果待删除的节点不是叶子节点,则先找到待删除节点的中序遍历的后继节点,用该后继节点的值替换待删除的节点的值,然后删除后继节点。 ?...BST存在的问题 BST存在的主要问题是,数在插入的时候会导致树倾斜,不同的插入顺序会导致树的高度不一样,而树的高度直接的影响了树的查找效率。...RBTree的删除操作 删除操作首先需要做的也是BST的删除操作,删除操作会删除对应的节点,如果是叶子节点就直接删除,如果是非叶子节点,会用对应的中序遍历的后继节点来顶替要删除节点的位置。...删除后就需要做删除修复操作,使的树符合红黑树的定义,符合定义的红黑树高度是平衡的。 删除修复操作在遇到被删除的节点是红色节点或者到达root节点时,修复操作完毕。...删除操作的总体思想是从兄弟节点借调黑色节点使树保持局部的平衡,如果局部的平衡达到了,就看整体的树是否是平衡的,如果不平衡就接着向上追溯调整。

    98960

    万字长文!二叉树入门和刷题看这篇就够了!

    [7gvge8ctk7.jpeg] 上面那是个玩笑,二叉树长这样: [k3u40b49yr.png] 二叉树常被用于实现二叉查找树和二叉堆。树比链表稍微复杂,因为链表是线性数据结构,而树不是。...而找到之后,会出现三种情况。 待删除的节点左子树为空,让待删除节点的右子树替代自己。 [htuq46s10a.png] 待删除的节点右子树为空,让待删除节点的左子树替代自己。...[dcduqa111u.png] 那什么又是完全二叉树呢:如果二叉树中除去最后一层节点为满二叉树,且最后一层的结点依次从左到右分布,则此二叉树被称为完全二叉树。...如果你在工作中没有用到,不是说明算法不重要,而可能是你还不够重要。 第814题:给定二叉树根结点 root ,此外树的每个结点的值要么是 0,要么是 1。返回移除了所有不包含 1 的子树的原二叉树。...每个节点的值只会为 0 或 1 。 还是先解释一下,啥是剪枝:假设有一棵树,最上层的是root节点,而父节点会依赖子节点。如果现在有一些节点已经标记为无效,我们要删除这些无效节点。

    56830

    整理得吐血了,二叉树、红黑树、B&B+树超齐全,快速搞定数据结构

    image 完全二叉树 如果二叉树中除去底层节点后为满二叉树,且底层节点依次从左到右分布,则此二叉树被称为完全二叉树。 ?...image 二叉查找树(Binary Search Tree - BST,又称二叉排序树、二叉搜索树) 二叉查找树根节点的值大于其左子树中任意一个节点的值,小于其右子树中任意一节点的值,且该规则适用于树中的每一个节点...对树结构改动最少、节点值最进行删除节点值的必然是左子树中的最大叶子节点值与右子树中的最小叶子节点值 为什么不用右子树中的最小叶子节点值取代删除节点?...为什么选择AVL树而不是BST? 大多数BST操作(如搜索、最大值、最小值、插入、删除等)的时间复杂度为O(h),其中h是BST的高度。对于极端情况下的二叉树,这些操作的成本可能变为O(n)。...,效率自然更慢 以上也是Java 8的HashMap中树节点实现结构采用红黑树而不是AVL树的原因 删除节点 删除节点主要违反的规则是子树中黑色高度的更改,导致根节点到叶子路径的黑色高度降低。

    3.1K21
    领券