Skip to main content

红黑树学习笔记-删除节点

Submitted by taotao on Sat, 02/23/2019 - 17:58

概述

根据前一篇文章中介绍的红黑树性质,现在我们需要考虑如何删除一个节点以及删除一个节点后,是否还能够满足它的5个特性,如果不满足我们需要如何调整使之满足红黑树的特性。

场景分析

被删除的节点有左子树或者右子树

case1case1_sub_tree_problem

如果被删除的节点和它的子节点为黑色,那么会破坏性质4: 每个从根节点到叶子节点的路径上必须包含相同数量的黑色节点,下面详细介绍:

被删除的节点的父节点为红色

node_balck

被删除的父节点为黑色

sub_tree_all_black

 

被删除的节点的叔叔节点有一个儿子是红色

ddd

被删除的节点的叔叔节点的两个儿子都是红色

case_red_black_del_node_all_are_red

 

Tags

Add new comment

Plain text

  • No HTML tags allowed.
  • Lines and paragraphs break automatically.
  • Web page addresses and email addresses turn into links automatically.