Red-Black Tree (레드 블랙 트리) 데이터 삽입

데이터 삽입

이진탐색 트리의 한 종류이기 때문에 기본적인 이진 탐색트리 삽입 방법을 따른다.

데이터 삽입 후, 레드 블랙 트리의 속성 5가지를 만족하는지 확인한다.

이를 불만족 한 노드가 발생한다면, 재조정을 한다

 

속성

 

1. 모든 노드는 Red/Black 두 가지중 하나의 색상값을 가진다.

2. Root노드는 반드시 Black 색상이다.

3. 없는 상태(Null, None, Nill)을 나타내는 노드는 Black 색상을 갖는다.

4. Red색상의 노드는 반드시 Black색상의 자식을 가져야 한다.(Black 노드는 Black/Red 어떤색이든 자식으로 가질 수 있다.)

5. 임의 노드에서 모든 Leaf 노드까지의 경로에서 시작 노드를 제외한, Black node의 개수(Black Height)는 동일하다.

 

삽입 방법.

 

1. 항상 삽입되는 노드의 색깔은 레드이다.

-> nil 노드는 블랙이며, 레드의 자식은 항상 블랙이다를 만족하며 아래와 같은 형태로 새로운 데이터를 삽입한다

-> 기존의 레드 블랙 트리에 black height의 영향을 주지않으면서 삽입 가능하다.

* 최초로 삽인되는 루트노드라면 삽입후 레드인 노드를 블랙으로 변경하여 속성을 만족한다. 

 

2. 레드 노드 자식으로 레드 노드가 삽입될때, (왼쪽,왼쪽) (오른쪽,오른쪽) 방향이며, 부모노드의 형제가 없거나 블랙 노드인 경우. 

회전을 하고 노드의 색상을 변경해준다. 

회전을 할때, 기본적인 이진탐색트리의 속성을 반드시 지켜줘야 한다.

Insert 10 (10이 삽입될때 부모인 20의 형제가 nill 이거나 블랙 노드)

3. 레드 노드 자식으로 레드 노드가 삽입될때, (왼쪽,오른쪽) (오른쪽,왼쪽) 방향이며, 부모노드의 형제가 없거나 블랙 노드인 경우.

 

꺽여 있는 경로를 펴주기 위해 20을 중심으로 왼쪽으로 회전한다.

이후, 2번의 방법을 이용하여 불만족을 해결한다. 

 

Insert 40 (40이 삽입될때 부모인 20의 형제가 nill 이거나 블랙 노드)

4.   레드 노드 자식으로 레드 노드가 삽입될때, 부모노드의 형제가 레드 노드인 경우

 

insert 30 (30이 삽입될때 부모인 50의 형제가 10이 레드이다.)

두 자식의 색상이 동일할때, 부모노드와 색상을 변경해도 black height에 영향을 미치지 않는다. 

루트노드인 20이 레드이기 때문에 블랙으로 색상을 변경해준다. 

* 부모노드와 색상을 변경하고 반드시 또 다른 속성을 위반했는지 확인하고 다른 불만족이 나타났다면 1,2,3번의 방법을 사용하여 해결한다.