5주차. AVL Tree & BR Tree
:트리의 균형을 맞추는 방법
5-8 규칙
Red Black Tree
-자가 균형 이진 탐색 트리로, 스스로 균형을 잡는 트리
-모든 노드는 빨간색 or 검은색으로 표시(현 강의에서는 색이 아닌 Boolean으로 표현)
-규칙에 어긋나면 색상변환 or 회전으로 해결
- 규칙
-Every node is red or black
-Root is always black
-New insertion are always red(만약 루트로 들어가면, red로 들어가 바로 black으로 색상 변환)
-Every path from root-leaf has the same number of black nodes
-No path can have two consecutive red nodes
-Null is black
즉,
1.노드는 레드 혹은 블랙 중 하나
2. Root node는 블랙!
3. 모든 리프 노드들은 블랙이다. (NIL)
4. 레드 노드의 자식노드는 양쪽 모두 블랙이다. (레드 노드의 부모노드는 블랙만 가능하다.)
5. 어떤 노드에서 시작하여 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.
+)두 개의 연속된 black 노드는 존재 가능
+)root에서 leaf까지 가는 여러 경로에서 red 노드의 갯수는 달라질 수 있다
==> 트리에 추가할 때마다 규칙을 따져야 한다!
if) 규칙이 깨졌을 경우, 해결방법
1. aunt가 black - 회전
결과: parent) black, children) red
2. aunt가 red - 색상 전환
결과: parent) red, children) black
5-9 RB Tree[예제]
ex1) 1,3,5,7를 RB Tree로 배열
:연속으로 red 노드가 연결되어 규칙 위반 so aunt가 red로 색상 변환
ex2) 위 배열에서 6추가
:연속 red 노드로 규칙 위반 so aunt 확인하니 빈 공간(black으로 처리)이므로 회전
ex3) 이후 8,9,10추가
:회전이 일어나는 경우, 원래 색상으로 노드를 배치한 뒤에 노드의 위치와 관계에 따라 색상을 정한다
결과)
:RB Tree에서는 black 노드의 갯수가 서로 다르거나 red 노드가 인접할 때 회전 발생!
:이 트리를 AVL Tree로 해석하면 균형 맞는 트리에 해당되나 모든 RB Tree가 AVL Tree로 해석할 때 맞는 건 아니다
- 모든 트리는 불균형이 일어나면 대처방식은 동일하다
만약 불균형이 일어난 장소가
right-right라면 L rotation
right-left라면 RL rotation
left-right라면 LR rotation
left-left라면 R rotation
5-10 클래스
- boolean으로 색상 구분: black-참, red-거짓
public class RedBlackTree<K,V> implements RedBlackI<K,V> {
Node<K,V> root;
int size; // 트리에 있는 요소의 갯수
class Node<K,V> { // 내부 클래스
K key;
V value;
Node<K,V> left, right, parent;
boolean isLeftChild, black;
public Node (K key, V value) { // 생성자 정의에 재네릭 사용X
this.key = key;
this.value = value;
left = null; // 노드 초기화
right = null;
parent = null;
black = false; // 새로 추가하는 노드는 red
isLeftChild = false; // 아직 left인지 right인지 모름
}
}
}:추가하는 노드는 트리와 혼자 놀기 때문에 left인지 right인지 결정X
- parent에 따라 aunt를 파악한다
-parent가 left child라면 aunt는 right
-parent가 right child라면 aunt는 left
