Red black tree & B-tree

레드블랙트리

개념

- 모든 노드의 컬러가 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

굿노트에 정리함~~