，四个子节点（灰色节点），所以可以定义上面的图片为 4 阶 B 树 根节点 节点【10】即为根节点，特征：根节点拥有的子节点数量的上限和内部节点相同，如果根节点不是树中唯一节点的话，至少有俩个子节点（不然就变成单支了...否则的话这一节点已经满了，将它平均地分裂成两个节点： 从该节点的原有元素和新的元素中选择出中位数 小于这一中位数的元素放入左边节点，大于这一中位数的元素放入右边节点，中位数作为分隔值。...分隔值被插入到父节点中，这可能会造成父节点分裂，分裂父节点时可能又会使它的父节点分裂，以此类推。如果没有父节点（这一节点是根节点），就创建一个新的根节点（增加了树的高度）。...” 或“右孩子最左边的节点”)到父节点中，然后是移动之后的情况；如果没有，直接删除。...(5/2)-1=2），则可以向父结点借一个元素，然后将最丰满的相邻兄弟结点中上移最后或最前一个元素到父节点中，在这个实例中，右相邻兄弟结点中比较丰满（3 个元素大于 2），所以先向父节点借一个元素【23
删除3节点中数据 当待删除元素在2节点时，由于删除这个元素会导致2节点失去唯一的元素，引发树中某条路径的高度发生变化，为维持平衡，此时有两种方法。 先删除再对2-3树进行平衡调整。...想办法让这个被删除的元素不可能出现在2节点中。如果发现删除元素树2节点则会从兄弟节点或父节点借个元素，当前2节点变为3节点或临时4节点，然后再删除目标数据。...算法导论中说如果删除黑节点X带来黑色平衡破坏，让X的子节点变为黑-黑或红-黑。...将关注节点 a 的父节点 b 的颜色设置为黑色。 从关注节点 a 中去掉一个黑色，节点 a 就变成了单纯的红色或黑色。 将关注节点 a 的叔叔节点 e 设置为黑色，调整结束。...3.6.3 删除理解 多画图，不画图单看代码一会儿就眩晕了。 插入跟删除算法都是用到了递推，比如插入情况1，情况1的处理之后，关注节点从本身变成了它的祖父红色节点，这就是往根节点递推。
Tree) 红黑树是一种自平衡二叉搜索树（BST），且红黑树节点遵循以下规则： 每个节点只能是红色或黑色 根节点总是黑色的 红色节点的父或子节点都必然是黑色的(两个红色的节点不会相连) 任一节点到其所有后代...则根据不同的情况执行操作 2.3.1：n的uncle节点u是红色(uncle节点：父节点p父节点下的另一节点|n祖父节点g的另一子节点) a....进行比较，重复2、3步骤 搜索值大于当前key：将搜索值与同一节点中的下一个key进行比较，重复2、3步骤，直到精确匹配，或搜索值与叶子节点中的最后一个key值相比较 如果叶节点中的最后一个键值也不匹配...因为我们可以从任何节点（不仅是叶子）中删除key，而且从内部节点删除key时，我们将不得不重新排列节点的子节点。...从B树中删除键的各种情况(设删除键k所在节点为n)： k所在节点n为树中节点(非叶子节点也非根节点)，则根据以下不同的情况执行子节点key上移或合并完成删除操作 a.
平衡二叉树（Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。...从2-3树来看红黑树 一般我们接触最多的是二叉树，也就是一个父节点最多有两个子节点。2-3树与二叉树的不同之处在于，一个父节点可以有两个子节点，也可以有三个子节点，并且其也满足类似二叉搜索树的性质。...2-3树中插入2插入后2、3、4三个元素所在的叶子节点不再满足2-3树的定义，需要进行分裂，即抽出元素3融入父节点，2和4分裂为3的左右子节点，3融入5所在的父节点中。...2-3树到红黑树的改造然后我们将其改造成图3的形式；再将3节点的位于中间的子节点的父节点设置为父节点中那个红色的节点，如图4的所示；最后我们将图4的形式改为二叉树的样子，如图5所示。...从2-3树看红黑树性质1：每个节点要么是黑色，要么是红色。 2-3树中存在2节点和3节点，3节点中左侧的元素便是红色节点，而其他的节点便是黑色节点。 性质2：根节点是黑色。
向BTree中插入51，直接将51加入与4同节点中，此时该节点有2个key，满足每个节点不超过2个key的性质....向BTree中插入48，添加48到43|51所在的节点后，此时该节点不满足BTree性质，对其进行拆分，将中间的48加入到父节点（38所在的节点），43|48|51节点中的key被分成43和51两部分，...向BTree中插入1 向BTree中插入10，此时1|4|10节点不满足BTree性质，需要进行分裂，将4插入到父节点中，插入之后，父节点4|30|48也不满足BTree性质，继续对其进行分裂。...但此时父节点中的元素为空了，不满足BTree性质，于是对父节点采用从它的兄弟节点借或者合并的方法，而此时它的兄弟节点中也只有一个元素22，所以只能进行合并，将根节点的中的元素41和21合并，BTree的高度减少一层...所以BTree中查找元素的过程很简单，从根节点开始，每次可以定位可能所在的1个子节点，这样一路向下查询，如果在内部节点中没有找到，最后达到叶子节点，如果叶子节点也没有，则说明要查询的元素不在BTree中
重复12两个步骤，直到新的当前节点为空，则此地方就是添加节点的地方。 三.排序二叉树删除节点 被删除的节点是叶子节点，只需将它从其父节点中删除即可。...若被删除节点 p 的左、右子树均非空，有两种做法： 以 p 节点的中序前趋(见图3.1.1)或后继(见图3.1.2)替代 p 所指节点，然后再从原排序二叉树中删去中序前趋或后继节点即可。...将 pL 设为 p 的父节点 q 的左或右子节点（取决于 p 是其父节点 q 的左、右子节点），将 pR 设 为 p 节点的中序前趋节点 s 的右子节点（s 是 pL 最右下的节点，也就是 pL 子树中最大的节点...性质 5：从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。...由于以前的节点 G 是黑色，否则父节点 P 就不可能是红色，我们切换以前的父节 点 P 和节点 G 的颜色，使之满足性质 4，性质 5 也仍然保持满足，因为通过这三个节点中任何一个的 所有路径以前都通过节点
用一个图片来对比一下： 02 二叉查找树（Binary Search Tree） 从名字上不能看出，这种二叉树就是为了实现快速搜索而设计的，同时支持快速插入、删除。 那么它是如何实现的呢？...重点之处在于其对节点中元素大小的排列： 对于任一节点，其左子树中任一节点的值都必须小于当前节点的值，其右子树中任一节点的值都必须大于当前节点的值。...在了解二叉查找树的特点之后，我们用一个例子来体验一下二叉查找树的搜索效率： 假设我们需要找到数字65，判断思路很简单：从根节点开始，当前数字若小于节点中数字则向左寻找，反之若大于节点中数字则向右寻找。...： 1、需要删除的目标节点无子节点，直接删除即可 2、需要删除的目标节点只有一个子节点，直接将子节点指向父节点即可 3、需要删除的目标节点有两个子节点，则将右测数值大的节点上移，维持查找二叉树的数字排列规则...4、需要删除的目标节点有多级子节点，我们需要从目标节点的右侧所有子节点中寻找到最小的，然后将其替换至目标节点位置。
树是包含n（n为整数，大于0）个结点， n-1条边的有穷集，它有以下特点： ❝ 每个结点或者无子结点或者只有有限个子结点； 有一个特殊的结点,它没有父结点，称为根结点； 每一个非根节点有且只有一个父节点...； 树里面没有环路 ❞ 一些有关于树的概念： ❝ 结点的度：一个结点含有的子结点个数称为该结点的度； 树的度：一棵树中，最大结点的度称为树的度； 父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点...平衡二叉树（AVL）：一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树 ❞ B-树、B+树简介 B-树 简介 B-树，也称为B树，是一种平衡的多叉树（可以对比一下平衡二叉查找树...，并且该关键值存在父子节点中，那么删除该关键字，同时需要相应调整父节点的值。...如果删除20，因为关键字个数为3 > [5/2]=2，并且20是当前节点的边界值，且存在父子节点中，所以删除后，其父子节点也要响应调整。 ?
树是包含n（n为整数，大于0）个结点， n-1条边的有穷集，它有以下特点： 每个结点或者无子结点或者只有有限个子结点； 有一个特殊的结点,它没有父结点，称为根结点； 每一个非根节点有且只有一个父节点；...树里面没有环路 一些有关于树的概念： 结点的度：一个结点含有的子结点个数称为该结点的度； 树的度：一棵树中，最大结点的度称为树的度； 父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；...平衡二叉树（AVL）：一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树...（小）值，并且该关键值存在父子节点中，那么删除该关键字，同时需要相应调整父节点的值。...如果删除20，因为关键字个数为3 > ⌈5/2⌉-1=2，并且20是当前节点的边界值，且存在父子节点中，所以删除后，其父子节点也要响应调整。 ?
一颗普通的树如下: 树是包含n（n为整数，大于0）个结点， n-1条边的有穷集，它有以下特点： ❝ 每个结点或者无子结点或者只有有限个子结点； 有一个特殊的结点,它没有父结点，称为根结点； 每一个非根节点有且只有一个父节点...； 树里面没有环路 ❞ 一些有关于树的概念： ❝ 结点的度：一个结点含有的子结点个数称为该结点的度； 树的度：一棵树中，最大结点的度称为树的度； 父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点...平衡二叉树（AVL）：一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树 ❞ B-树、B+树简介 B-树 简介 B-树，也称为B树，是一种平衡的多叉树（可以对比一下平衡二叉查找树...，并且该关键值存在父子节点中，那么删除该关键字，同时需要相应调整父节点的值。...，并且删除的关键字存在于父子节点中，那么需要相应调整父子节点的值 如果删除20，因为关键字个数为3 > [5/2]=2，并且20是当前节点的边界值，且存在父子节点中，所以删除后，其父子节点也要响应调整
）； 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点，实际上这些结点不存在，指向这些结点的指针都为null)； 每个非终端结点中包含有n个关键字信息： (n...删除操作 首先查找B树中需删除的元素,如果该元素在B树中存在，则将该元素在其结点中进行删除，如果删除该元素后，首先判断该元素是否有左右孩子结点，如果有，则上移孩子结点中的某相近元素到父节点中，然后是移动之后的情况...(5/2)-1=2），则可以向父结点借一个元素，然后将最丰满的相邻兄弟结点中上移最后或最前一个元素到父节点中（有没有看到红黑树中左旋操作的影子?）...，在这个实例中，右相邻兄弟结点中比较丰满（3个元素大于2），所以先向父节点借一个元素W下移到该叶子结点中，代替原来S的位置，S前移；然后X在相邻右兄弟结点中上移到父结点中，最后在相邻右兄弟结点中删除X，...；首先移动父结点中的元素（该元素在两个需要合并的两个结点元素之间）下移到其子结点中，然后将这两个结点进行合并成一个结点。
这次我们从这些数据结构的底层逻辑设计出发，不牵扯任何代码层面上的内容。 二三四树 定义 ?...依次插入1、2、3节点 ? 插入4节点，需要将4节点分裂成3个2节点的操作 ? ? ? ? ? ? 至此，插入逻辑介绍完毕 删除 节点的删除逻辑，和二叉树的删除逻辑区别不大。...如果是叶子节点，可以直接删除；如果是非叶子节点，需要转换为后继/前驱节点的删除方式，所有都可以转换为极值的删除 非2节点的删除 ?...2节点的删删除 对于2节点的删除，需要转换为3、4节点中节点的删除 父节点为非2节点，兄弟节点是2节点 ? 父节点是非2节点，兄弟节点是非2节点 ? 父节点是2节点，兄弟节点非2节点 ?...父节点是2节点，兄弟节点也是2节点 ? 至此，我们的234树的插入和删除操作介绍完了。搞清楚234树的插入和删除操作将是后续红黑树、B树、B+树的前置条件。
长这样： 1、其中每一个节点都有两个孩子（称为2节点）或三个孩子（三节点）或者没有。...2、子节点排序参考二叉树 3、一个二节点包含一个元素和两个子节点（或没有子节点），一个三节点包含两个元素和三个子节点（或没有子节点） 4、2-3树中所有的叶子节点都在同一层次上。 ?...先看一下，要插入节点的父节点是个二节点，那就好办了，把那个二节点变成三节点，自然就有地方插入了。怎么变？把“6”提上去啊，图自己画。 如果要插入节点的父节点是个三节点，那就比较尴尬一点。...删除场景2：删除根节点，也是直接删了吧。 删除场景3：删除的节点位于一个二节点上。就像插入节点在三节点上一样的尴尬。不，更尴尬。 删除场景3.1：该节点的父节点为三节点：将父节点拆开下放一个节点。...在B树上的查找过程是一个顺指针查找节点和在节点中查找关键字的交叉过程。 关于B树的插入删除，和2-3树一样，只不过阶数可能会大了些。
然后为该锚分配一个简称为节点的SCNNode。...该函数将返回一个SCNNode，如右箭头所示。所以基本上，它输入一个平面锚并输出一个节点。 你应该在一个函数中错误地返回一个预期返回'SCNNode'的函数中的Missing return。...您现在正在学习如何在代码中应用它。 飞机位置 所以，就像我们为手表所做的步骤一样，我们需要定位它。将平面节点放在检测到的曲面的中心。...let planeNode = createPlane(planeAnchor: planeAnchor) 然后，将planeNode作为表示平面的节点的子节点。...ARPlaneAnchor 更新平面锚点的尺寸的方法，我们首先必须将其从场景中删除，然后将其添加回来。对于的所有子节点的节点，从父节点删除它们。
从判定树可以看出，查找成功时的查找长度为从根结点到目的结点的路径上的结点数，而查找不成功时的查找长度为从根结点到对应失败结点的父结点的路径上的结点数；每个结点值均大于其左子结点值，且均小于右子结点值。...，右部分包含的关键字放到新的结点中，中间位置的节点插入到原结点的父结点中。...image.png 删除8：因为删除8后，不破坏树的性质，所以直接删除即可 image.png 删除16：这导致该节点只剩下一个13节点，不满足节点内元素个数为2~4个的要求了。所以需要调整。...每个父结点的元素都出现在子结点中，是子结点的最大（或最小）元素 所有的叶子结点都位于同一层 所有叶子节点包含全部关键字及指向相应记录的指针，而且叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来...所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。 4.
二叉树（Binary Tree） 任何一个节点的子节点数量不超过2（子节点分为左节点与右节点）。 ? 2.1 满二叉树（Full Binary Tree） 所有叶子结点都在最后一层。...若子树不空，则子树上所有节点的值均小于或等于根节点的值。 若右子树不空，则右子树所有节点的值均大于或等于根节点的值。 左、右子树也分别为二叉排序树，或是一颗空树。 ?...每个红色节点必须有两个黑色的子节点（从每个叶子到根的所有路径上不能有两个连续的红色节点）。 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。 ? ---- 3....B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。...B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点
j，则其左子树的深度必为j或j+1图片什么是大顶堆（最大堆）大顶堆是一种完全二叉树，其每个父节点的值都大于或等于其子节点的值，即根节点的值最大。...每个节点的两个子节点顺序没做要求，和之前的二叉查找树不一样。图片什么是小顶堆（最小堆）小顶堆是一种完全二叉树，其每个父节点的值都小于或等于其子节点的值，即根节点的值最小。...方便操作，一般数组的下标0不存储，直接从1节点存储。堆其实就是利用完全二叉树的结构来维护一个数组数据下表为k的节点左子节点下标为2*k的节点。右子节点就是下表为2*k+1的节点。...0或1开始依次存放数据，但是顺序需要满足堆的特性如何让堆满足：不断比较新节点 arrk和对应父节点arrk/2的大小，根据情况交互元素位置直到找到的父节点比当前新增节点大则结束图片2.大顶堆构编码实现大顶堆...（最大堆）大顶堆是一种完全二叉树，其每个父节点的值都大于或等于其子节点的值，即根节点的值最大图片编码实现public class Heap { //用数组存储堆中的元素 private int
（也就是说非叶子节点是不会存在空链接的） 由于2-3-4树是一颗阶数为4的B树，所以它会存在以下节点： 2节点 3节点 4节点 2节点中存放着一个key[X]，两个指针，分别指向小于X的子节点和大于X的子节点...；3节点中存放在两个key[X,Y],三个指针，分别指向小于X的子节点，介于X~Y之间的子节点和大于Y的子节点；4节点可依此类推。...因此我们有两种方案去解决这个问题： 第一种方案，先删除这个2节点，然后对树进行平衡调整。 第二种方案，我们想办法让这个被删除的元素不可能出现在2节点中。...从而能够直接删除某个元素（现在这个元素不在2节点中了）。 ? 2-3树的删除 再看红黑树 ?...因此，如果实在无法理解【双重黑】，【既黑又红】，那么直接按照“某条路径欠黑，所以要想办法补充一个黑色节点”这个思路来思考吧！ 还是删除阶段，四个删除场景该如何记忆？
而删除分类也只需将其直属子分类的 pid 改成该分类的 pid即可。但对于查询该分类的所有上级至顶级分类或查询就不友好了，需要进行递归。...INSERT INTO CategoryTree(ancestor,descendant,distance) VALUES(10,10,0) 删除 如果删除分类同时也删除其所有下级分类那好办，先找出该节点所有子级节点逐个删除...// 当子节点的父节点中超过该节点到 4节点距离时，距离- 1 update CategoryTree set distance = distance-1 where descendant=6 and...descendant=4 // 删除4节点本身 移动 节点的移动没有很好的解决方法，因为新位置所在的深度、路径都可能不一样，这就导致移动操作不是仅靠UPDATE语句能完成的，这里选择删除+插入实现移动...删除id=5节点的所有记录 DELETE FROM CategoryTree WHERE descendant=5 然后配合上面一节的插入操作实现移动。
二叉查找树 二叉查找树，也称有序二叉树（ordered binary tree），或已排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树： 若任意节点的左子树不空，...如图所示，图中M结点就是一个二节点，M左边的EJ节点是一个三节点。依然是大的数据放右边，小的数据放左边。...此时我们向该树重如果该数可以直接放入二节点中，就直接进去，但如果正好需要放在三节点中，就像图中一样，Z正好要放在SX中。...那么我们需要将该节点分裂成两个节点，并将中间的数提到父节点中去，就像图中将X放在了R旁边。当然如果将子节点提到父节点的时候导致了父节点里的数超过了两个，就继续向上提，直到满足了为止。 ?...但对于插入删除等操作效率提高很多。
领取专属 10元无门槛券
手把手带您无忧上云
