RB Tree

이진 탐색 트리 모든 원소는 유일한 키 값을 갖는다. 왼쪽(오른쪽#) 서브트리의 모든 원소들은 루트의 키보다 작은(큰#) 값을 갖는다. 왼쪽, 오른쪽 서브트리도 이진탐색트리이다. (재귀적인 정의) 모든 서브트리에 대해서 이상의 조건들이 만족하여야 한다. (재귀)

참고 자료(위키백과 - 우리 모두의 백과사전, ALGORITHMS - 토마스코멘,찰스 레이서손)https://ko.wikipedia.org/w/index.php?title=%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99\_%ED%8A%B8

회전 (Rotation)

삽입(insertion) 레드-블랙 트리에서 새로운 노드를 삽입할 때, 새로운 노드는 항상 적색으로 입력한다. 만약 트리가 레드블랙 트리의 특성을 위반하면, 두가지 operation 을 통해 트리의 구조를 조정한다. (1) Recolor (2) Rotation.

레드-블랙 트리의 특성(조건) 모든 노드는 적색이거나 흑색이다. 루트는 흑색이다. 모든 리프(NIL)는 흑색이다. 노드가 적색이면 그 노드의 자식은 모두 흑색이다. 각 노드로부터 그 노드의 자손인 리프로 가는 경로들은 모두 같은 수의 흑색 노드를 포함한다. 레드 블