2021-10-08：填充每个节点的下一个右侧节点指针。给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。填充它的每个 next 指针，让这个指针指向其下一个右侧节点。...如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL。进阶：你只能使用常量级额外空间。...queue.isEmpty() { // 第一个弹出的节点 var pre = &Node{} size := queue.size for
题目 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。...百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
2022-05-22：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。...百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。...二叉树的最近公共祖先。 答案2022-05-22： 莫里斯遍历。 答案用rust编写，答案有误。...tree node. type TreeNode struct { val int left *TreeNode right *TreeNode } // 提交以下的方法 // 该方法亮点在于
1.当前节点存入上一节点和下一节点的引用（双向链表） 2.当前节点存入多个下一节点的引用（树） 我们把一个节点中存入多个下一节点的数据结构称为树，首节点称为根节点，如图： ?...任意节点的左、右⼦树也分别为⼆叉查找树。 红黑树 假如有这样一个业务场景，一批已经排序好的数据，要找一个数据结构加快访问和搜索数据，那么二叉搜索树合适吗？？仔细想象。...性质5:从任一节点到其子树中每个叶子节点(nil节点)的路径都包含相同数量的黑色节点。 利用颜色规则，通过旋转达到树的平衡。...情况1，父亲节点在祖父节点左边，且叔叔节点为红色。 ? 情况2，父亲节点在祖父节点左边，叔叔节点不是红色，且当前节点位于父节点的右边 ? 情况3，当前父亲节点在祖父节点右边，且叔叔节点是红色 ?...，从开始的设置当前节点为红，判断父节点是否红、根节点，根据“性质4:每个红色节点的两个子节点都是黑色的”判断是否需要调整，通过调整节点颜色和旋转，保证二叉树符合所有红黑树的性质，达到一个自动平衡树的状态
二叉搜索树 什么是二叉搜索树？ 二叉搜索树首先是个二叉树，这个二叉树有这么一个特点，左子树的所有节点都比根节点小，右子树的所有节点都比根节点大。...二叉搜索树的实现——K模型 K模型只存k值 二叉搜索树的每一个节点都有一个值，以及两个指针，指向左节点的指针，指向右节点的指针。...那么我们解决问题的方法就有两种了： 找到它左子树最大的那个节点（上图的2节点），然后和它交换。——根据该树的性质，该最大的节点在左子树的最右边。然后可以直接删除节点吗？...——不可以，因为2左边可能有左子树，所以我们要该节点的父节点（本图为1）的右指针指向交换之后改节点的左子树。 这里不需要确定父节点和子节点的关系，是因为关系已经确定了。...交换之后改节点也不能直接进行删除，因为它可能有右子树，我们要把它的父节点的左指针指向它的右子树。 如下图： 注意： 当删除的该节点为根节点的时候，就和上面的规则不一样了。
二叉堆满足堆特性：父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆。 当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。...请回忆一下二叉树的性质，其中有一条性质： 性质五：如果对一棵有n个节点的完全二叉树的节点按层序编号（从第一层开始到最下一层，每一层从左到右编号，从1开始编号），对任一节点i有： 如果i=1 ，则节点为根节点...简单来说： 如果根节点在数组中的位置是1，第n个位置的子节点分别在2n 与 2n+1，第n个位置的双亲节点分别在⌊i /2⌋。因此，第1个位置的子节点在2和3....如果根节点在数组中的位置是0，第n个位置的子节点分别在2n+1与2n+2，第n个位置的双亲节点分别在⌊（i-1） /2⌋。因此，第0个位置的子节点在1和2....我们删除根节点12： ? 可能有人疑惑，删除后数组最末尾不是多了一个6吗？ 的确，但我们把数组中有效元素的个数减少了一，最末尾的6并不是堆的组成元素。
2021-02-26：一个数组arr是二叉树的中序遍历结果，每条边的开销是父节点和子节点的乘积，总开销是所有边的开销之和。请问最小总开销是多少？...链接：https://www.nowcoder.com/questionTerminal/0d939e874a004f449a370aca1346dd5c 来源：牛客网 小团有一个由N个节点组成的二叉树...，每个节点有一个权值。...定义二叉树每条边的开销为其两端节点权值的乘积，二叉树的总开销即每条边的开销之和。小团按照二叉树的中序遍历依次记录下每个节点的权值，即他记录下了N个数，第i个数表示位于中序遍历第i个位置的节点的权值。...输入描述: 第一行输入一个整数N（1<=N<=300），表示二叉树的节点数。 第二行输入N个由空格隔开的整数，表示按中序遍历记录下的各个节点的权值，所有权值均为不超过1000的正整数。
比如“猫属”有两个子节点“家生”和“野生”，“蝇属”中也有一个“家生”，但它和“猫属”中的“家生”完全不同而且相互独立。这意味着我们可以在不影响“猫属” 的子节点的情况下更改“蝇属”的子节点。...代码的第一个标记符是同时最后一个是。这一页中所有其他的标记符也都是成对的。试一下你就会发现这种嵌套的特点在树的每一层都是成立的。...一个节点也可能有更多的信息，我们称之为“负载”。虽然负载信息和树的许多算法并不直接相关，但是它对于树的应用至关重要。 边（Edge） 边也是树的基本构成部分。边连接两个节点，并表示它们之间存在联系。...在图 2 中，节点log/，spool/，yp/构成节点var/的子节点集。 父节点（Parent） 一个节点是它出边所连接的所有节点的父节点。...在图 2 中，节点var/是节点log/，spool/，yp/的父节点。 兄弟节点（Sibling） 同一个节点的所有子节点互为兄弟节点，在文件系统树中节点etc/和节点usr/是兄弟节点。
性质二：根节点是黑色； 根节点总是黑色的。它不能为红。 性质三：每个叶节点（NIL或空节点）是黑色； 这个可能有点理解困难，可以看图： ?...性质四：每个红色节点的两个子节点都是黑色的（也就是说不存在两个连续的红色节点）； 就是连续的两个节点不能是连续的红色，连续的两个节点的意思就是父节点与子节点不能是连续的红色。...如果我们把原先的父节点看做是新的要插入的节点，把原先要插入的节点看做是新的父节点，那就变成了当要插入的节点在父节点的左支的情况，对，是的，就是按照当要插入的节点在父节点的左支的情况进行旋转，旋转完之后变成如下...4、当被删除元素为黑，且兄弟节点为黑，兄弟节点两个孩子也为黑，父节点为红，此时，交换兄弟节点与父节点的颜色；NIL元素是指每个叶节点都有两个空的，颜色为黑的NIL元素，需要他的时候就可以把它看成两个黑元素...最后 1、红黑树的实现其实是一个2、3、4树，只是将双节点或者三节点用红色进行了标示，如果你将红色节点放到和它父元素相同的高度，并把它和父元素看做是一个元素，你就会发现，变成了一个高度为lgN的二叉树，
下面就从2-3树的角度来谈谈红黑树的定义。 从2-3树来看红黑树 一般我们接触最多的是二叉树，也就是一个父节点最多有两个子节点。...2-3树与二叉树的不同之处在于，一个父节点可以有两个子节点，也可以有三个子节点，并且其也满足类似二叉搜索树的性质。...2-3树中把有两个元素，三个子节点的节点称为3节点，把有一个元素，两个子节点的的节点称为2节点。 接着插入8，插入8的时候同样要先融入叶子节点中，如下图左侧所示 ?...在2-3树中，根节点只能是2节点或者3节点，2节点与3节点在红黑树中的等价形式，如下图所示 ? 2节点与3节点在红黑树中的等价形式显然，无论是哪种情况，根节点都是黑色的。...2-3树中2节点对应到红黑树便是一个黑色的节点，而3节点对应到红黑树是一个红色节点和一个黑色节点。所以，无论是2节点还是3节点，在红黑树中都会对应一个黑色节点。
key为结点中的value值，left,right为该结点的左右孩子指针，没有的话为NIL，p是一个指针，是指向该节的父节点。如下图（来自维基百科）表示就是一颗红黑树，NIL为指向外结点的指针。...2.由于红黑树是特殊的二叉查找树，它的删除和二叉查找树类型，真正的删除点即为删除点A的中序遍历的后继(前继也可以)，通过红黑树的特性可知这个后继必然最多只能有一个孩子，其这个孩子节点必然是右孩子节点，从而为单支情况...从图中可以看出，操作之后红黑树并未达到平衡状态，而是变成的黑兄的情况 Case 2:新节点的兄弟节点为黑色,此时可能有如下情况 红父二黑侄：将父节点变成黑色，兄弟节点变成红色，新节点变成黑色即可,如下图所示...情况二:新节点在右子树，红侄在兄弟节点右子树，此时的操作为先左旋，后右旋并将侄节点变为父亲的颜色，父节点变为黑色，如下图所示 ?...3.正在删除的节点有两个子节点 2.修复红黑树的特性，如代码中调用removeFixUp方法修复红黑树的特性。
key为结点中的value值，left,right为该结点的左右孩子指针，没有的话为NIL，p是一个指针，是指向该节的父节点。如下图（来自维基百科）表示就是一颗红黑树，NIL为指向外结点的指针。...(根节点必须为黑色，其两个子节点为红色，叔节点不用改变),如下图所示，注意省略黑哨兵节点 以上就是红黑树新增节点所有可能的操作，下面会介绍红黑树中的删除操作 删除操作 删除操作相比于插入操作情况更加复杂...Case 2:新节点的兄弟节点为黑色,此时可能有如下情况 * 红父二黑侄：将父节点变成黑色，兄弟节点变成红色，新节点变成黑色即可,如下图所示 黑父二黑侄：将父节点变成新节点的颜色，新节点变成黑色，...，父亲节点变为黑色，如下图所示 情况四：新节点在右子树，红侄在兄弟节点右子树,此时的操作为左旋，并将兄弟节点变为父节点的颜色，父亲节点变为黑色，侄节点变为黑色，如下图所示 红黑树实现 如下是使用JAVA...3.正在删除的节点有两个子节点 2.修复红黑树的特性，如代码中调用removeFixUp方法修复红黑树的特性。
2节点直接转化为黑色节点；3节点这里可以有两种表现形式，左倾红节点或者右倾红节点。而4节点被强制要求转化为一个黑父带着左右两个红色儿子。 ?...只要把左倾红黑树中的红色节点顺时针方向旋转45°使其与黑父平行，然后再将它们看作一个整体，你就会发现，这不就是一颗2-3树吗？ ?...算法4中给出的红黑树是基于2-3树实现，而且这种实现的红黑树十分特殊，它要求概念模型中的3节点在红黑树中必须用左倾的红色节点来表示。...试想在2-3树中如果待插入节点是个2节点，那么反应在红黑树中，不正好对应着黑色父节点吗，在黑色父节点下面增加一个红色儿子，确实不会违背红黑树的任何规则，这也对应着我们向2-3树中的2节点插入一个元素，只需要简单的把...注意，这种情况对应着2-3树中出现了临时4节点，我们在2-3树中的处理是将这个临时4节点分裂，左右元素各自形成一个2节点，中间元素上升到上层跟父节点结合。
而祖先节点是父节点的父节点(或者祖先）节点。 兄弟节点：拥有同一个父节点的节点们！ 节点的度: 就是节点拥有孩子节点的个数(是直接连接的孩子不是子孙). 树的度: 就是所有节点中最大 (节点的度)。...二叉树 二叉树是一树的一种，但应用比较多，所以需要深入学习，二叉树的每个节点最多只有两个子节点(但不一定非得要有两个节点)。...待删除节点有1个孩子 左右节点均不空 左右孩子节点都不为空这种情况是相对比较复杂的，因为不能直接用其中一个孩子节点替代当前节点(放不下，如果孩子节点也有两个孩子那么有一个节点无法放，例如拿下面71节点替代...待删除节点有两个孩子 如果拿19或者71节点填补。虽然可以保证部分侧大于小于该节点，但是会引起合并的混乱.比如你若用71替代23节点。...所以，我们要分析我们要的这个点的属性：能够保证该点在这个位置仍满足二叉搜索树的性质(找到值最近的)，那么子树中哪个节点满足这样的关系呢？
parentOf(x)), RED); x = parentOf(parentOf(x)); } else { // 插入节点在父节点的右侧...2、待删除节点无孩子：直接删除即可。 3、待删除节点只有一个孩子节点：删除后，用孩子节点替换自己即可。 4、待删除节点有两个孩子：删除会复杂点，见下文介绍。...删除有两个子节点的父节点时： 删除过程：找到节点3右子树中最小的节点2，将3和2节点进行交换，然后删除3节点，3删除后，将原来的4节点变为5节点的子节点。...如果3节点和2节点被替换后，3节点下仍有两个孩子节点，重复利用上述规则删除即可。...这种方式的巧妙之处在于，总是将删除的当前节点向叶子节点方向移动，保证最后没有两个孩子节点时就可以执行真正的删除了，而利用右子树的最小节点与自身交换的动作并不会破坏二叉查找树的任何特性。
对应3节点(3-node)，保存两个Key，2-3查找树的定义如下： 对于2节点，该节点保存一个key及对应value，以及两个指向左右节点的节点，左节点也是一个2-3节点，所有的值都比key要小，有节点也是一个...对于3节点，该节点保存两个key及对应value，以及三个指向左中右的节点。...左节点也是一个2-3节点，所有的值均比两个key中的最小的key还要小；中间节点也是一个2-3节点，中间节点的key值在两个跟节点key值之间；右节点也是一个2-3节点，节点的所有key值比两个key中的最大的...2)3-节点：含有两个键和三条链接，左链接指向的2-3树中的键都小于该节点，中链接指向的2-3树中的键都位于该节点的两个键之间，右链接指向的2-3树中的键都大于该节点。...但是如果查找的节点结束于一个3-node节点，那么可能有点麻烦。 ?
长这样： 1、其中每一个节点都有两个孩子（称为2节点）或三个孩子（三节点）或者没有。...2、子节点排序参考二叉树 3、一个二节点包含一个元素和两个子节点（或没有子节点），一个三节点包含两个元素和三个子节点（或没有子节点） 4、2-3树中所有的叶子节点都在同一层次上。 ?...先看一下，要插入节点的父节点是个二节点，那就好办了，把那个二节点变成三节点，自然就有地方插入了。怎么变？把“6”提上去啊，图自己画。 如果要插入节点的父节点是个三节点，那就比较尴尬一点。...删除场景2：删除根节点，也是直接删了吧。 删除场景3：删除的节点位于一个二节点上。就像插入节点在三节点上一样的尴尬。不，更尴尬。 删除场景3.1：该节点的父节点为三节点：将父节点拆开下放一个节点。...在一个典型的B树应用中，要处理的硬盘数据量很大，因此无法一次全部装入内存。因此我们会对 B树进行调整， 使得B树的阶数 (或结点的元素)与硬盘存储的页面大小相匹配。
对应3节点(3-node)，保存两个Key，2-3查找树的定义如下： 对于2节点，该节点保存一个key及对应value，以及两个指向左右节点的节点，左节点也是一个2-3节点，所有的值都比key要小，有节点也是一个...对于3节点，该节点保存两个key及对应value，以及三个指向左中右的节点。...左节点也是一个2-3节点，所有的值均比两个key中的最小的key还要小；中间节点也是一个2-3节点，中间节点的key值在两个跟节点key值之间；右节点也是一个2-3节点，节点的所有key值比两个key中的最大的...2)3-节点：含有两个键和三条链接，左链接指向的2-3树中的键都小于该节点，中链接指向的2-3树中的键都位于该节点的两个键之间，右链接指向的2-3树中的键都大于该节点。...但是如果查找的节点结束于一个3-node节点，那么可能有点麻烦。
对于普通的2节点(2-node)，他保存1个key和左右两个自己点。对应3节点(3-node)，保存两个Key，2-3查找树的定义如下： 1. 要么为空，要么： 2....对于2节点，该节点保存一个key及对应value，以及两个指向左右节点的节点，左节点也是一个2-3节点，所有的值都比key有效，有节点也是一个2-3节点，所有的值比key要大。 3....对于3节点，该节点保存两个key及对应value，以及三个指向左中右的节点。...左节点也是一个2-3节点，所有的值均比两个key中的最小的key还要小；中间节点也是一个2-3节点，中间节点的key值在两个跟节点key值之间；右节点也是一个2-3节点，节点的所有key值比两个key中的最大的...但是如果查找的节点结束于一个3-node节点，那么可能有点麻烦。 ?
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
