[WEEK05] 정글5기 - 탐험 준비 - Red-Black Tree

1. 레드 블랙 트리(RB Tree)의 삽입/삭제

레드-블랙 트리 (RB Tree)	- 자가 균형 이진 탐색 트리     · 삽입 삭제 시 최악의 경우에서도 모두 O(log n) 보장 - 이진 탐색 트리 : 자신의 왼쪽 서브 트리에는 현재 노드보다 값이 작은 것, 오른쪽 서브 트리에는 값이 큰 것들을 배치     · 이진 탐색 트리의 조회 : O(log n)     · 최악의 경우(균형이 무너질 경우) : O(n)
레드-블랙 트리 조건	1. 모든 노드는 빨간색 혹은 검은색이다. 2. 루트 노드는 검은색이다. 3. 모든 리프 노드(NIL)들은 검은색이다. 4. 빨간색 노드의 자식은 검은색이다.     · == No Double Red(빨간색 노드가 연속으로 나올 수 없다.) 5. 모든 리프 노드에서 Black Depth는 같다.     · == 리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다.     · == 자손 nil 노드들까지 가는 경로들의 검은색 노드들의 수는 값다.
NIL node (leaf)	- 해당 노드는 key나 data를 포함하지 않으며 실제 코드에서도 구현하지 않는 "완전 가상의 노드" - (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드)
internal nodes	- internal nodes는 NIL이 아닌 나머지 노드
black height (black depth)	- 노드 x의 black height란?     · 노드 x에서 임의의 자손 nil 노드까지 내려가는 경로에서의 black 수 (자기 자신은 카운트에서 제외)
추가 특징	- RB트리가 5번 속성을 만족하고 있고 두 자녀가 같은 색을 가질 때 부모와 두 자녀의 색을 바꿔줘도 5번 속성은 여전히 만족한다.

 

삽입 쉬운 버전

삽입과정	- 레드-블랙 트리에 새로운 노드를 삽입할 때 새로운 노드는 항상 빨간색으로 삽입한다. 1. 부모의 형제노드(삼촌 노드)가 검은색이라면 → Restructuring을 수행 2. 부모의 형제노드(삼촌 노드)가 빨간색이라면 → Recoloring을 수행
왜 새로 삽입하는 노드는 빨간색인가?	- 삽입 후에도 5번 속성을 만족하기 위해서
1. Restructuring (삼촌 노드가 검은색)	1. 새로운 노드(N), 부모 노드(P), 조상 노드(G)를 오름차순으로 정렬한다. 2. 셋 중 중간값을 부모로 만들고 나머지 둘을 자식으로 만든다. 3. 새로 부모가 된 노드를 검은색으로 만들고, 나머지 자식들을 빨간색으로 만든다.
2. Recoloring (삼촌 노드가 빨간색)	1. 새로운 노드(N)의 부모(P)와 삼촌(U)을 검은색으로 바꾸고 조상(G)을 빨간색으로 바꾼다.     · 1-1. 조상(G)이 루트 노드라면 검은색으로 바꾼다.     · 1-2. 조상(G)을 빨간색으로 바꿨을 때 또 다시 Double Red가 발생한다면 또 다시 Restructuring               혹은 Recoloring을 진행해서 Doubled Red 문제가 발생하지 않을 때까지 반복한다. * 검은색 노드는 2번 나와도 괜찮다.
* 삼촌 노드가 없는 경우	- 삼촌 노드가 없는 경우, 조부모가 NIL 노드를 왼쪽 혹은 오른쪽 자식으로 가지고 있는 경우이다. - 이때 NIL 노드 또한 검정 노드이므로 Restructing을 수행하면 된다.

 

삽입 자세히 알아보기! ( 중간 노드에서 4번 조건을 만족하기 위해서는 회전의 개념을 확실히 알아야 한다.)

- 삭제하면서 회전의 개념을 잡을 수 있다.. 삽입은 쉬운 버전으로 이해하고 삭제를 통해 회전을 이해하고 삽입을 다시 해보자!

 

삭제 과정

삭제과정	- RB tree에서 노드를 삭제할 때 어떤 색이 삭제되는지가 속성 위반 여부를 확인할 때 매우 중요 1. 삭제하려는 노드의 자녀가 없거나 하나라면     · 삭제되는 색 = 삭제되는 노드의 색 2. 삭제하려는 노드의 자녀가 둘이라면     · 삭제되는 색 = 삭제되는 노드의 successor(후임자)의 색     · 후임자는 오른쪽 노드의 최솟값.
삭제되는 색 (레드)	- 어떠한 속성도 위반하지 않는다.
삭제되는 색 (블랙)	- 2번, 4번, 5번 속성을 위반할 수 있다. 1. 2번 위반 시     · 루트 노드를 black으로 변경
삭제되는 색이 블랙일 때 5번 속성이 위반되었을 때	- 삭제되는 색이 black이고 삭제된 색의 위치를 대체한 노드에 extra black을 부여한다. - doubly black : extra black이 부여된 black 노드 - red-and-black : extra black이 부여된 red 노드
red-and-black	- red-and-black은 black으로 바꾸면 해결된다.
doubly black	- 4가지 경우가 존재한다. doubly black의 형제의 색과 그 형제의 자녀들의 색으로 분류

 

1. doubly black의 오른쪽 형제가 black    & 그 형제의 오른쪽 자녀가 red 일때	- 그 red를 doubly black 위로 옮기고 - 옮긴 red로 extra black을 전달해서 - red-and-black으로 만들면 red-and-black을 black으로 바꿔서 해결 정리 - 오른쪽 형제는 부모의 색으로, - 오른쪽 형제의 자녀는 black으로 - 부모는 black으로 변경 후 부모를 기준으로 왼쪽으로 회전하면 해결
2. doubly black의 오른쪽 형제가 black    & 그 형제의 왼쪽 자녀가 red    & 그 형제의 오른쪽 자녀는 black 일때	- doubly black의 형제의 오른쪽 자녀를 red가 되게 만들어서 1번과 같이 해결
3. doubly black의 형제가 black    & 그 형제의 두 자녀 모두 black 일 때	- 형제 노드의 black과 자신의 노드의 extra black을 루트로 올린다.     · 부모가 red-and-black이 된다면 black으로 변경     · 부모가 doubly black이 된다면 부모가 extra black을 해결하도록 위임
4. doubly black의 형제가 red일 때	- 부모와 형제의 색을 바꾸고 부모를 기준으로 왼쪽으로 회전한 뒤 doubly black을 기준으로 해결

 

 

---

ADD. AVL 트리

AVL 트리 (Adelson-Velskii and Landis Tree)	- 최초의 스스로 균형을 잡는 데이터 구조 - AVL 트리에서, 두 자식 서브트리의 높이는 항상 최대 1만큼 차이난다. - 아직까지 DB에서 사용중
AVL 트리의 특징	- 트리의 모든 내부 노드(internal node) v에 대해 v의 자식 노드들의 높이 차이가 최대 1이다.     · 어떤 시점에서 높이 차이가 1보다 커지면 회전(rotation)을 통해 균형을 잡아 차이를 줄인다. - RB Tree의 경우 balck height만 만족하면 어느 정도 불균형함도 허락해줬지만 좀 더 깐깐한 트리이다. - 따라서 n개의 노드를 갖는 AVL 트리 높이는 반드시 log n 이다.     · 검색 시간도 O(log n)이다. - 반대로 삽입, 삭제할 때에 조건을을 맞추려면 더 많은 작업이 필요해서 RB Tree보다 효율이 떨어진다.     · 하지만, 삽입, 삭제 시간복잡도는 O(log n)으로 동일하다.
Balance Factor(BF)	- BF(K) = K의 왼쪽 서브트리의 높이 - K의 오른쪽 서브트리의 높이

 

	Red-black tree	AVL tree
장점	- 삽입, 삭제 작업 시 균형을 맞추기 위한 작업 횟수가 적다. - 각 노드 당 색깔을 표현하는 데 단 1bit의 저장공간만 필요하다. - C++의 map, multimap, multiset 등 여러 곳에 쓰인다.	- 조회 시 더 빠른 성능을 자랑한다. - 노드에 색깔이 없다.
단점		- balance factor나 height를 노드에 저장하기 때문에 각 노드당 Integer 값을 하나 저장하고 있어야 한다.

 

	Red-Black 트리	AVL 트리
binary search tree	Yes	Yes
삽입/ 삭제/검색 시간 복잡도	worst case에서도 O(logN)	worst case에서도 O(logN)
삽입/삭제 성능	AVL 트리에 비해 빠르다	RB 트리에 비해 느리다
검색 성능	AVL 트리에 비해 느리다	RB 트리에 비해 빠르다
균형 잡는 방식	rb 트리 속성을 만족시키도록	balance factor ∈ {-1, 0, 1} 되도록 (좌우 서브트리의 높이 차이가 1보다 더 커지면 구조 조정)
응용 사례	linux kernel 내부에서 사용 Java TreeMap 구현 c++ std::map 구현, etc	dictionary, 한번 만들어 놓으면 삽입/삭제가 거의 없고 검색이 대부분인 상황에서 사용