노드 x의 black height : 노드 x에서 임의의 자손 nil 노드까지 내려가는 경로에서의 black수(자기 자신은 카운트에서 제외), 5번 속성을 만족해야 성립하는 개념
RB 트리가 #5 속성을 만족하고 있고 두 자녀가 같은 색을 가질 때 부모와 두 자녀의 색을 바꿔줘도 #5 속성은 여전히 만족한다.
==> nil노드 까지 가는 black의 수는 같다. A의 부모노드 기준 black의 수 유지.
A를 기준으로 양옆 +1씩 black의 수 증가.
레드 블랙 트리에만 존재하는 개념
자녀가 없을 때 자녀를 nil 노드로 표기
ex) 40을 기준으로 왼쪽은 자녀가 있지만, 오른쪽은 nil 노드로 표시.
90을 기준으로 왼쪽, 오른쪽 모두 nil 노드로 표시
값이 있는 노드와 동등하게 취급한다.
삽입 노드의 색 : 삽입하는 노드는 항상 red다.
insert(50);
// 삽입하는 50은 red로 저장되고,
// 자녀 노드는 nil 노드이다.
root node는 반드시 black이여야 하는데 추가된 50은 red이다. 색을 변경한다.
insert(20);
// 추가되는 20은 red이고
// 자손 노드는 모든 nil 노드로 black
// 모든 노드를 기준으로 nil 노드까지의 black수가 동일하다.
// 50을 기준으로 blakc height = 양옆 모두 1, 20 기준 양옆 1
삽입 후에도 #5 속성을 만족하기 위해
임의의 노드를 기준으로 red가 추가되고 red의 자녀가 모두 nil 노드이다.
양쪽 모두 black수는 그대로 유지되기 때문에 #5속성이 유지된다.
insert(10);
// nil 노드 표시 생략.
// 새로 추가된 10은 red이지만, red의 자녀 노드들은 black이여야한다.
// 속성 위반
구조를 바꾸면서도 BST의 특징을 유지시키는 방법은 회전(로테이트)이다.
20을 기준으로 nil노드까지의 높이 양쪽 1, 10과 50을 기준으로 1
삽입된 red 노드가 부모의 왼쪽 자녀 & 부모도 red고 할아버지의 왼쪽 자녀
& 삼촌(=부모의 형제,sibling node)은 black이라면 부모와 할아버지의 색을 바꾼 후 할아버지 기준으로 오른쪽 회전한다.
==> 오른쪽 왼쪽을 바꿔도 성립한다.
insert(40);
// 추가된 40은 red이고,
// 부모 20은 red, 자녀 40도 red 속성위반.
20을 기준으로 왼쪽으로 회전 시켜 꺽인 부분을 펴준다.
insert(30);
// red 50의 자녀는 블랙이어야한다.
// red는 연속으로 나올 수 없다.
루트노드는 반드시 black이어야하고, black의 자녀가 black인것은 상관없다.
부모와 삼촌을 black으로 바꾸고, 할아버지를 red로 바꾼다.
그 후 할아버지에서 다시 확인을 시작한다.
delete(10);
10은 자녀가 없기 때문에 black이 제거되고 #5를 맞추기 위해 10노드가 존재하던 위치에 extra black을 부여한다.
doubly black : extra black이 부여된 black노드
delete(30);
30은 자녀 노드가 1개이기 때문에, 삭제되는 색은 black이며 30의 자리를 대체하는 25에 extra black을 부여한다.
red-and-black : extra black이 부여된 red 노드
delete(50);
50은 자녀가 2개이기 때문에 successor의 색 black이 제거된다.
red-and-black 노드를 black으로 바꾸면 해결.
결국 extra black을 어떻게 해결할 것인가 ? 4가지 방법이 존재한다.
doubly black의 형제의 색과 그 형제의 자녀들의 색에 따라 case가 나뉘어진다.
파란색으로 표시한 노드는 어떤색이던지 상관없다.
1)
레드 블랙 트리 특징 : 자녀의 노드색이 같을 경우 부모와 자녀색을 바꿔도 여전히 속성을 유지한다.
2) 부모의 자녀의 색 교환.
3) C의 색이 어떤것인지 모르기 때문에 red-and-black 또는 doubly black이 된다.
4) D가 왼쪽으로 갈 수 있도록 B와 D의 색을 바꾼다.
5) B를 기준으로 왼쪽으로 회전한다.
6) B의 자녀 노드 A,C는 extra black을 가지고 있는 상태이다.
7) 자녀 노드에 존재하는 extra black을 부모 B로 보내고, B를 black으로 변경한다.
C의 red를 E로 옮기면 case4와 같은형태이다. 즉, C의 red를 E로 옮기고 case4처럼 진행한다.
유튜브 26:58 red-black-tree 삭제 예제(이해하기!)
O(logN)