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가 다시 발생 할 수 있다
hopark