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

为什么此代码用于删除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.1K20

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

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

40220

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

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

55032

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

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

2.6K20

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

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

12510

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

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

69720

【算法】论平衡二叉树(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: 返回最小键    *

83820

【算法】论平衡二叉树(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: 返回最小键    *

991110

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

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

37610

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

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

49420

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

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

54030

红黑树深入剖析及Java实现

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

1.3K30

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

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

51620

数据结构简单复习

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

95120

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

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

55710

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

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

29130

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

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

33820

红黑树深入剖析及Java实现

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

94260

看动画学算法之:二叉搜索树BST

如果一个树每个节点都只有0,1,2个子节点的话,这颗树就被称为二叉树,如果我们对二叉树进行一定排序。...比如,对于二叉树每个节点,如果左子树节点元素都小于根节点右子树节点元素都大于根节点,那么这样树被叫做二叉搜索树(Binary Search Tree)简称BST。...BST基本性质 刚刚我们已经讲过BST基本特征了,现在我们再来总结一下: BST任意节点左子树一定要比该节点值要小 BST任意节点右子树一定要比该节点值要大 BST任意节点左右子树一定要是一个...看一张图直观感受一下BSTBST构建 怎么用代码来构建一个BST呢?...return node; } BST删除 BST删除要比插入复杂一点,因为插入总是插入到叶子节点删除可能删除是非叶子节点

42630
领券