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

为什么在删除函数调用后指针没有将BST的节点置零?

在删除函数调用后,指针没有将BST的节点置零的原因是因为在删除节点时,只是将节点从树中移除,并没有对指针进行置零操作。这是因为在删除节点时,只需要将其父节点指向其子节点即可完成删除操作,不需要对被删除节点的指针进行修改。

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

  1. 被删除节点没有子节点:直接将其父节点指向空即可。
  2. 被删除节点只有一个子节点:将其父节点指向其子节点即可。
  3. 被删除节点有两个子节点:需要找到其右子树中的最小节点(或左子树中的最大节点),将其值替换到被删除节点中,然后再删除该最小节点(或最大节点)。

在以上情况中,只有第一种情况需要将指针置零,其他情况只需要修改指针的指向即可。这是因为在删除节点后,BST的结构并没有发生改变,只是节点的值发生了变化或者节点的位置发生了调整。

需要注意的是,删除节点时需要保证BST的性质仍然成立,即左子树中的所有节点的值小于根节点的值,右子树中的所有节点的值大于根节点的值。如果删除节点后没有进行相应的调整,可能会导致BST的性质被破坏。

推荐的腾讯云相关产品:腾讯云数据库TDSQL、腾讯云云服务器CVM、腾讯云容器服务TKE、腾讯云对象存储COS等。具体产品介绍和链接地址可以参考腾讯云官方网站。

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

相关·内容

【43期】盘点那些必问数据结构算法题之二叉树基础

树中基本单位是结点,结点之间链接,称为分支。一棵树最上面的结点称之为根节点,而下面的结点为子结点。一个结点可以有0个或多个子结点,没有子结点结点我们称之为叶结点。...而二叉搜索树(BST)是有序二叉树,BST需要满足如下条件: 若任意结点左子树不空,则左子树上所有节点值均小于它节点值; 若任意结点右子树不空,则右子树上所有节点值均大于或等于它节点值...删除结点 删除结点稍微复杂一点,要考虑3种情况: 删除是叶子结点,好办,移除该结点并将该叶子结点父结点 left 或者 right 指针空即可。...删除结点有两个子结点,则需要找到该结点左子树最大结点(使用后面的bstSearchIter 函数),并将其值替换到待删除结点中,然后递归调用删除函数删除该结点左子树最大结点即可。 ?...这里值得一提是层序遍历,先是计算了二叉树高度,然后调用辅助函数依次遍历每一层结点,这种方式比较容易理解,虽然时间复杂度上会高一些。

35110

二叉搜索树

---- 查找操作 算法如下: 1)树为空,返回NULL 2)树非空时,对根节点键值与x即你想那个比较,如果相等则返回根节点 3)如果x小于根结点键值,左子树进行查找x 4)如果x...,最大值一定在最右分支节点上,最小值最左分支节点上。...算法如下: 1)树空时,直接返回NULL 2)树非空时,如果要删除是叶子节点时,直接删除,并把父节点相应指针为NULL。...3)要删除只有一个孩子时,把其父节点指针指向要删除结点孩子结点。...3)若当前结点为树根结点时,直接返回根结点右子树 4)否则,若当前结点右子树为空,即当前结点为叶子结点时,父节点左子树NULL,释放当前结点。

64620

Binary Search Trees(BST)

BST性质 BST形状为 image.png 每个BST节点x,存在一个key,一个指向父节点parent指针,同时还有一个左子树和右子树 rootparent不存在 左子树值y与父节点...然后插入第二个元素40,它比30要大,为它节点 image.png 插入第三个元素17,比30要小,为它节点 image.png 然后是20,比30小,找到做子树,左子树节点值为17...y.right = z else: y.left = z 复制代码 它耗时为O(lgn) 找到后继节点 后继节点即从值上来讲,找到比要找元素要大最接近值,根据BST性质,它肯定在右子树上...,由于20没有右子树,会先回溯到17,然后17是它节点左子树,那么它就是后继节点; 40后继不存在; def successor(self,node): if node == None...=None: x = x.left return x 复制代码 删除节点 节点删除之后,必须要维持原有的BST性质 image.png 删除节点13,它一个子节点没有,直接删除即可 image.png

36130

数据结构学习—树(2)

二叉搜索树(Binary Search Tree) 1.非空左子树所有键值小于其根节点键值 2.非空右子树所有键值大于其根节点键值 3.左右子树都是二叉搜索树 二叉搜索树删除删除是叶节点...:直接删除,并再修改其父节点指针为NULL 要删除节点只有一个孩子节点:将其父节点指针指向要删除节点孩子节点删除节点有左、右两颗子树:右子树最小元素或左子树最大元素替代被删除节点...) //树空 { if(BST !...return NULL; } Position Find(int x, Tree BST) //找到值为x元素树中位置,使用递归方式 { if(!...) 找到值为x元素树中位置,使用循环迭代方式 { while(BST){ if(x > BST->Data) BST = BST->Right;

43330

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

为什么选择AVL树而不是BST? 大多数BST操作(如搜索、最大值、最小值、插入、删除等)时间复杂度为O(h),其中h是BST高度。对于极端情况下二叉树,这些操作成本可能变为O(n)。...image 根据BST规则删除节点133,155替代133位 从155位往上检测到100为失衡节点u,左高右低为LR情况,对u左子节点ul=37左旋,再对u节点执行右旋(可以看成对50同时插入2个子节点导致...个人引申疑问 为什么红黑树也算平衡树呢?它平衡因子是什么? 为什么AVL比红黑树更平衡?为什么AVL树插入和删除会引起更多选择呢?...插入步骤: 节点n根据BST规则插入,且新使节点颜色为红色 根据n节点p情况执行不同操作 2.1 n没有节点p,即N为根,n颜色更改为黑色 2.2 p为黑色,直接插入 2.3 p为红色,...数据指针B+树中仅存在于叶节点,因此叶节点必须将所有键值及其对应数据指针存储到磁盘文件块以便访问。此外,叶节点也用于链接以提供对记录有序访问。

2.6K20

使用 Go 语言实现二叉搜索树

原文链接: 使用 Go 语言实现二叉搜索树二叉树是一种常见并且非常重要数据结构,很多项目中都能看到二叉树身影。...二叉搜索树特点最重要就是它有序性,二叉搜索树中,每个节点值都大于其左子树中所有节点值,并且小于其右子树中所有节点值。图片这意味着通过二叉搜索树可以快速实现对数据查找和插入。...,分三种情况来考虑:如果要删除节点没有节点,只需要直接节点中,指向要删除节点指针为 nil 即可如果删除节点只有一个子节点,只需要更新父节点中,指向要删除节点指针,让它指向删除节点节点即可如果删除节点有两个子节点...,我们需要找到这个节点右子树中最小节点,把它替换到要删除节点上。...然后再删除这个最小节点,因为最小节点肯定没有左子节点,所以可以应用第二种情况删除这个最小节点即可最后是一个打印树形结构方法,实际项目中其实并没有实际作用:func (bst *ItemBinarySearchTree

16520

【数据结构与算法】详解什么是树结构,并用代码手动实现一个二叉查找树

树结构优点: 空间利用率比较高 可以非常快速地查找到最大值和最小值 三、树结构术语 因为本文是从开始学习树结构,所以我们在这里有必要讲解一下,我们封装各种树结构过程中涉及到术语,方便大家理解...该方法接收一个回函数 handle 作为参数, 用于遍历过程中执行某些操作 实现思路: 从根结点开始,按照 访问根结点 => 访问左子树 => 访问右子树 顺序对各个结点进行访问 访问到结点时,执行回函数...== null) { // 根结点 key传给回函数处理 handle(node.key) // 遍历左子树 this.preOrderNodes...该方法无需传入参数 实现思路: 从根结点开始,按照 访问左子树 => 访问根节点 => 访问右子树 顺序对各个结点进行访问 访问到结点时,执行回函数 handle ,并将访问到结点 key 作为参数传入...删除结点为叶子结点 假设我们要删除 结点14 ,因为该结点为叶子结点,后面没有其它结点,所以直接删除它不会对后续结点造成影响,即将 结点14 节点 结点13 右子结点设置为 null ,如图

64830

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

,并将元素传递给回函数。...回函数四个参数意义如下:accumulator,必需,累计器累计回返回值, 它是上一次调用回时返回累积值,或initialValue;currentValue,必需,数组中正在处理元素;...哈希表把key(键)通过一个固定算法函数(此函数称为哈希函数/散列函数)转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组下标,value(值)存储以该数字为下标的数组空间里...,而当使用哈希表进行查询时候,就是再次使用哈希函数key转换为对应数组下标,并定位到该空间获取value。...遍历时候,我们分为三种遍历方法--先序遍历,中序遍历和后序遍历: 删除节点是一个比较复杂操作,考虑情况比较多: 该节点没有叶子节点时候,直接将该节点空; 该节点只有左子树,直接将该节点赋予左子树

12510

查找--数据结构

从数据结构线形表一端开始,顺序扫描,依次扫描到结点关键字与给定值k相比较,若相等则表示查找成功;若扫描结束仍没有找到关键字等于k结点,表示查找失败。...SearchMax(root->rchild); } //删除节点代码: void DeleteBSTNode(BST_P *root, DataType data) { BST_P p...result data << endl; //二叉排序树中插入9 Insert_BST(&root, 9); printf...,若余数为再加上30而为哈希函数值。...注:会产生空隙 三、 哈希表查找及分析 哈希表上进行查找过程跟哈希造表过程基本一致,给定K值,根据造表时设计哈希函数计算出哈希地址,若此位置上没有记录,则查找不成功;否则比较关键字若与给定关键字相同

60320

实现一个二叉搜索树(JavaScript 版)

二叉树计算机科学中应用很广泛,学习它有助于让我们写出高效插入、删除、搜索节点算法。二叉树节点定义:一个节点最多只有两个节点,分别为左侧节点、右侧节点。...初始化一个二叉搜索树 声明一个 BST 类,构造函数 constructor() 里声明它结构: class BST { constructor () { this.root...中序遍历 中序遍历,先访问左侧节点,直到为最小节点访问到树最底端,当前节点 value 取出来,访问右侧节点,适用于从小到大排序。...二叉树搜索销毁 在上面最后讲解了二叉搜索树后序遍历,这里讲下它实际应用, C++ 等面向对象编程语言中可以定义析构函数使得某个对象所有引用都被删除或者当对象被显式销毁时执行,做一些善后工作。...例如,我们本次实现二叉搜索树,可以利用后序遍历方式,逐渐每个节点进行释放。 定义一个 destroy 方法,以便在树实例上能够调用。

1.4K30

【算法】二叉查找树(BST)实现字典API

所以代码默认不能选择 -1作为 Key或者Value (实际场景中,我们会将int类型Key替换为实现Compare接口对象,同时“失败”时返回值从-1设为null,这时是没有这个问题)..., 设置为外部类BST成员变量不是就可以了吗,  为什么要为每个结点都设置一个N属性呢 Node类里成员变量N除了为size方法服务外, 更多地是为rank方法和select方法服务。...: 递归调用前代码和递归调用后代码 put递归一段代码分割成两部分: 递归调用前代码和递归调用后代码,如图所示 ?...,能够“继承”某个结点结点 删除实现思路 查找到相应结点 将其删除 分析删除某个结点三种情况 删除结点时, 按结点位置,可以分三种情况分析: 第一种情况: 当被删除结点没有子树时, 直接将它父节点指向它链接为...都是:查找到待删除结点后,判断左子树或右子树是否为空, 若其中一个子树为空,则将该结点节点指向该节点链接, 改为指向该节点另一颗子树(左子树为null则指向右子树,右子树为null则指向右子树

1.6K90

美团面试官:你对二叉树后续遍历一无所知

那有的读者可能会问,根据 BST 定义,有没有可能一棵二叉树中不存在 BST?...不会,因为按照 BST 定义,任何一个单独节点肯定是 BST,也就是说,再不济,二叉树最下面的叶子节点肯定是 BST。...res; } 这样,这道题就解决了,traverse函数遍历二叉树同时顺便把之前辅助函数事情都做了,避免了递归函数中调用递归函数,时间复杂度只有 O(N)。...其实也不是,主要是看题目,就好比 BST 中序遍历是有序一样。 这道题为什么用后序遍历呢,因为我们需要这些变量都是可以通过后序遍历得到。...因为以上几点都可以通过后序遍历方式「顺便」计算出来,所以这道题使用后序遍历肯定是最高效

47320

百度前端一面常见手写面试题(持续更新中)

// 移动指针位置 return head // 返回删除元素 }else { let current = this.head for (let i = 0; i 200=>300 找到200上一个100nextnext为300,把300赋值给...因为 Promise 状态只能改变一次, 那么我们只需要把 Promise.race 中产生 Promise 对象 resolve 方法, 注入到数组中每一个 Promise 实例中函数中即可...在这个对象上使用 open 方法创建一个 HTTP 请求,open 方法所需要参数是请求方法、请求地址、是否异步和用户认证信息。发起请求前,可以为这个对象添加一些信息和监听函数。...('cxk', 'father');child.say() // father好,我是练习时长两年半cxk手写防抖函数函数防抖是指在事件被触发 n 秒后再执行回,如果在这 n 秒内事件又被触发,则重新计时

32820

数据结构简单复习

插入 先判断队列是否已满,如果还没满,rear=(rear+1)%n 删除 先判断队列是否为空,如果不为空,front=(front+1)%n BST(二叉查找树) BST节点左孩子值总是小于该结点...剩余字符结点与哈夫曼树树根结点间选择最小两个结点,两个结点合成一颗树(此时有多棵哈夫曼树)或一个结点加入哈夫曼树(这个结点和树根有同一个父节点)。 重复第三步直到所有结点被加入哈夫曼树。...大顶堆 删除 堆尾部元素与将要删除元素交换位置,再重新调整先前处于尾部元素位置。...针对合并过程,也可以再组织一个数组,前半部分正向存储数组,后半部分反向存储,同样拥有两个指针,形如:1367|5432。这么做好处是不需要判断指针是否越界,两个指针指向同一位时合并过程结束。...闭哈希( Closed Hashing ) 闭哈希遇到不同关键字处于同一位情况,会确定下一个可能存储位置,其中最简单一种是线性探测,当哈希函数计算出位置存放了别的数据时,依次往后寻找。

95320

BST & AVL 二分搜索树 & 平衡二叉树实现原理

一.BST 二分搜索树实现原理 本文完整实现了基本BST,由于注重是逻辑和原理实现,所以没有采用泛型。注意方法访问修饰符。...实际 上这样思路是没有问题。但是java中, 删除节点操作并不是那么容易,这与java没有指针有关。...问题就是出现在函数 private boolean deleteNode(TreeNode node)之中,我们删除节点当做参数传进来,能够用操作原来数吗?不能。...因此这样做法是错C中可以采用这种方式,删除节点没有问题。...二:AVL 平衡二叉树实现原理 AVL树将在构建树时候就将不平衡消灭了,实际上,AVL树与BST改进就只是insert()函数上, 下面重点讲解insert()函数

66710

跳跃表深入理解

那么有没有实现起来简单、和自平衡BST效率想近实现方法呢?答案就是跳表,并且简单很多。...3、设计思想 跳跃表(skiplist)是一种有序数据结构,它通过每个节点中维持多个指向其它节点指针,从而达到快速访问节点目的。跳跃表 Redis 里没有其它用途。...为了避免占用过多空间,第1层之上都不存储实际数据,只有指针。 当查找元素时,会从最顶层链表节点开始遍历。如当前节点下一个节点包含值比目标元素值小,则继续向右查找。...相对于插入来说,删除操作没有那么多逻辑,跟正常单链表删除一致。 3、为啥Redis不用平衡搜索树来实现?...性能至少不比平衡树差 简单更容易实现和维护 一句话总结什么是跳表:跳表就是在有序链表基础上通过增加额外指针节点来解决查询效率,通过随机插入来提高变更效率一种数据结构。

41420
领券