Red Black Tree (레드 블랙 트리) 레드 블랙 트리는 균형 이진 탐색 트리로 탐색, 삽입, 삭제 모두 시간 복잡도가 O(logn) 입니다. 각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하며, 삽입 및 삭제 중에 트리가 균형을 유지하도록 하는데 사용됩니다. * 균형이진트리 단, 다음의 성질을 만족하도록 색칠을 해야 하는데, 이를 레드블랙특성이라 한다.
노드는 레드 혹은 블랙의 색을 가진다. 루트는 블랙이다.
모든 리프(NIL)노드는 블랙이다. 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.
(블랙의 자식은 뭐든 상관없다.) 로트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다. 5번째 특성때문에 밸런스가 맞아지고 O(logn)의 시간복잡도를 가지게 된다.
“모든 리프 노드와 루트 노드는 블랙이고 어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.” NIL이 뭐냐면 null값같은 노드이다.
원래 아무것도 없는건데 레...
원문 링크 : Red Black Tree (레드 블랙 트리)
