TIL 11월 4일 2023년

레드 블랙 트리 속성

1. 모든 노드는 red, 와 black의 색상을 가짐.
2. 루트 노드는 black 이어야 함
3. 모든 nil(leaf) 노드는 black 이어야함
4. red의 자녀들은 black, or red가 연속적으로 존재할 수 없다.
5. 임의의 노드에서 자손 nil 노드들 까지 가는 경로들의 black 수는 같다. (자기 자신은 카운트에서 제외) Q . 리프 노드는 블랙인가?

노드 x의 black height

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

색을 바꾸면서도 5번 속성을 유지하기

• rb 트리가 #5 속성을 만족하고 있고 두 자녀가 같은 색을 가질 때, 부모와 두 자녀의 색을 바꿔줘도 #5 속성은 여전히 만족한다.

nil 노드

• 존재하지 않음을 의미하는 노드
• 자녀가 없을 때 자녀를 nil 노드로 표기
• 값이 있는 노드와 도읃ㅇ하게 취급
• RB 트리에서 leaf(자료가 없는) 노드는 nil 노드

RB 트리는 어떻게 균형을 잡는가?

• 삽입/삭제 시 주로 속성 4, 5를 위반하며 이들을 해결하려고 구조를 바꾸다 보면 자연스럽게 트리의 균형이 잡히게 된다.

RB 트리 삽입 방식

1. 삽입 전 RB 트리 속성 만족한 "상태"
2. 삽입 방식은 일반적인 BST와 동일 [[이진 탐색 트리]]
3. 삽입 후 RB 트리 위반 여부 "확인"
4. RB 트리 속성을 위반했다면 "재조정"
5. RB트리 속성을 다시 만족

insert(50)

• 노드(레드)를 삽입 할 때 노드의 nil 노드의 색은 balck으로 고정 그러면 자연스럽게 #3 속성을 만족 (3번 속성 : 모든 nil 노드는 black) 현재는 2번 속성을 위반한 상태
• 루트 노드를 black으로 바꾸면 해결할 수 있다 (2번 속성 : 루트 노드는 black)
• 정리 : red 삽입 후 2번 속성을 위반했을 때 루트노드를 black으로 바꿔준다.
• 왜 새로 삽입하는 노드는 red인가? 삽입후에도 5번 속성을 유지하기 위해. (5번 속성 : 임의의 노드에서 자손 nil 노드들 까지 가는 경로들의 black 수는 같다)

회전

case.3

• 50->20->10 의 그래프 상황에서 10<- 20 ->50, 즉 바이너리 트리의 특성을 유지해야 할 때 쓰는 방법.
• 1. #4 속성 위반을 해결하기 위해 red 하나를 넘겨야함 (속성 4 : 노드가 red라면 자녀들은 black)
• 2. 20(레드)과 50(블랙)의 색을 바꿔주고
• 3. 20과 50을 회전(?) 시켜준다. (Q.어떻게????)
• 4번 속성 만족하게 됨
• 정리 : 부모와 할아버지의 색을 바꾼후 할아버지 기준으로 오른쪽으로 회전한다.

case.2

50->10->40 경우는 어떻게 해야할까?

• 20을 기준으로 왼쪽으로 회전한다. 50->40->20
• case3 의 형태가 됨으로 위와 같이 해결한다.

case.1

• red 삽입 후 #4 속성을 위반했을 때
• 삽입된 red 노드의 부모도 red & 삼촌(=부모의 형제) 도 red라면
• 부모와 삼촌을 black으로 바꾸고 할아버지를 red로 바꾼 뒤
• 할아버지에서 다시 확인을 시작한다.

정리

레드 블랙트리의 다섯가지 속성

1. 각 노드는 레드 혹은 블랙
2. 루트 노드는 블랙
3. 모든 리프(닐 노드)는 블랙
4. 레드 노드의 양쪽 자식은 모두 블랙 노드 (즉, 레드 노드는 연속될 수 없음)
5. 어떤 노드로부터 그 노드의 후손인 모든 리프까지 이어지는 각각의 경로에는 같은 수의 블랙 노드가 있음.

레드 블랙트리에서 삽입, 삭제 과정 중에 발생 할 수 있는 문제

• Case : 1 새 노드(N)의 부모(P)가 블랙인 경우

  이 경우는 문제가 되지 않음, 새로 삽입된 레드 노드가 블랙 부모를 가지므로, 트리의 속성이 유지 됨.

• Case : 2 새 노드의 부모(P)와 부모의 형제(U) 가 레드인 경우

  이 경우 부모와 부모의 형제를 블랙으로, 조부모를 레드로 바꾸고, 조부모에서 재귀적으로 균형 조정을 시도.

• Case : 3 새 노드의 부모(P)는 레드이지만, 부모의 형제(U)는 블랙인 경우

  이 경우 복잡하며, 새 노드와 부모의 위치에 따라 회전이 필요함. 크게 두가지로 나뉨 .
  Case 3a : 새 노드(N)가 부모(P) 의 오른쪽 자식이고, 부모(P)가 조부모(G)의 왼쪽 자식일 때 이 경우에는 P 에서 좌회전을 하여 Case 3b로 변환.
  Case 3b : 새 노드(N)가 부모(P)의 왼쪽 자식이고, 부모(P)가 조부모(G)의 왼쪽 자식일 때 이 경우에는 G에서 우회전을 하고, P와 G의 색을 바꿈.

---

• EC2서버의 리눅스를 vscode와 ssh로 연결하는 방법 중 키 권한을 너무 열어 놓으면(상위폴더) 접속 안됨 로컬 컴퓨터의 권한을 바꿔줘야함.
• .vscode 폴더 있는 파일에 관련한 링크
• https://80000coding.oopy.io/93593d7e-617f-412e-9615-8051bd16104f
• https://velog.io/@markyang92/vscode
• https://best-mother-seonnyeo.tistory.com/63