区块链技术博客
www.b2bchain.cn

数据结构与算法-基础(十五)红黑树(3)删除元素求职学习资料

本文介绍了数据结构与算法-基础(十五)红黑树(3)删除元素求职学习资料,有助于帮助完成毕业设计以及求职,是一篇很好的资料。

对技术面试,学习经验等有一些体会,在此分享。

摘要

红黑树删除节点,和 B 树删除节点的情况非常的接近。理解红黑树删除节点之后的恢复操作前,再过一下 B 树的删除逻辑,这样会更好的理解红黑树的删除逻辑。各种处理操作就不会离开一个主要思想,就是红黑树的 5 条性质。

在 B 树中,最后真正需要删除的一定是叶子节点,就算删除的不是叶子节点,也可以先和它的前驱或者后继交换位置之后,删除被交换到叶子的节点。红黑树可以简单的移动一下节点的位置,就能变成 B 树(如下图所示),所以红黑树的删除就可以转换为对 B 树的删除。

数据结构与算法-基础(十五)红黑树(3)删除元素

RBT-remove2

红黑树的节点被删除之后,就要判断是否还符合红黑树性质,若不符合性质时,就要做恢复红黑树的处理。判断的依据就是红黑树的 5 条性质,尤其是性质 4。

红黑树的 5 条性质:

  1. 节点必须是 RED 或者 BLACK;
  2. 根节点是 BLACK;
  3. 叶子节点都是 BLACK,这里要特别留意,叶子节点存在两个空节点,只有一个子树的节点,另外一个不存在的子树也是一个空节点。
  4. RED 节点的子节点都是 BLACK,RED 节点的父节点也都是 BLACK。保证从根节点到叶子节点的所有路径上,不会出现 2 个连续的 RED 节点
  5. 从任意一个节点到叶子节点的所有路径上包含的 BLACK 节点数量相同。

首先看删除的叶子节点是 RED,那么就不需要做任何处理,依然满足红黑树的性质。比如删除元素 17、33、55 和 72。如下图所示:

数据结构与算法-基础(十五)红黑树(3)删除元素

RBT-remove3

接下来,删除的叶子节点是 BLACK,就有 3 种情况,首先第一种就是有两个 RED 子节点(如下图元素 25),因为有两个叶子节点,所以若要删除也是找子节点替换,然后删除与它交换的叶子节点,不可能直接删除的,所以不考虑。第二种呢,是有一个 RED 子节点(比如元素 46、76),这种情况就可以直接拿这个 RED 子节点替换 BLACK 节点,然后将这个 RED 子节点染成 BLACK,依然满足红黑树的性质。

数据结构与算法-基础(十五)红黑树(3)删除元素

RBT-remove4

第三种就是它既是 BLACK,也是叶子节点(比如元素 88),删除这个节点会造成 B 树下溢出。那么就要做调整来消除下溢的影响。

这里要拿它的兄弟节点(sibling)来帮助处理。如果它的 sibling 是 BLACK时,若 sibling 至少有一个 RED 的子节点,就可以根据它的失衡情况做旋转,旋转之后的中心节点染成 parent 的颜色,他的左右节点就染成 BLACK。

sibling 一个 RED 节点都没有,而 parent 是 RED 时,就直接将 sibling 染成 RED,parent 染成 BLACK,就满足了红黑树的性质。但是 parent 是 BLACK 时,就会导致 parent 下溢,那么就把 parent 当作被删除的节点去处理即可。

sibling 是 RED,那么就需要将 sibling 染成 BLACK,parent 染成 RED,进行旋转之后,就会回到 sibling 是 BLACK 的情况。然后继续按照 sibling 是 BLACK 的情况继续处理。

现在开始代码实现删除红黑树的节点之后的处理:

删除节点之后,当前节点位置要不就是不存在,为 null,要不就是其他节点被替换到当前节点。所以下面函数中传递的参数就是删除位置的节点:

void afterRemove(Node<E> node) { }

这里要判断当前节点的颜色,如果是红色,那么就染黑处理。下溢情况会再次调用 afterRemove 函数。

// 如果删除的节点是红色 // 或者 用于取代删除节点的子节点是红色 if (isRed(node)) {   black(node);   return; }

接下来就是要判断,删除的节点是否是根节点,如果是,就根节点,也可以不用操作:

Node<E> parent = node.parent; // 删除的是根节点 if (parent == null) return;

下面就是被删除的节点是黑色节点,那么这时候就要看它的兄弟节点是否可以拿出来一个节点来补位。这里先以兄弟节点是当前节点的右侧来处理,兄弟节点是当前节点的左侧刚好与前面情况相反。

boolean left = parent.left == null || node.isLeftChild(); Node<E> sibling = left ? parent.right : parent.left; if (left) { // 被删除的节点在左侧,兄弟节点在右侧     // 实现逻辑  }

这时,如果兄弟节点是红色,那么就可以替换过来:

if (isRed(sibling)) { // 兄弟节点是红色   black(sibling);   red(parent);   rotateLeft(parent);   // 更换兄弟   sibling = parent.right; }

摘要

红黑树删除节点,和 B 树删除节点的情况非常的接近。理解红黑树删除节点之后的恢复操作前,再过一下 B 树的删除逻辑,这样会更好的理解红黑树的删除逻辑。各种处理操作就不会离开一个主要思想,就是红黑树的 5 条性质。

在 B 树中,最后真正需要删除的一定是叶子节点,就算删除的不是叶子节点,也可以先和它的前驱或者后继交换位置之后,删除被交换到叶子的节点。红黑树可以简单的移动一下节点的位置,就能变成 B 树(如下图所示),所以红黑树的删除就可以转换为对 B 树的删除。

数据结构与算法-基础(十五)红黑树(3)删除元素

RBT-remove2

红黑树的节点被删除之后,就要判断是否还符合红黑树性质,若不符合性质时,就要做恢复红黑树的处理。判断的依据就是红黑树的 5 条性质,尤其是性质 4。

红黑树的 5 条性质:

  1. 节点必须是 RED 或者 BLACK;
  2. 根节点是 BLACK;
  3. 叶子节点都是 BLACK,这里要特别留意,叶子节点存在两个空节点,只有一个子树的节点,另外一个不存在的子树也是一个空节点。
  4. RED 节点的子节点都是 BLACK,RED 节点的父节点也都是 BLACK。保证从根节点到叶子节点的所有路径上,不会出现 2 个连续的 RED 节点
  5. 从任意一个节点到叶子节点的所有路径上包含的 BLACK 节点数量相同。

首先看删除的叶子节点是 RED,那么就不需要做任何处理,依然满足红黑树的性质。比如删除元素 17、33、55 和 72。如下图所示:

数据结构与算法-基础(十五)红黑树(3)删除元素

RBT-remove3

接下来,删除的叶子节点是 BLACK,就有 3 种情况,首先第一种就是有两个 RED 子节点(如下图元素 25),因为有两个叶子节点,所以若要删除也是找子节点替换,然后删除与它交换的叶子节点,不可能直接删除的,所以不考虑。第二种呢,是有一个 RED 子节点(比如元素 46、76),这种情况就可以直接拿这个 RED 子节点替换 BLACK 节点,然后将这个 RED 子节点染成 BLACK,依然满足红黑树的性质。

数据结构与算法-基础(十五)红黑树(3)删除元素

RBT-remove4

第三种就是它既是 BLACK,也是叶子节点(比如元素 88),删除这个节点会造成 B 树下溢出。那么就要做调整来消除下溢的影响。

这里要拿它的兄弟节点(sibling)来帮助处理。如果它的 sibling 是 BLACK时,若 sibling 至少有一个 RED 的子节点,就可以根据它的失衡情况做旋转,旋转之后的中心节点染成 parent 的颜色,他的左右节点就染成 BLACK。

sibling 一个 RED 节点都没有,而 parent 是 RED 时,就直接将 sibling 染成 RED,parent 染成 BLACK,就满足了红黑树的性质。但是 parent 是 BLACK 时,就会导致 parent 下溢,那么就把 parent 当作被删除的节点去处理即可。

sibling 是 RED,那么就需要将 sibling 染成 BLACK,parent 染成 RED,进行旋转之后,就会回到 sibling 是 BLACK 的情况。然后继续按照 sibling 是 BLACK 的情况继续处理。

现在开始代码实现删除红黑树的节点之后的处理:

删除节点之后,当前节点位置要不就是不存在,为 null,要不就是其他节点被替换到当前节点。所以下面函数中传递的参数就是删除位置的节点:

void afterRemove(Node<E> node) { }

这里要判断当前节点的颜色,如果是红色,那么就染黑处理。下溢情况会再次调用 afterRemove 函数。

// 如果删除的节点是红色 // 或者 用于取代删除节点的子节点是红色 if (isRed(node)) {   black(node);   return; }

接下来就是要判断,删除的节点是否是根节点,如果是,就根节点,也可以不用操作:

Node<E> parent = node.parent; // 删除的是根节点 if (parent == null) return;

下面就是被删除的节点是黑色节点,那么这时候就要看它的兄弟节点是否可以拿出来一个节点来补位。这里先以兄弟节点是当前节点的右侧来处理,兄弟节点是当前节点的左侧刚好与前面情况相反。

boolean left = parent.left == null || node.isLeftChild(); Node<E> sibling = left ? parent.right : parent.left; if (left) { // 被删除的节点在左侧,兄弟节点在右侧     // 实现逻辑  }

这时,如果兄弟节点是红色,那么就可以替换过来:

if (isRed(sibling)) { // 兄弟节点是红色   black(sibling);   red(parent);   rotateLeft(parent);   // 更换兄弟   sibling = parent.right; }

摘要

红黑树删除节点,和 B 树删除节点的情况非常的接近。理解红黑树删除节点之后的恢复操作前,再过一下 B 树的删除逻辑,这样会更好的理解红黑树的删除逻辑。各种处理操作就不会离开一个主要思想,就是红黑树的 5 条性质。

在 B 树中,最后真正需要删除的一定是叶子节点,就算删除的不是叶子节点,也可以先和它的前驱或者后继交换位置之后,删除被交换到叶子的节点。红黑树可以简单的移动一下节点的位置,就能变成 B 树(如下图所示),所以红黑树的删除就可以转换为对 B 树的删除。

数据结构与算法-基础(十五)红黑树(3)删除元素

RBT-remove2

红黑树的节点被删除之后,就要判断是否还符合红黑树性质,若不符合性质时,就要做恢复红黑树的处理。判断的依据就是红黑树的 5 条性质,尤其是性质 4。

红黑树的 5 条性质:

  1. 节点必须是 RED 或者 BLACK;
  2. 根节点是 BLACK;
  3. 叶子节点都是 BLACK,这里要特别留意,叶子节点存在两个空节点,只有一个子树的节点,另外一个不存在的子树也是一个空节点。
  4. RED 节点的子节点都是 BLACK,RED 节点的父节点也都是 BLACK。保证从根节点到叶子节点的所有路径上,不会出现 2 个连续的 RED 节点
  5. 从任意一个节点到叶子节点的所有路径上包含的 BLACK 节点数量相同。

首先看删除的叶子节点是 RED,那么就不需要做任何处理,依然满足红黑树的性质。比如删除元素 17、33、55 和 72。如下图所示:

数据结构与算法-基础(十五)红黑树(3)删除元素

RBT-remove3

接下来,删除的叶子节点是 BLACK,就有 3 种情况,首先第一种就是有两个 RED 子节点(如下图元素 25),因为有两个叶子节点,所以若要删除也是找子节点替换,然后删除与它交换的叶子节点,不可能直接删除的,所以不考虑。第二种呢,是有一个 RED 子节点(比如元素 46、76),这种情况就可以直接拿这个 RED 子节点替换 BLACK 节点,然后将这个 RED 子节点染成 BLACK,依然满足红黑树的性质。

数据结构与算法-基础(十五)红黑树(3)删除元素

RBT-remove4

第三种就是它既是 BLACK,也是叶子节点(比如元素 88),删除这个节点会造成 B 树下溢出。那么就要做调整来消除下溢的影响。

这里要拿它的兄弟节点(sibling)来帮助处理。如果它的 sibling 是 BLACK时,若 sibling 至少有一个 RED 的子节点,就可以根据它的失衡情况做旋转,旋转之后的中心节点染成 parent 的颜色,他的左右节点就染成 BLACK。

sibling 一个 RED 节点都没有,而 parent 是 RED 时,就直接将 sibling 染成 RED,parent 染成 BLACK,就满足了红黑树的性质。但是 parent 是 BLACK 时,就会导致 parent 下溢,那么就把 parent 当作被删除的节点去处理即可。

sibling 是 RED,那么就需要将 sibling 染成 BLACK,parent 染成 RED,进行旋转之后,就会回到 sibling 是 BLACK 的情况。然后继续按照 sibling 是 BLACK 的情况继续处理。

现在开始代码实现删除红黑树的节点之后的处理:

删除节点之后,当前节点位置要不就是不存在,为 null,要不就是其他节点被替换到当前节点。所以下面函数中传递的参数就是删除位置的节点:

void afterRemove(Node<E> node) { }

这里要判断当前节点的颜色,如果是红色,那么就染黑处理。下溢情况会再次调用 afterRemove 函数。

// 如果删除的节点是红色 // 或者 用于取代删除节点的子节点是红色 if (isRed(node)) {   black(node);   return; }

接下来就是要判断,删除的节点是否是根节点,如果是,就根节点,也可以不用操作:

Node<E> parent = node.parent; // 删除的是根节点 if (parent == null) return;

下面就是被删除的节点是黑色节点,那么这时候就要看它的兄弟节点是否可以拿出来一个节点来补位。这里先以兄弟节点是当前节点的右侧来处理,兄弟节点是当前节点的左侧刚好与前面情况相反。

boolean left = parent.left == null || node.isLeftChild(); Node<E> sibling = left ? parent.right : parent.left; if (left) { // 被删除的节点在左侧,兄弟节点在右侧     // 实现逻辑  }

这时,如果兄弟节点是红色,那么就可以替换过来:

if (isRed(sibling)) { // 兄弟节点是红色   black(sibling);   red(parent);   rotateLeft(parent);   // 更换兄弟   sibling = parent.right; }

部分转自互联网,侵权删除联系

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 数据结构与算法-基础(十五)红黑树(3)删除元素求职学习资料
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们