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

二叉搜索树删除中的指针问题

二叉搜索树(Binary Search Tree,简称 BST)是一种特殊的二叉树,其中每个节点的值都大于其左子树中的所有节点的值,且小于其右子树中的所有节点的值。在删除 BST 中的节点时,需要考虑以下几种情况:

  1. 节点没有子节点:直接删除该节点即可。
  2. 节点只有一个子节点:将该节点的子节点替换为该节点即可。
  3. 节点有两个子节点:找到该节点的中序遍历后继节点,将其值复制到该节点,然后删除后继节点。

在删除节点时,需要注意以下几个指针问题:

  1. 删除节点的左子树中的最大节点(或右子树中的最小节点),需要将其父节点的指针指向该节点的子节点。
  2. 删除节点的左子树中的最大节点(或右子树中的最小节点)的父节点,需要将其指针指向该节点的子节点。
  3. 删除节点的左子树中的最大节点(或右子树中的最小节点)的祖先节点,需要将其指针指向该节点的子节点。

在删除节点时,可以使用递归或迭代的方式来处理指针问题。具体实现可以参考相关数据结构和算法教材或在线资源。

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

相关·内容

如何删除二叉搜索节点?

450.删除二叉搜索节点 题目链接:https://leetcode-cn.com/problems/delete-node-in-a-bst/ 给定一个二叉搜索根节点 root 和一个值 key...,删除二叉搜索 key 对应节点,并保证二叉搜索性质不变。...递归 递归三部曲: 确定递归函数参数以及返回值 说道递归函数返回值,在二叉搜索插入操作通过递归返回值来加入新节点, 这里也可以通过递归返回值删除节点。...第五种情况有点难以理解,看下面动画: 450.删除二叉搜索节点 动画中颗二叉搜索删除元素7, 那么删除节点(元素7)左孩子就是5,删除节点(元素7)右子树最左面节点是元素8。...:搜索删除操作

1.3K30

二叉——700.二叉搜索搜索

1 题目描述 给定二叉搜索(BST)根节点 root 和一个整数值 val。 你需要在 BST 中找到节点值等于 val 节点。 返回以该节点为根子树。 如果节点不存在,则返回 null 。...来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/search-in-a-binary-search-tree 2 题目示例 3 题目提示 数节点数在...[1, 5000] 范围内 1 <= Node.val <= 10^7 root 是二叉搜索 1 <= val <= 10^7 4 思路 方法一:递归 二叉搜索满足如下性质: 左子树所有节点元素值均小于根元素值...复杂度分析 时间复杂度:O(N),其中N是二叉搜索节点数。最坏情况下二叉搜索是—条链,且要找元素比链末尾元素值还要小(大),这种情况下我们需要递归N次 空间复杂度:O(N)。...复杂度分析 时间复杂度:O(N),其中N是二叉搜索节点数。最坏情况下二叉搜索是—条链,且要找元素比链末尾元素值还要小(大),这种情况下我们需要迭代Ⅳ次 空间复杂度:O(1)。

33920

Python实现二叉搜索删除功能

二叉搜索实现可以参考:Python实现二叉搜索 本文使用 Python 实现二叉搜索删除功能,在此之前必须先知道二叉搜索特性: 1....在 SearchBinaryTree ,实现了判断二叉搜索是否为空 is_empty() 方法、一对供实例对象调用 root() 方法、按树形结构打印二叉搜索 show_tree() 方法和添加数据到二叉搜索...在二叉搜索查找节点方法 search(root, data),要从二叉搜索删除节点,首先要保证节点是属于二叉搜索,所以先搜索节点是否在二叉搜索。...删除叶节点后,不会破坏整棵结构,只要找到此节点,然后将节点从二叉“断开”(父节点指针指向空)即可。在上面添加数据后二叉搜索,随机选一个叶节点,如 66。...为了保证删除节点后二叉仍然是一棵二叉搜索,补位节点有两种选择方式,选择被删除节点前继节点或后继节点,前继节点一定存在左子树,后继节点一定存在右子树,选择两种方式都可以,本文选择后继节点。

84120

5.4删除二叉搜索任意元素

一.删除思路分析 在删除二叉搜索任意元素时,会有三种情况: 1.1 删除只有左孩子节点 节点删除之后,将左孩子所在二叉取代其位置;连在原来节点父亲元素右节点位置,比如在图中需要删除58这个节点...1.3 删除包含左右孩子节点 如下图,二叉搜索包含有左右孩子,假设现需要删除58这个节点。 ? 针对该种情况,分析如下: 我们把58这个节点记为d节点(包含有左子树与右子树),如下图所示: ?...针对这种节点删除情况需要把左子树与右子树融合起来,融合方法: 从d这节点左孩子与右孩子找一个比d节点还要大节点取代d节点,根据二叉搜索性质可知(左边节点<当前节点<右边节点),这个需要被找节点存在于...二、编码实现二叉搜索任意元素 根据上述分析,在此基础上进行编码,删除代码如下: //从二叉搜索删除元素为e节点 public void remove(E e) { root...= remove(root, e); } //删除以node为根二叉搜索中值为e节点,递归算法 //返回删除节点后更新二叉搜索根 private Node

54740

二叉搜索删除节点 动画演示

Day60:删除二叉搜索某个节点 1 题目 给定一个二叉搜索根节点 root 和一个值 key,删除二叉搜索 key 对应节点,并保证二叉搜索性质不变。...返回二叉搜索(有可能被更新)根节点引用。 一般来说,删除节点可分为两个步骤: 首先找到需要删除节点; 如果找到了,删除它。 说明:要求算法时间复杂度为 O(h),h 为高度。...这道题思路很straitforward,根据BST性质,具体说来分为如下几种情况: 如果被删除节点关键码key小于当前根节点nodei.val,则问题规模直接降阶到左子树 关键码key大于当前根节点...你首先要对递归有深刻理解,其次像链表、二叉等这类具备递归数据结构,操作它们节点引用问题要时刻保持清醒,很容易出错。...__delNodei(nodei.left,key) # 删除后返回nodei.left节点引用 以下面二叉搜索删除值等于3节点为例演示,伸入到左子树: ?

1.1K20

​LeetCode刷题实战450:删除二叉搜索节点

今天和大家聊问题叫做 删除二叉搜索节点,我们先来看题面: https://leetcode-cn.com/problems/delete-node-in-a-bst/ Given a root...给定一个二叉搜索根节点 root 和一个值 key,删除二叉搜索 key 对应节点,并保证二叉搜索性质不变。返回二叉搜索(有可能被更新)根节点引用。...(启示:说到 二叉搜索BST时,不仅要想到序遍历结果是排好序,还要想到可以递归,有点像二分查找模式寻找目标值,提高效率) 删除节点: 经过上一步递归过程,找到了key,而且key是要调整这个子树根节点...(思考1:竟然不用存储pre节点,是怎么做到连接两个部分?) 当遍历到这个节点时,其实变量名只是起到一个指针作用,直接修改它值就行,直接令它值等于它继承节点值。...刷题实战449:序列化和反序列化二叉搜索

31220

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

题目: 给定一个二叉搜索根节点 root 和一个值 key,删除二叉搜索 key 对应节点,并保证二叉搜索性质不变。返回二叉搜索(有可能被更新)根节点引用。...一般来说,删除节点可分为两个步骤: 首先找到需要删除节点; 如果找到了,删除它。...5 / \ 2 6 \ \ 4 7 解题思路: 待删除节点在二叉三种情况有: 如果目标节点没有子节点,我们可以直接移除该目标节点。...另外二叉搜索序遍历结果为从小到大顺序排列; 删除节点如果不是叶子节点时, 则应把该节点值替换为其右子树中最小一个节点值 (删除节点后驱节点); 删除节点如果不是叶子节点且无右子树时, 则应把该节点值替换为其左子树中最大一个节点值...(删除节点前驱节点), 并在子树递归删除刚刚替换节点 你会发现, 二叉搜索最小节点为该最左叶子; 最大节点为该最右叶子, 即: 如果 key > root.val,说明要删除节点在右子树

1.1K20

二叉搜索众数

二叉搜索众数 给定一个有相同值二叉搜索BST,找出BST所有众数(出现频率最高元素)。 假定BST有如下定义: 结点左子树中所含结点值小于等于当前结点值。...结点右子树中所含结点值大于等于当前结点值。 左子树和右子树都是二叉搜索。 示例 给定BST [1,null,2,2],返回[2]。...(假设由递归产生隐式调用栈开销不被计算在内),如果不考虑这个进阶条件的话,直接遍历一遍二叉并且顶一个哈希表将遍历过值以及出现次数记录,之后再遍历一遍哈希表取出众数即可,考虑到这个进阶条件,那么就需要定义一些变量保存当前状态...,判断哪些条件符合要求,置入返回值,当对二叉搜索进行二叉序遍历时,能够得到一个有序序列,通过数列有序以及存储当前状态变量即可达到目标,此外还需要注意是题目要求是返回一个数组,也就说众数可能有多个...,若左节点存在则向左递归,之后定义处理位置即序遍历,如果当前结点值与存储遍历当前节点值相同则将计数器递增,否则将当前值置数为节点值,将计数器置0,如果当前计数器大于等于最大值计数器则进入条件,如果这两个值相等

61630

二叉搜索公共祖先问题

说明: 所有节点值都是唯一。 p、q 为不同节点且均存在于给定二叉搜索。...和二叉:公共祖先问题不同,普通二叉求最近公共祖先需要使用回溯,从底向上来查找,二叉搜索就不用了,因为搜索有序(相当于自带方向),那么只要从上向下遍历就可以了。...在二叉:公共祖先问题中,如果递归函数有返回值,如何区分要搜索一条边,还是搜索整个。...总结 对于二叉搜索最近祖先问题,其实要比普通二叉公共祖先问题简单多。 不用使用回溯,二叉搜索自带方向性,可以方便从上向下查找目标区间,遇到目标区间内节点,直接返回。...:搜索公共祖先问题

32220

最优二叉搜索问题(Java)

最优二叉搜索问题(Java) 1、前置介绍 2、算法设计思路 2.1 最优二叉搜索结构 2.2 一个递归算法 2.3 计算最优二叉搜索期望搜索代价 3、代码实现 4、复杂度分析 5、参考资料...它具有下述性质:存储于每个结点中元素xi「大于」其左子树任一结点所存储元素,「小于」其右子树任一结点所存储元素。二叉搜索叶结点是形如(xi,xi+1)开区间。...在表示S二叉搜索搜索元素x, 返回结果有以下两种情形: 在二叉搜索内结点中找到 「x=xi」; 在二叉搜索叶结点中确定x属于 「(xi, xi+1)」。...ki, …, kr-1最优二叉搜索作为其左子树,以及一棵包含关键字kr+1, …, kj二叉搜索作为其右子树。...虽然我们将看到如何计算root[i, 月值,但是利用这些值来构造最优二叉搜索问题将留作练习(练习15.5-1)。

43940

LeetCode96|二叉搜索搜索

1,问题简述 给定二叉搜索(BST)根节点和一个值。 你需要在BST中找到节点值等于给定值节点。 返回以该节点为根子树。 如果节点不存在,则返回 NULL。...2,示例 例如, 给定二叉搜索: 4 / \ 2 7 / \ 1 3 和值: 2 你应该返回如下子树: 2.../ \ 1 3 在上述示例,如果要找值是 5,但因为没有节点值为 5,我们应该返回 NULL。...3,题解思路 递归方法+二叉有序性 4,题解程序 public class SearchBSTTest { public static void main(String[] args) {...6,总结 这道题还是比较容易理解,理解二叉特点和数据有序性是非常有必要二叉遍历方式,二叉节点特点都是我们需要掌握

37640

二叉搜索插入操作

701.二叉搜索插入操作 题目链接:https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/ 给定二叉搜索(BST)...根节点和要插入值,将值插入二叉搜索。...返回插入后二叉搜索根节点。输入数据保证,新值和原始二叉搜索任意节点值都不同。 注意,可能存在多种有效插入方式,只要在插入后仍保持为二叉搜索即可。你可以返回任意有效结果。...迭代 再来看看迭代法,对二叉搜索迭代写法不熟悉,可以看这篇:二叉二叉搜索登场! 在迭代法遍历过程,需要记录一下当前遍历节点父节点,这样才能做插入节点操作。...在530.二叉搜索最小绝对差和501.二叉搜索众数,都是用了记录pre和cur两个指针技巧,本题也是一样

38320

【图论搜索专题】结合「二叉图论搜索问题

题目描述 这是 LeetCode 上「863. 二叉中所有距离为 K 结点」,难度为「中等」。...Tag : 「图论 BFS」、「图论 DFS」、「二叉」 给定一个二叉(具有根结点 root), 一个目标结点 target ,和一个整数值 K 。...而是一类特殊图,我们可以通过将二叉转换为图形式,再进行「BFS / 迭代加深」。...由于二叉每个点最多有 个子节点,点和边数量接近,属于稀疏图,因此我们可以使用「邻接表」形式进行存储。...建图方式为:对于二叉相互连通节点(root 与 root.left、root 和 root.right),建立一条无向边。 建图需要遍历整棵,使用 DFS 或者 BFS 均可。

91040

基于序有序二叉搜索

什么是二叉搜索 二叉搜索是普通二叉升级,普通二叉除了存储数据以外好像没有别的优势了,但是二叉搜索不同,如果对搜索采用序遍历得到结果是一串有序数字。...3.它左右子树也是一棵二叉搜索结构如下: template struct BSTreeNode { //节点包含它左子树和右子树指针以及这个节点中值...因为序遍历得到结果是一串有序数字列,所以对于二叉搜索而言中序遍历才是王道。...在一棵二叉搜索搜索一个元素,最坏结果也就是O(N),但如果这个搜索一个接近完全二叉情况,则只需要查找高度次。...false : true; } 二叉搜索插入 向搜索插入不能破坏搜索结构,所以不能插入和树种元素相同值 非递归 //二叉搜索序遍历结果是有序数列,不允许往其中插入相同值,插入删除不允许破坏结构

16830
领券