레드블랙트리
개념
- 모든 노드의 컬러가 red / black 인 binary search tree
- 모든 빈 노드(null pointer)가 외부 노드로 대체된다 (external node = 맨끝에잇는 리프노드. 네모)
(자녀가 없음 -> 자녀를 nill 노드라고 설정함)
- 복잡도 O(log n) !!!
- rank : 해당 노드에서부터 external node까지 블랙노드 개수
lemma (부명제)
- h<=2lon(n+1)
이므로 삽입, 삭제의 복잡도가 O(logn임을 알수 ㅇ)
증명 ..
특징
- 루트와 외부노드는 블랙
- 루트에서 외부까지 경로에서 레드가 연속으로 나올 수 x (root-to-external path)
-> 부모가 레드면 자식은 무조건 블랙 (삽입시 어기게됨) - 레드규칙 이라고 부름
- 루트에서(임의의 노드에서) 외부까지 모든경로에서 블랙 개수는 같다! (자기 자신은 제외)
-> delete연산시 위반가능.
연산
1. insert
굿노트에 정리함~~