05_week_C_RB_tree

RB 트리

BST (이진 탐색 트리) 의 한 종류
양쪽의 균형을 맞추면서 만들어진다
장점 : 시간 복잡도가 O(LogN) 이 됨 (그냥 이진트리는 최악의 경우 시간 복잡도 O(N))

속성 - RB Tree의 규칙(무조건 지켜져야함)
1. 모든 노드는 red 혹은 black
2. 루트 노드는 black
3. 모든 Nil(비어있는) 노드는 black
4. 노드가 red라면 자녀들은 black
5. 각 노드에서 자손 nil 노드들까지 가는 모든 경로는 black 수가 같다.(black height의 값이 같다)
black height : 임의의 노드에서 Nil 노드까지 갈때까지 Black의 수

삭제 방법
삭제되는 색이 black
삭제되는 색이 있던 위치를 대체한 노드에 extra black 부여
대체한 노드가 red-and- black이면 black으로 바꿔줌
대체한 노드가 doubly black이면 위의 속성을 지키기위에 회전과 색 전환을 사용함

youtube : 쉬운코드
RB tree visualization