TIL(17일차) 레드블랙트리 삽입

https://www.youtube.com/watch?v=2MdsebfJOyM&t=30s 

 

Red-black Tree의 대해서 이 자료 저자료 보다가 시각적으로나 영상으로나 쉬운코드님의 설명이 가장 잘 이해되어서 위 영상을 기반으로 공부를 하게 되었다.

 

Red-Black Tree

 

Red-black Tree은 이진 탐색 트리의 한 종류이다.

 

스스로 균형을 잡는 트리이다.

 

균형트리는 AVL 트리를 먼저 접하게 되어 대표적인 자료구조는 AVL이구나 라고 생각했다.

 

BST(binary search tree)의 worst case O(n)이므로 이것을 O(log n)으로 개선한 것이 AVL트리라고만 생각하고 있었다.

 

근데 Red - black Tree는 AVL의 밸런싱 과정이 시간이 오래 걸린다는 단점을 가지고 있다고 하여 그것을 보완시킨 자료구조라고 한다.

 

하지만 AVL은 RB트리에 비해 검색이 빨라서 만들어 놓고 삽입 삭제를 안하는 검색 기능에 대부분 사용한다고 한다.

 

Red-Black Tree의 속성

 

1. 모든 노드는 red 혹은 black 이다.

2. 루트 노드는 black

3. 모든 nil노드는 black

4. red의 자녀들은 black이어야한다.(red가 두번 나올 수 없다)

5. 임의의 노드에서 자손 nil노드들까지 가는 경로들의 black 수는 같다(자기 자신은 카운트에서 제외)

 

 

Nil 노드란 : 존재하지 않는 노드를 의미하며, 자녀가 없을때는 자녀를 nil노드로 표기한다.

값이 있는 노드와 동등하게 취급하고 red-black 트리에서는 leaf노드는 nil노드이다.

 

 

 

삽입시에 두 자식은 nil노드 이고, 삽입시 색상은 항상 red이다.

 

이것은 5번 속성을 만족하게 하기 위한 이유이기도하다.

 

삽입시에는 4개의 위반 케이스가 적용되는데

 

위반의 형태

이는 하나는 위에서 설명한 항상 red 노드로 삽입했을때에 root노드가 무조건 black 이어야 한다는 것과

 

두번째는 삽입된 red노드가 부모의 왼쪽 자녀 이면서 부모도 red이고 조상의 왼쪽 자식노드이면서 조상의 다른 한노드는 black일때 이다.

 

세번째는 두번째와 비슷하지만 삽입된 red노드가 부모의 오른쪽 자녀로 삽입될때 이다.

 

마지막 네번째는 삽입된 red 노드의 부모도 red 이면서 조상의 다른 자식 노드도 red 일때 이다.

 

 

 

해결방법

 

해결방법은 첫번째는 root노드의 색깔을 black으로 바꾸는 것이고

 

두번째는 부모 노드와 조상 노드의 색깔을 바꿔주고 오른쪽으로 회전한다.

 

세번째는 부모노드를 기준으로 왼쪽으로 회전하여 두번째와 같은 형식으로 만들고 두번째와 같이 동작한다.

 

네번째는 조상노드와 부모노드의 색깔을 바꾸고 만약 루트노드가 red가 된다면 첫번째 케이스를 적용해준다.