你开心就好
RTEMS调度器-EDF调度演示
编辑
2025-04-16
记录知识
0

之前我们讨论了EDF调度器的实施策略，在rtems上，我们可以通过修改测试程序来演示一下edf调度器对任务调度的现象。

测试代码

为了能够开始测试代码，我们需要首先创建三个任务，如下

  Task_name[ 1 ] =  rtems_build_name( 'T', 'A', '1', ' ' );
  Task_name[ 2 ] =  rtems_build_name( 'T', 'A', '2', ' ' );
  Task_name[ 3 ] =  rtems_build_name( 'T', 'A', '3', ' ' );
  for ( index = 1 ; index <= 3 ; index++ ) {
    status = rtems_task_create(
      Task_name[ index ],      
      1,
      RTEMS_MINIMUM_STACK_SIZE,
      RTEMS_DEFAULT_MODES,     
      RTEMS_DEFAULT_ATTRIBUTES,
      &Task_id[ index ]        
    );  
    directive_failed( status, "rtems_task_create loop" );
  }
  for ( index = 1 ; index <= 3 ; index++ ) {
    status = rtems_task_start( Task_id[ index ], Task_1_through_3, index );
    directive_failed( status, "rtems_task_start loop" );
  }

3个任务都运行了函数Task_1_through_3,我们可以查看Task_1_through_3函数的实现如下

rtems_task Task_1_through_3(
  rtems_task_argument argument
)
{
  rtems_id          rmid;
  rtems_id          test_rmid;
  rtems_time_of_day time;
  rtems_status_code status;
  int start = 0;

  status = rtems_rate_monotonic_create( argument, &rmid );
  directive_failed( status, "rtems_rate_monotonic_create" );

  status = rtems_rate_monotonic_ident( argument, &test_rmid );
  directive_failed( status, "rtems_rate_monotonic_ident" );

  if ( rmid != test_rmid ) {
     printf( "RMID's DO NOT MATCH (0x%" PRIxrtems_id " and 0x%" PRIxrtems_id ")\n",
             rmid, test_rmid );
     rtems_test_exit( 0 );
  }

  switch ( argument ) {
    case 1:
      while ( FOREVER ) {
        status = rtems_rate_monotonic_period( rmid, RTEMS_MILLISECONDS_TO_TICKS(8000));
        directive_failed( status, "rtems_rate_monotonic_period" );
	status = rtems_clock_get_tod( &time );
    	directive_failed( status, "rtems_clock_get_tod" );
	put_name( Task_name[ argument ], FALSE );
	print_time( " - executing - ", &time, "\n" );
        rtems_task_wake_after(RTEMS_MILLISECONDS_TO_TICKS(2000));
	status = rtems_clock_get_tod( &time );
    	directive_failed( status, "rtems_clock_get_tod" );
	put_name( Task_name[ argument ], FALSE );
	print_time( " - finished - ", &time, "\n" );

	if ( time.second >= 30 && time.minute == 0) {
          printf( "PERIODS CHECK OK 30s\n");
          TEST_END();
          rtems_test_exit( 0 );
        }
      }
      case 2:
        while ( FOREVER ) {
          status = rtems_rate_monotonic_period( rmid, RTEMS_MILLISECONDS_TO_TICKS(6000));
          directive_failed( status, "rtems_rate_monotonic_period" );
	  status = rtems_clock_get_tod( &time );
    	  directive_failed( status, "rtems_clock_get_tod" );
	  put_name( Task_name[ argument ], FALSE );
	  print_time( " - executing - ", &time, "\n" );
          rtems_task_wake_after(RTEMS_MILLISECONDS_TO_TICKS(3000));
          directive_failed( status, "rtems_task_wake_after" );
	  status = rtems_clock_get_tod( &time );
    	  directive_failed( status, "rtems_clock_get_tod" );
	  put_name( Task_name[ argument ], FALSE );
	  print_time( " - finished - ", &time, "\n" );
	}
	break;
      case 3:
        while ( FOREVER ) {
          status = rtems_rate_monotonic_period( rmid, RTEMS_MILLISECONDS_TO_TICKS(4000));
          directive_failed( status, "rtems_rate_monotonic_period" );
	  status = rtems_clock_get_tod( &time );
    	  directive_failed( status, "rtems_clock_get_tod" );
	  put_name( Task_name[ argument ], FALSE );
	  print_time( " - executing - ", &time, "\n" );
	  rtems_task_wake_after(RTEMS_MILLISECONDS_TO_TICKS(1000));
          directive_failed( status, "rtems_task_wake_after" );
	  status = rtems_clock_get_tod( &time );
    	  directive_failed( status, "rtems_clock_get_tod" );
	  put_name( Task_name[ argument ], FALSE );
	  print_time( " - finished - ", &time, "\n" );
	}
        break;
    }
}

上面的代码,我在每个任务中，按照要求定义了三个任务如下

  • A任务运行时间为2s，A任务的截止时间(周期)是8s
  • B任务运行时间为3s，B任务的截止时间(周期)是6s
  • C任务运行时间为1s，C任务的截止时间(周期)是4S

对于任务的周期创建，这里通过标准接口rtems_rate_monotonic_create和rtems_rate_monotonic_period来设置。其中RTEMS_MILLISECONDS_TO_TICKS会将ms转换成系统的tick值

对于任务的运行时间，这里通过rtems_task_wake_after来实现，它会默认将进程让出就绪队列，然后休眠超时后，将任务加入就绪队列。

当系统任务运行结束时间超过30s时，会主动退出此测试程序

接下来我们编译运行，查看运行结果

输出结果

将上述代码运行之后，可以得到如下日志

TA3  - executing - 09:00:00   04/16/2025 
TA3  - finished - 09:00:01   04/16/2025  
TA2  - executing - 09:00:02   04/16/2025 
TA1  - executing - 09:00:04   04/16/2025 
TA3  - executing - 09:00:04   04/16/2025 
TA2  - finished - 09:00:05   04/16/2025  
TA3  - finished - 09:00:05   04/16/2025  
TA1  - finished - 09:00:06   04/16/2025  
TA2  - executing - 09:00:08   04/16/2025 
TA3  - executing - 09:00:08   04/16/2025 
TA3  - finished - 09:00:09   04/16/2025  
TA2  - finished - 09:00:11   04/16/2025  
TA1  - executing - 09:00:12   04/16/2025 
TA3  - executing - 09:00:12   04/16/2025 
TA3  - finished - 09:00:13   04/16/2025  
TA2  - executing - 09:00:14   04/16/2025 
TA1  - finished - 09:00:14   04/16/2025  
TA3  - executing - 09:00:16   04/16/2025 
TA2  - finished - 09:00:17   04/16/2025  
TA3  - finished - 09:00:17   04/16/2025  
TA1  - executing - 09:00:20   04/16/2025 
TA2  - executing - 09:00:20   04/16/2025 
TA3  - executing - 09:00:20   04/16/2025 
TA3  - finished - 09:00:21   04/16/2025  
TA1  - finished - 09:00:22   04/16/2025  
TA2  - finished - 09:00:23   04/16/2025  
TA3  - executing - 09:00:24   04/16/2025 
TA3  - finished - 09:00:25   04/16/2025  
TA2  - executing - 09:00:26   04/16/2025 
TA1  - executing - 09:00:28   04/16/2025 
TA3  - executing - 09:00:28   04/16/2025 
TA2  - finished - 09:00:29   04/16/2025    
TA3  - finished - 09:00:29   04/16/2025    
TA1  - finished - 09:00:30   04/16/2025    
PERIODS CHECK OK 30s

分析结果

其实根据日志的输出，已经很明显看出edf调度器的工作机制了，这里逐步分析一下，方便加深edf调度算法的理解

我逐步分析如下

  • 任务3优先级最高，在1s时直接执行完成，然后执行任务2，预计第5s完成
  • 在第4s时，任务1作为优先级最低开始执行，预计在第6s时结束
  • 因为任务3的周期是4s，所以从第4s开始，任务3也开始执行，预计第5s完成
  • 我们知道任务2的周期是6s，任务3的周期是4s，第8s是第二个周期。而第6s之后，所有任务都完成了。
  • 从第8s开始，任务2和任务3都得到执行，第12s时任务1得以执行
  • 以此类推

根据上面的分析，我们可以发现

  1. 任务3优先级最高，任务2次之，任务1最低。由截止时间决定
  2. 在一个周期内，任务一定会运行一次

根据上面的推论，我们还可以发现

  • 任务1优先级最低，所以等到任务2和任务3完成之后才能得以运行，也就是一个周期的第3+1s时
  • 同理，任务2优先级次之，它需要等到任务1完成之后得以执行
  • 同理，任务1优先级最高，所以每次周期开始，它都直接运行

根据上面的日志，我们可能发现，任务2每次在周期内都是在第2秒才运行，也就是2/8/20/26。而任务1时间只有1s中，那么我们可以推论，此时操作系统中，还有一个任务周期为1s的任务。它的优先级在任务3和任务2之间。不过此任务不影响我们对edf任务调度的观测和推论。

最后，我们关心任务的执行此时，如下

# cat task.log | grep TA1 | wc -l
8
# cat task.log | grep TA2 | wc -l
10
# cat task.log | grep TA3 | wc -l
16

我们以30s作为任务结束为计数，可以得到如下

  • TA1 = 8/2 times * 8s = 32s
  • TA2 = 10/2 times * 6s = 30s
  • TA3 = 16/2 times * 4s = 32s

可以发现，完全符合edf的调度情况

总结

根据上面的演示，我们清晰的了解了edf调度的运行机制。

阅读全文
安装tensorflow2
编辑
2025-04-14
记录知识
0

本文基于linux发行版安装tensorflow2程序，用作后期的调研评估，如下是步骤

安装软件

安装步骤如下

pip install -i https://mirrors.aliyun.com/pypi/simple --upgrade pip
pip install -i https://mirrors.aliyun.com/pypi/simple tensorflow==2.2.0
pip install -i https://mirrors.aliyun.com/pypi/simple jupyterlab
pip install -i https://mirrors.aliyun.com/pypi/simple numpy==1.20.0
pip install -i https://mirrors.aliyun.com/pypi/simple protobuf==3.20.1

值得注意的是，这里protobuf和numpy都是降级了的

jupyter的配置

为了开发tensorflow2，我们需要使用jupyter开放一个端口，默认8888，如下

{
        "NotebookApp" : {
                "ip": "*",
                "port": 8888,
                "password": "",
                "open_browser": false,
                "token": "",
                "allow_root": true
        }
}

运行jupyter

为了运行jupyter，可以新建一个shell脚本，名字为run_jupyter.sh，内容如下

jupyter lab --config jupyter_config.json

打开端口

上述动作完成之后，打开端口可以看到如下

image.png

此时我们点击Notebook下的python3进行测试

测试

这里直接打印tensorflow2的版本即可，如下

image.png

至此，tensorflow的安装完成了，接下来继续调研tensorflow2

阅读全文
RTEMS调度器-最早截止优先级(EDF)调度算法
编辑
2025-04-14
记录知识
0

我们之前介绍了优先级调度算法和简单优先级调度算法，这两种调度算法都是基于优先级的值来调度的，也就是每个任务在创建的时候，会分配一个优先级，那么较高优先级始终比较低优先级优先调度。今天我们介绍rtems中另一种调度算法，EDF，最早截止事件调度算法

介绍EDF调度算法

对于最早截止时间调度算法而言，默认情况下会给任务分配一个截止事件，调度器根据每个任务的截止时间来确定优先级，它需要预设一个周期，当任务的实际运行时间越靠近周期设置时间，那么任务的优先级越高。这里优先级的动态调整通过的是timer来实现。
下面通过图示来介绍一下EDF调度算法的工作规则
现在加上，有任务A,B,C共三个任务，其中：

  • A任务运行时间为2s，A任务的截止时间(周期)是8s
  • B任务运行时间为3s，B任务的截止时间(周期)是6s
  • C任务运行时间为1s，C任务的截止时间(周期)是4S

根据上面的信息，实际EDF的执行流程会如下表现

image.png

光看图片可能不好理解，如下解释一下就清楚了：

  1. 根据EDF调度的定义，从0时刻开始调度，那么C的优先级最高，因为C的截止时间最短
  2. 到第1s的时候，C任务完成执行，但是还没有到周期，此时B任务截止时间是5，A任务截止时间是7，此时B优先级高
  3. 到第4s的时候，B任务完成调度，此时C任务也到达周期，C任务的截止时间是4，A任务的截止时间是4，但是A先如的队列，默认执行A
  4. 到第6s的时候，A任务完成执行，此时B任务到达周期，B任务截止时间是6，C任务优先级最高，默认执行C
  5. 到第7s的时候，C任务完成，开始执行B任务
  6. 到第10s的时候，B任务完成，并且没到截止时间，此时A任务的截止时间是8s，C任务优先执行
  7. 第11s的时候，A任务得以执行，因为B和C都未到截止时间
  8. 以此类推。

根据上面的详细解释，我们知道了edf调度算法的执行逻辑，下面查看实现

预设周期

根据上面分析的，如果我们需要使用edf调度算法将任务运行，那么任务必须要有一个周期值设置，在rtems中，设置周期的方式如下

status = rtems_rate_monotonic_create( argument, &rmid );
status = rtems_rate_monotonic_period( rmid, Periods[ argument ] );
status = rtems_rate_monotonic_delete( rmid );

上面的意思非常容易理解，就是为edf调度器设置一个周期，其实现通过timer。
那其实际对timer的操作如下

_Watchdog_Initialize( &the_period->Timer, _Rate_monotonic_Timeout );
deadline = _Watchdog_Per_CPU_insert_ticks(
    &the_period->Timer,
    cpu_self,
    next_length
);

值得注意的是，这里会提前设置周期的长度为 Periods的值，如下

the_period->next_length = length;

所以当timeout的时候，会再次重启timer。

_Rate_monotonic_Restart( the_period, owner, &lock_context );

或

_Rate_monotonic_Renew_deadline( the_period, &lock_context );

根据截止时间设置优先级

根据上面的介绍，我们知道了edf调度算法会通过截止时间来动态调整优先级，也知道了默认情况下我们会预先设置一个周期值，这个周期值就是rtems_rate_monotonic_period的第二个参数，接下来，我们需要明确edf算法如何根据截止时间来动态调整优先级
首先，我们关注_Rate_monotonic_Release_job函数，其实现如下

static void _Rate_monotonic_Release_job(
  Rate_monotonic_Control *the_period,
  Thread_Control         *owner,
  rtems_interval          next_length,
  ISR_lock_Context       *lock_context
)
{
  Per_CPU_Control      *cpu_self;
  Thread_queue_Context  queue_context;
  uint64_t              deadline;

  cpu_self = _Thread_Dispatch_disable_critical( lock_context );

  deadline = _Watchdog_Per_CPU_insert_ticks(
    &the_period->Timer,
    cpu_self,
    next_length
  );
  _Scheduler_Release_job(
    owner,
    &the_period->Priority,
    deadline,
    &queue_context
  );

  _Rate_monotonic_Release( the_period, lock_context );
  _Thread_Priority_update( &queue_context );
  _Thread_Dispatch_enable( cpu_self );
}

上述函数的步骤如下

  1. 为周期值开启一个定时器watchdog,返回定时器的时间period
  2. 根据定时器时间来确定deadline
  3. 根据deadline来调整scheduler edf的优先级Priority
  4. 在edf调度器中更新优先级的值
  5. 打开线程dispatch

我将关键点函数提取出来如下

rtems_rate_monotonic_period( rmid, Periods[ argument ] );
_Watchdog_Insert(header, the_watchdog, expire);
deadline = _Watchdog_Per_CPU_insert_ticks(*)
_Priority_Node_set_priority(*)
_Thread_Priority_update( &queue_context );
_Thread_Dispatch_enable( cpu_self );

根据上面的代码流程，我们知道了，在edf调度算法中，一个周期Period内，优先级是根据watchdog的expire来动态调整，expire的值会换算成调度器的priority值，edf调度算法根据此值来动态调整任务的优先级

红黑树管理优先级

对于调度器的优先级管理，edf中使用的是红黑树，其主要函数如下

    _Scheduler_EDF_Schedule,         /* schedule entry point */ \
    _Scheduler_EDF_Yield,            /* yield entry point */ \
    _Scheduler_EDF_Block,            /* block entry point */ \
    _Scheduler_EDF_Unblock,          /* unblock entry point */ \
    _Scheduler_EDF_Update_priority,  /* update priority entry point */ \

下面我们逐个介绍调度器管理优先级的方式

执行调度

_Scheduler_EDF_Schedule的作用是将当前任务调度一次，此时需要获得优先级最高的任务，对于edf而言，默认expire值最小说明优先级越高，所以在红黑树中是获得最小的节点，在红黑树获得最小节点的方式是遍历根节点，找其左孩子
那么执行调度过程中，获得最高优先级任务的方式如下

RBTree_Node *_RBTree_Minimum( const RBTree_Control *tree )
{
  RBTree_Node *parent;
  RBTree_Node *node;

  parent = NULL;
  node = _RBTree_Root( tree );

  while ( node != NULL ) {
    parent = node;
    node = _RBTree_Left( node );
  }

  return parent;
}

当找到优先级最高的任务之后，直接设置其标志位为true即可

_Scheduler_uniprocessor_Schedule
_Thread_Dispatch_necessary = true;

让出任务

对于让出任务而言，我们需要做的是

  1. 将任务从红黑树中删除
  2. 根据新的优先级，将任务插入到红黑树中
  3. 执行调度

关于1，其实就是红黑树的删除操作，其代码如下

RTEMS_RB_REMOVE( RBTree_Control, the_rbtree, the_node );

关于红黑树的删除，可以查看文章<rb-tree实现-删除操作-原理>

关于2，其实就是红黑树的插入操作，其代码如下

static inline bool _RBTree_Insert_inline(
  RBTree_Control *the_rbtree,
  RBTree_Node    *the_node,
  const void     *key,
  bool         ( *less )( const void *, const RBTree_Node * )
)
{
  RBTree_Node **link;
  RBTree_Node  *parent;
  bool          is_new_minimum;

  link = _RBTree_Root_reference( the_rbtree );
  parent = NULL;
  is_new_minimum = true;

  while ( *link != NULL ) {
    parent = *link;

    if ( ( *less )( key, parent ) ) {
      link = _RBTree_Left_reference( parent );
    } else {
      link = _RBTree_Right_reference( parent );
      is_new_minimum = false;
    }
  }

  _RBTree_Add_child( the_node, parent, link );
  _RBTree_Insert_color( the_rbtree, the_node );
  return is_new_minimum;
}

根据上面的代码，我们可以知道，在插入之前，我们需要遍历根节点，找到小于等于某个节点的位置，然后如果待插入节点插入到其节点的左边。然后执行红黑树的插入操作_RBTree_Insert_color
关于红黑树的插入，可以查看文章<rb-tree实现-插入操作-原理>

阻塞任务

对于阻塞当前任务，我们需要做的是

  1. 将任务从红黑树中删除
  2. 执行调度

代码如下

static inline void _Scheduler_uniprocessor_Block(
  const Scheduler_Control *scheduler,
  Thread_Control          *the_thread,
  Scheduler_Node          *node,
  void                  ( *extract )(
                             const Scheduler_Control *,
                             Thread_Control *,
                             Scheduler_Node *
                        ),
  Thread_Control       *( *get_highest_ready )( const Scheduler_Control * )
)
{
  ( *extract )( scheduler, the_thread, node );

  /* TODO: flash critical section? */

  if ( _Thread_Is_heir( the_thread ) ) {
    Thread_Control *highest_ready;

    highest_ready = ( *get_highest_ready )( scheduler );
    _Scheduler_uniprocessor_Update_heir( _Thread_Heir, highest_ready );
  }
}

恢复任务

对于当前任务恢复调度，就是将其加入就绪队列中，也就是红黑树的插入操作，其代码如下

void _Scheduler_EDF_Unblock(
  const Scheduler_Control *scheduler,
  Thread_Control          *the_thread,
  Scheduler_Node          *node
)
{
  Scheduler_EDF_Context *context;
  Scheduler_EDF_Node    *the_node;
  Priority_Control       priority;
  Priority_Control       insert_priority;

  context = _Scheduler_EDF_Get_context( scheduler );
  the_node = _Scheduler_EDF_Node_downcast( node );
  priority = _Scheduler_Node_get_priority( &the_node->Base );
  priority = SCHEDULER_PRIORITY_PURIFY( priority );
  insert_priority = SCHEDULER_PRIORITY_APPEND( priority );

  the_node->priority = priority;
  _Scheduler_EDF_Enqueue( context, the_node, insert_priority );
  _Scheduler_uniprocessor_Unblock( scheduler, the_thread, priority );
}

这里就绪队列的入队_Scheduler_EDF_Enqueue就是红黑树的插入操作

总结

至此，我们讲解了edf调度的原理，接下来通过实验来演示edf调度

阅读全文
rb-tree实现-删除操作-演示
编辑
2025-04-12
记录知识
0

本文根据<rb-tree实现-删除操作-原理>文章的原理描述，逐一演示删除操作

必要条件

  • 默认情况下，图示只按照前驱方式来寻找删除节点。
  • 默认情况下，图示先进行左旋/右旋然后再进行染色/颜色互换

删除红色根节点

红色根节点不影响平衡，无需调整，故直接删除，如下图

image.png

删除黑色根节点

假设当前红黑树如下，我们准备删除节点1

image.png

此时节点1有两个空黑节点，则直接进行第二阶段修复

在修复时，其情况为，兄弟节点6是黑色，且节点6包含两个空黑节点，如下图所示

image.png

于是步骤为如下：

  1. 将兄弟节点6染红
  2. 将父节点4染黑
  3. 将关注节点设置为节点4
  4. 向上递归

如下图示

image.png

此时对于节点4，其兄弟节点13是黑色，兄弟节点包含两个黑节点9和16，则步骤如下：

  1. 将兄弟节点13染红
  2. 将父节点8染黑
  3. 将关注节点设置为节点8
  4. 由于节点8是根节点，则调整完成

如下图示

image.png

删除只有一个节点的节点

假设当前红黑树如下，我们准备删除节点4

image.png

那么步骤如下

  1. 节点6替换节点4
  2. 将节点6染色为黑色

比较简单，就不截图了。

删除节点的前驱节点是删除节点的左孩子

要让删除节点的左孩子是删除节点的前驱节点，那么待删除节点的左孩子没有右孩子。 假设当前红黑树如下，我们准备删除节点8，因为节点8的左孩子节点4没有右孩子，所以节点4就是前驱节点

image.png

那么步骤如下：

  1. 将节点4替换到节点8上
  2. 将节点4的颜色设置为黑色
  3. 将节点4的左节点3设置为黑色

如下图

image.png

删除节点的前驱节点不是删除节点的左孩子

如果前驱节点不是删除节点的左孩子，那么前驱节点和被删除节点没有强相关性，我们在替换删除节点后，需要进行第二步根据实际情况修复步骤
假设当前红黑树如下

image.png

此时我们删除节点30，按照前驱方式，默认节点28作为替代节点，如下

image.png

此时替代节点是节点26的右孩子，其兄弟节点22是黑色，且其兄弟节点22有两个黑色节点，我们需要：

  1. 节点22强制染红色
  2. 然后将关注节点调整为父节点，也就是节点26

如下图

image.png

此时关注节点是26，其兄弟节点35是黑色，左侄子节点33是黑色，右侄子节点42是红色。我们需要：

  1. 左旋父节点，也就是节点28
  2. 左旋后，将祖父节点35设置为节点28的颜色，也就是红色
  3. 将父节点28设置为黑色
  4. 将叔叔节点42设置为黑色
  5. 调整完成

如下图

image.png

修复阶段：关注节点的兄弟节点是红色

为了复现此场景的例子，我们需要构造红黑树如下

image.png

此时我们删除节点28，此时节点27作为前驱节点替换到节点28位置上，而节点27作为关注节点，其兄弟节点21是红色。状态如下

image.png

此时步骤如下

  1. 将父节点26左旋
  2. 左旋完成后，将父节点26和祖父节点21颜色互换
  3. 继续检查关注节点

此时状态如下

image.png

此时关注节点的兄弟节点24是黑色，其左右孩子都是红色，符合场景：修复阶段：关注节点的兄弟节点是黑色，其左右侄子都是红色

此时关注节点作为节点26的右孩子，所以步骤如下

  1. 先右旋父节点26
  2. 将祖父节点24设置为父节点26的颜色(红色)
  3. 将父节点26设置为黑色
  4. 将叔叔节点23设置为黑色
  5. 调整结束

此时调整完成后的状态如下

image.png

修复阶段：关注节点作为右孩子时，其兄弟节点是黑色，右侄子是红色，左侄子是黑色

为了准备这种情况，我们需要构造红黑树情况如下，我们关注节点35，如下

image.png

此时我们删除节点35，那么节点33会替代节点35，然后关注节点在原节点33的位置，记住节点33是父节点32的右孩子，那么状态如下

image.png

此时关注节点的兄弟节点30是黑色，右侄子是红色，左侄子是黑色 我们需要目的将红色节点搬到左侄子节点上，那么步骤如下

  1. 兄弟节点30左旋
  2. 节点30和原右侄子节点颜色互换

那么此时状态如下

image.png

此时关注节点不变，其兄弟节点31是黑色，其左侄子节点是红色，右侄子节点是黑色，那么步骤如下

  1. 右旋父节点32
  2. 将祖父节点31的颜色设置为父节点32的颜色(红色)
  3. 将父节点32染黑
  4. 将叔叔节点30染黑
  5. 调整结束

上述步骤完成之后，状态如下

image.png

总结

至此，针对删除的所有场景演示完成了，本文没有按照关注节点的左右孩子都重复介绍，只是按照单边作为示例，演示了所有的场景。那么本文涉及到的场景如下：

可以对应文章<rb-tree实现-删除操作-原理>查看场景

删除阶段：

  1. 删除节点没有子节点
    章节: <删除红色根节点>
  2. 删除节点只有一个子节点
    章节: <删除只有一个节点的节点>
  3. 删除节点有两个子节点，前驱节点是其左孩子
    章节: <删除节点的前驱节点是删除节点的左孩子>
  4. 删除节点有两个子节点，前驱节点不是其左孩子
    章节: <删除节点的前驱节点不是删除节点的左孩子>

修复阶段：

  1. 兄弟节点是红色
    章节: <修复阶段：关注节点的兄弟节点是红色>
  2. 兄弟节点是黑色，且侄子都是黑色
    章节: <删除黑色根节点>
  3. 兄弟节点是黑色，其左侄子是红色，右侄子是黑色
    章节: <修复阶段：关注节点作为右孩子时，其兄弟节点是黑色，右侄子是红色，左侄子是黑色>（镜像）
  4. 兄弟节点是黑色，其左侄子是黑色，右侄子是红色
    章节: <删除节点的前驱节点不是删除节点的左孩子>
  5. 兄弟节点是黑色，其左右侄子都是红色
    章节: <修复阶段：关注节点的兄弟节点是红色>

至此，可以发现，全部演示完成。

阅读全文
rb-tree实现-删除操作-原理
编辑
2025-04-11
记录知识
0

之前介绍了插入操作，简单总结就是如果平衡出现问题，先向上递归染色成父红叔黑状态，然后根据LL/RR/LR/RL进行右旋(针对g节点)/左旋(针对g节点)/左旋(针对p节点)+右旋(针对g节点)/右旋(针对p节点)+左旋(针对g节点)，最后互换颜色。
可以发现对于插入操作，我们可以一句话描述清楚所有场景，而对于删除操作，就比较复杂了。本文介绍删除操作的原理

删除操作

对于红黑树的删除操作，其全部操作分为两个阶段。

  • 删除阶段：找到前驱/后继节点替换待删除节点
  • 修复阶段：修复，平衡破坏，修复平衡

这两步操作宏观看还是非常好理解的，现在逐一介绍

删除阶段

对于删除阶段，主要有三种场景，我们先准备一下必要条件

  1. 如果被删除节点没有子节点，那么其就相当于有两个空黑节点 (一种情况)
  2. 如果被删除节点只有一个节点，那么被删除节点一定是黑色，被删除节点的子节点一定是红色 (两种情况)

因为被删除节点只有一个节点，而黑高必须平衡，所以子节点肯定得红色，又因为子节点必须是红色，所以被删除节点一定是黑色

  1. 如果被删除节点有两个节点，理论上按照有2的3次方共计8种组合方式，但是根据红黑树的规定，不能连续的红色，则只有按照前序遍历的 黑红红/红黑黑/黑红黑/黑黑红 (四种情况) 好了，根据上面的必要条件，一共七种情况，我们可以直接开始逐个根据所有场景分析了。
    本文将相关节点如下称呼
  • 待删除节点(s)
  • 待替换节点(r)
  • 父节点(p)
  • 兄弟节点(b)
  • 侄子节点(n)：兄弟节点的左/右孩子

没有子节点

这种情况下，就相当于有两个空节点，没有人替换它，我们不需要进行第一阶段删除，直接跳转到第二阶段修复去调整平衡

只有一个子节点

这里两种情况，子节点无论是左边还是右边，处理方式都是

  • 删除节点s，把其孩子节点作为节点r替换为节点s
  • 将节点s从红色染色成黑色

因为只有一个子节点的时候，由红色节点替代了被删除的黑色节点，此时修复黑高的方法就是将替代节点r的红色染成黑色即可。
故仅需两步，调整结束

有两个子节点

这种情况对应了其他四种场景，此时我们需要找到前驱节点或后继节点。也就是找到小于此节点的值或者大于此节点的值。所以关键点在于如何找到前驱节点和后继节点作为替代节点r。
而找前驱节点和后继节点的情况分别又是两种。

所以在 黑红红/红黑黑/黑红黑/黑黑红 四种场景下，我们根据红黑树的找前驱还是后继的方式可以两种实现(前驱/后继)来找节点r，在不同的实现下如何找前驱和后继还有两种方式，下面逐一介绍。

前驱方式

先介绍前驱方式寻找小于节点s的节点r

节点s的左子树没有右孩子

如果节点s的左子树没有右孩子，那么节点s的左孩子就是替代节点r，因为此时的节点r就是节点s的前驱节点。那么步骤如下：

  1. 我们将节点r(前驱节点)替换到节点s上
  2. 将节点r的颜色设置为节点s的颜色
  3. 然后将节点r的左孩子强制设置为黑色

我们需要注意的是，节点r的左孩子只能是红色。原因如下：

如果节点r的左孩子是黑色，那么又因为节点r是单节点，黑高肯定不平衡，图示如下。

首先我们假设一个红黑树如下：

image.png

此时我们删除节点3，让其处于如下状态

image.png

此时节点2相当于节点r，节点1相当于节点r的左孩子
我们算上叶子节点来计算黑高，可以发现，4-2 这里黑高是3，而其他的黑高是4。所以黑高一定不平衡。

那么我们可以得出结论，此情况下，节点r的左孩子一定是红色

根据上面的结论而言，我们的步骤相当于删除前驱节点r的颜色，然后再将节点r的左孩子强制设置为黑色。因为节点r的左孩子一定是红色，我们将节点r的左孩子强制染黑，黑高自然就是平衡了。

再补充一点，我们知道节点r的左孩子一定是红色，根据红色不能连续的规则，那么节点r一定就是黑色，在这种情况下，删除节点r的颜色就是删除了一个黑色，而为了维持黑高，将节点r的孩子染色成黑色，自然就平衡了。

节点s的左子树有右孩子

因为节点s的左子树有右孩子，我们就需要遍历其所有的右孩子，找到节点s的前驱节点。
值得注意的是，此时节点s的前驱节点r和节点s就没有相关性了。如我们步骤如下

  1. 遍历其所有的右孩子，找到节点s的前驱节点

  2. 我们将节点r(前驱节点)替换到节点s上

  3. 将节点r的颜色设置为节点s的颜色

  4. 然后将节点r的左孩子强制设置为黑色

上面三个步骤和节点s的左子树无右孩子的场景一致，但是我们在第三步将节点r的左孩子强制染黑了，而此时节点r和节点s没有相关性。所以黑高平衡破坏了之后，没办法直接修复，需要进行修复第二步骤。也就是如下

补充一下为什么没办法直接修复，因为节点s和节点r相差距离可能很远，我们是删掉了节点r，将节点r的内容放在节点s，实际上是因为节点r的丢失，导致从节点s的左边全部失去平衡。所以才有了第二步骤：修复

  1. 将关注节点变成节点r的左孩子，进行第二步骤修复

后继方式

后继方式和前驱方式逻辑一致，操作方式是镜像的

节点s的右子树没有左孩子

步骤如下：

  1. 我们将节点r(后继节点)替换到节点s上
  2. 将节点r的颜色设置为节点s的颜色
  3. 然后将节点r的右孩子强制设置为黑色

节点s的右子树有左孩子

我们需要遍历其所有的左孩子，找到节点s的前驱节点。
指的注意的是，此时节点s的前驱节点r和节点s就没有相关性了。如我们步骤如下

  1. 遍历其所有的左孩子，找到节点s的后继节点

  2. 我们将节点r(后继节点)替换到节点s上

  3. 将节点r的颜色设置为节点s的颜色

  4. 然后将节点r的右孩子强制设置为黑色

  5. 将关注节点变成节点r的右孩子，进行第二步骤修复

总结

至此，我们针对最后四种场景下，根据找前驱和后继的方式，将原节点进行了删除操作，如果前驱/后继节点和节点s没有相关性，则我们需要开展第二阶段修复操作，否则我们强制染色就能维持平衡。接下来开始介绍红黑树删除的第二阶段：修复操作

修复阶段

在删除阶段，实际上我们目的是先将目标节点s删除，然后通过找前驱/后继的方式找到替代节点r，将其替换目标节点s。(其本质是删除了节点r)
而在修复阶段，实际上我们就需要将无法修复的黑高来进行进一步修复。

在这里，我们将兄弟节点称之为节点b，将侄子节点称之为节点n(ln/rn)，将关注节点称之为节点s，记得关注节点注意和第一阶段区分。

在修复阶段，一共五种情况， 如下：

  1. 兄弟节点b是红色
  2. 兄弟节点b是黑色，且节点b的左右孩子(节点ln和rn)都是黑色(包含空节点)
  3. 兄弟节点b是黑色，且节点b的左孩子(节点ln)是红色，右孩子(节点rn)是黑色
  4. 兄弟节点b是黑色，且节点b的左孩子(节点ln)是黑色，右孩子(节点rn)是红色

这里还有一种情况：

  1. 兄弟节点b是黑色，且节点b的左右孩子(节点ln和rn)都是红色 这种情况和情况4合并

在上面五种情况下，我们还需要考虑关注节点s自身作为左孩子还是右孩子，这两种情况下，操作是镜像的。 为了方便介绍，我们先假设节点s自身作为父节点的左孩子。然后再介绍节点s自身作为父节点的右孩子的情况。

节点s是左孩子

假设节点s自身作为父节点的左孩子

兄弟节点b是红色

我们还是和插入的思想一致，如果兄弟节点b是红色的，我们要想办法让其变成黑色。

根据插入的时候的逻辑，假设是LL状态，那么我们对祖父节点右旋。这样自身插入节点向上一级。
同样的，如果是删除的时候，如果兄弟节点b是红色的，在L状态，为了让关注节点s向下降级，我们选择左旋。对谁左旋呢，当然是对父节点的左旋才能让关注节点s下降一级。

当左旋完成之后，节点s自降一级，我们知道节点b是红色的，那么节点b的任何子节点都一定是黑色的。那么左旋完成之后，兄弟节点肯定是黑色的。

这样我们就可以只讨论兄弟节点是黑色的情况了。

关于互换颜色，我们知道在插入操作后，会将兄弟节点b和父节点p颜色互换，同样删除也是。

对于左旋之后，我们需要的是将关注节点s的父节点p和祖父节点g的颜色互换

如果细心的可以了解到，对于颜色互换操作，其和插入操作是镜像的。 我列出如下

  • 对于插入操作，LL状态下，右旋后将兄弟节点和父节点的颜色互换
  • 对于删除操作，LL状态(左旋之后是LL状态)，左旋后将父节点和祖父节点颜色互换

也就是说，如果兄弟节点b是红色，那么再左旋完成之后，需要做一下颜色互换即可。互换的角色是

旋转后的 父节点和祖父节点。

总结一下，那么其步骤如下：

  1. 将父节点p左旋
  2. 将父节点p和祖父节点g交换颜色
  3. 继续检查关注节点(因为左旋会让关注节点降级，所以可以继续关注节点)

至此，我们分析了情况1，它的目的是将兄弟节点染黑，染黑的操作是通过左旋完成(因为兄弟节点的子节点一定是黑色)，自身下降一级。

兄弟节点b是黑色，节点b的子节点都是黑色(包含空节点)

我们知道进入修复阶段的时候，红黑树已经不平衡了，那么如果兄弟节点b是黑色，且其子节点都是黑色，那么我们计算其兄弟的黑高一定是2，而关注节点和子节点的黑高是1或2(自身是红则是1,自身是黑则是2)。所以
我们可以发现，在这个状态，就是黑高不平衡的状态。

我们找到了不平衡的关键点。我们的操作是强制让其染红，也就是

强制给兄弟节点染红

当兄弟节点染红之后，我们得到的结果是兄弟的黑高固定为1，往上递归，找到所有兄弟节点b是黑色且所有侄子节点(ln/rn)是黑色节点的情况，把兄弟节点染红，让其黑高固定为1.(兄弟节点红色,两个侄子节点都是黑色)

此时，我们将兄弟节点强制染红了，那么对父节点p，就需要强制染黑，否则出现了连续的红色节点

总结一下，那么本情况下，其步骤如下：

  1. 将兄弟节点b染色成红色
  2. 将父节点p染色成黑色
  3. 设置关注节点是父节点
  4. 向上递归

兄弟节点b是黑色，左侄子是红色，右侄子是黑色

我们现在剩下三种情况，如下

  1. 节点b是黑色，节点ln是红色，节点rn是黑色
  2. 节点b是黑色，节点ln是黑色，节点rn是红色
  3. 节点b是黑色，节点ln和rn都是红色

为了能够归一化这个问题，我们聚焦在一个点上：

  • 右侄子节点(rn是红色)

为了让节点rn是红色，我们需要对 本情况1:节点b是黑色，节点ln是红色，节点rn是黑色 进行调整，调整步骤如下：

  1. 兄弟节点b右旋
  2. 交换兄弟节点b和节点ln的颜色

这样之后，我们发现，上述剩下的三种情况就变成两种情况了，我们继续情况4和5

兄弟节点b是黑色，左侄子是黑色，右侄子是红色

对于此情况，考虑到我们是删除操作，我们找到替代节点是前驱节点，前驱节点是找到左孩子的最右节点，实际上对于关注节点s，其黑高是少于右边的(因为删除过节点)，为了修复黑高，此时应该做的是左旋

因为左旋会将左侄子节点rn给关注节点作为关注节点的右节点

故步骤如下

  1. 先左旋父节点p
  2. 将祖父节点g的颜色设置为父节点p的颜色
  3. 将父节点p的颜色设置为黑色
  4. 将叔叔节点u的颜色设置为黑色

此时调整结束

兄弟节点b是黑色，左右侄子都是红色

其实根据插入的定义，我们插入时必须要保证父红叔黑，所以插入节点后，不会出现非底层节点出现两个红色

那么出现左右侄子都是红色的情况是 左右侄子节点ln/rn都只含有空节点

此时，我们的行为可以和情况4合并，因为最后将 左侄子节点rn给关注节点作为关注节点的右节点 的时候，这个右节点是红色的，它本身就维持平衡了，调整结束。

节点s是右孩子

这种情况和节点s是左孩子的情况是镜像的，主要如下

兄弟节点b是红色

那么此时的步骤如下：

  1. 将父节点p右旋
  2. 将父节点p和祖父节点g交换颜色
  3. 继续检查关注节点(因为左旋会让关注节点降级，所以继续关注节点来修复)

兄弟节点b是黑色，节点b的子节点都是黑色(包含空节点)

那么此时的步骤如下

  1. 将兄弟节点b染色成红色
  2. 将父节点p染色成黑色
  3. 设置关注节点是父节点
  4. 向上递归

兄弟节点b是黑色，左侄子是黑色，右侄子是红色

那么此时的步骤如下

  1. 兄弟节点b左旋
  2. 交换兄弟节点b和节点ln的颜色

兄弟节点b是黑色，左侄子是红色，右侄子是黑色

那么此时的步骤如下

  1. 先右旋父节点p
  2. 将祖父节点g的颜色设置为父节点p的颜色
  3. 将父节点p的颜色设置为黑色
  4. 将叔叔节点u的颜色设置为黑色

兄弟节点b是黑色，左右侄子都是红色

此情况和 兄弟节点b是黑色，左侄子是红色，右侄子是黑色 情况一致，步骤也是一致

总结

红黑树的删除操作比较复杂，捋清楚需要认真思考很久，作为总结，删除操作简单来说如下，以节点s为左孩子为例：

  1. 先进行删除操作
  2. 删除操作中要找到替换节点，替换节点可能是左右子树，也可能是前驱节点，不同的红黑树实现，也可能使用后继节点实现
  3. 当平衡产生破坏的情况下，需要进行修复操作
  4. 修复操作的场景有五种，需要归一化处理
  5. 先让兄弟节点变黑，向下继续
  6. 如果兄弟节点和其子节点的黑高是2(都是黑的)，强行染色兄弟节点，让其黑高暂时是1
  7. 根据5和6的操作，兄弟节点肯定是黑色，黑高不会一定是2
  8. 此时想办法固定右侄子节点为红色
  9. 如果右侄子为黑色，则对兄弟节点右旋，并交换颜色，此时右侄子一定为红色(因为原左侄子的红色给了右侄子)
  10. 此时所有情况都归一化到：兄弟节点是黑，右侄子是红的情况
  11. 将父节点左旋，完成后，强行将祖父节点设置为父节点颜色，并强行将父节点和叔叔节点染黑
  12. 调整结束

在节点为右孩子时，我们左旋右旋的操作镜像即可。

本文将删除的原理彻底弄清楚了，为了方便理解，下一篇文章将所有的场景示例出来，加深印象。

阅读全文