Red-Black Tree

BST의 worst case 의 단점을 개선하는 것
이진 탐색트리 (Binary Search Tree) : 자신 보다 큰 값은 오른쪽, 작은 값은 왼쪽에 있는 트리

시간복잡도가 $O(N)$로 오래걸리는데 → $O(logN)$이 되게 스스로 균형을 잡는 트리

Properties

→ 모든 노드는 red/ black

→ 자녀가 없으면 자녀를 nil 노드로 표기 nil : 존재하지 않음 ( leaf 노드 : 자식이 없는 노드 )

→ 모든 nil 노드는 black 이다

→ red의 자녀들은 반드시 black, = red가 연속적으로 존재할 수 없다

→임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 수가 같다

↑ 속성을 만족해야 성립하는 개념
black height : 노드 x에서 임의의 자손 nil 노드까지 내려가는 경로에서의 black 수

부모와 자식의 색을 바꿔준 뒤에도 속성은 여전히 만족한다

삽입

🏃‍♀️ 삽입하는 노드의 색은 red

삽입 후에도 5번 속성을 만족하기 위해서 red로 시작한다

+2번 속성을 만족하지 않는다면 black으로 바꾼다

+4번 속성을 만족하지 않는다면 BST 특징을 유지하면서 회전을 해야한다

_case 1.
삽입된 red 노드의 부모도 red, 삼촌도 red면, 부모와 삼촌을 black으로 바꾸고 조상은 red로 바꾸고, 조상 노드에서 다시 확인을 시작한다

case 2,3 ( 자식, 부모가 red이고 조상, 삼촌이 black일 경우)

_case 2.
왼쪽으로 한 줄로 만든 다음, 부모와 조상의 색을 바꾸고 오른쪽으로 회전해준다

_case 3.
왼쪽으로 뻗어있는 상태에서 , 부모와 조상의 색을 바꾸고 오른쪽으로 회전해준다.

삭제

BST 에서 노드를 삭제하는 것과 같다

삭제하려는 노드의 자식이 둘이라면,

삭제되는 색 : 삭제되는 노드의 successor의 색

삭제하려는 노드의 자식이 하나나 없다면,

삭제되는 색 : 삭제되는 노드의 색

1, 삭제되는 색이 red라면 어떠한 속성도 위반하지 않는다.

2, 삭제되는 색이 black이라면 2,4,5 속성을 위반할 수 있다.


삭제된 색의 위치를 대체한 노드에 extra black 의 역할
5번 속성을 위반하지 않기 위해 하나의 black으로 카운트


doubly black : black 노드에 extra black가 부여된 상태

red-and-black : red 노드에 extra black이 부여된 상태

red-and-black일 경우에는 노드 색을 black으로 바꿔주는 걸로 해결


_case 4.
doubly black 의 형제가 black, 그 형제의 오른 자녀가 red일 경우, 오른쪽 자녀의 색을 바꾸고 doubly black의 부모를 기준으로 left rotation, 더블리가 루트가 되면 loop 종료

_case 3.
doubly black 의 오른쪽 형제가 black, 그 형제가 왼쪽 자녀가 red일때 오른쪽이 블랙일때 → doubly black 의 형제의 오른쪽 자녀가 red가 되게 만들어야함

왼쪽 자식과 바꾸고 오른쪽으로 회전하고 case 4의 해결방식을 적용-

_case 2.
doubly black 형제가 black, 자식도 모두 black일때, 부모에게 extra black위임

_case 1.
doubley black의 형제가 red, 형제와 부모의 색을 바꾸고, 부모 노드를 기준으로 왼쪽으로 회전→ 앞의 ( 2-4 ) case 들 중 하나로 해결-

RB tree vs AVL

( RB tree, AVL ) 모든 연산에서의 시간복잡도 : $O(logN)$

	RB tree	AVL
삽입 삭제 성능	보다 빠르다	보다 느리다
검색 성능	보다 느리다	보다 빠르다
균형잡는 방식	속성을 만족시키도록	balance factor {-1.0,1}이 되도록
응용 사례	linux kernel, Java tree Map,c++ std::map 구현	dictionary, 수정이 적고 검색이 대부분인 상황에서 주로 사용