[자료구조][Linux] Red Black Tree

자료구조 시간에 배운 binary search tree를 알아야 이해할 수 있는 개념이다!!

 

(자신의 왼쪽 트리에는 현재보다 작은거, 오른쪽 tree에는 현재 값보다 큰 값이 왔던 tree이다. )

(inorder traverse를 하면 오름차순으로 정렬된 값을 얻을 수 있다)

 

red black tree는 binary search tree중 balance가 맞는 tree이다. (self-balanced라고 한다)

 

red black tree의 조건

1. root node는 black

2. 모든 external node는 black

3. red의 자식은 black

4. 모든 leaf node에서 root node까지 가는데 만나는 black의 개수는 같다. 

 

처음 root는 black으로 만들고, 자식으로는 red만 붙여나간다.

double red가 온 상황이 생긴다면 다음과 같은 두가지 전략을 쓸 수 있다.

 

1) restructuring : uncle node가 black일 때

2) recoloring : uncle node가 red일 때

 

restructuring 과정

1. 나, 내 부모, 내 부모의 부모를 오름차순으로 정렬

2. 가운데 값을 부모로, 나머지 둘을 자식으로

3. 부모는 검은색, 자식은 빨간색으로

 

restructuring은 무조건 한번에 끝난다. 

 

recoloring 과정

1. 현재 insert된 노드의 부모와 uncle을 Black으로 하고 Grand Parent(내 부모의 부모)를 빨강(Red)로 한다.

2. 내 부모의 부모가 Root node가 아니었을 시 Double Red가 다시 발생 할 수 있다.

 

double red가 또 발생한다면, 두 가지 전략중 맞는 상황을 또 반복해서 해결하면 된다. 

red black tree는 binary search tree중에서 가장 성능이 좋다고 한다. 

 

Linux에서의 Red Black Tree

Kernel에서 rbtree는 "Completely Fair Scheduling(CFS)" 를 위해서 사용된다고 한다. 

Linux에서 default scheduler인데, 각 task에는 vruntime이 있고 CFS에서 vruntime이 최소인 프로세스를 고른다. 

 

 

출처: https://zeddios.tistory.com/237 [ZeddiOS]