RED-BLACK TREE

박호준·2021년 11월 5일
0

ft_containers

목록 보기
3/6

RED-BLACK TREE

  • balanced binary search tree

특징

  • 모든 node는 red / black 의 색을 가져야함

  • 삽입되는 새로운 노드는 항상 red

  • Root Property : root node는 black

  • External Property : leaf(NULL) node는 black

  • Internal Property : red node의 child는 모두 black

  • Depth Property : 각 노드에서 leaf 로 가는 경로의 black node의 수가 항상 같아야 함
    [ red node의 hieght <= logN ]


Double Red 해결방법 <삽입>

G(할아버지노드) P(부모노드) U(삼촌노드) M(내 노드)

Restructuring ( U is black)


1. 나(M)와 내 부모(P), 할아버지(G)를 오름차순으로 정렬

2. 무조건 가운데 있는 값을 부모로 만들고 나머지 둘을 자식으로 만든다.

3. 올라간 가운데 있는 값을 검정(Black)으로 만들고 그 두자식들을 빨강(Red)로 만든다.
4. 삼촌(U)의 자식이 있다면 붙여준다.


Recoloring (U is Red)


1. 현재 inset된 노드(M)의 부모(P)와 삼촌(U)를 검정(Black)으로 하고 할아버지노드(G)를 빨강(Red)로 한다.

2. 할아버지(G)가 Root node가 아니었을 시 Double Red가 다시 발생 할 수 있다

profile
hopark

0개의 댓글