1206 Red Black Tree

1. 레드 블랙 트리란?
균형 트리 중 하나

특징	모든 노드는 빨간색 혹은 검은색
	루트 노드는 검은색
	모든 노드는 우선 NIL 노드를 자식으로 가지고 있다.
	빨간색 노드의 자식은 검은색 (연속된 빨간색 노드가 올 수 없다.)
	모든 NIL노드에서 루트까지의 검은색 노드의 수는 같다.
	새로운 노드 추가할 때 새로운 노드는 우선 빨간색
NIL 노드	데이터를 저장하지 않은 노드
	모든 NIL 노드들은 검은색

구현( 삽입)
맨 처음 노드 삽입	ㅡ>	새로운 노드 생성 후 검은색으로 변경
두번째부터 빨-빨이 오면 변형
	삼촌 노드가 검정색 Restructuring	새로운 노드, 부모 노드, 조무보 노드를 오름차순으로 정렬
		셋 중 중간 값을 부모로 만들고 나머지를 자식으로 만든다.
		새로 부모가 된 노드를 검은색으로 만들고  나머지 자식은 빨간색으로 변경
	삼촌 노드가 빨간색 Recoloring	새로운 노드의 부모 노드와 삼촌의 색상을 검정으로 바꾸고 조부모를 빨강 변경
		조부모가 루트면 검은색으로 변경
		조부모가 빨간색으로 바꼈을 때  또 빨강이 이중으로 있으면 반복