To Be myself

레드-블랙 트리(red-black tree)2-3-4 트리를 이진 탐색 트리 형태로 구현한 것으로서, 검정 노드와 빨강 노드로 구성된 균형 탐색 트리 ⦁ 이진 탐색 트리로서 다음의 성질을 추가로 만족하는 균형 탐색 트리 ① 모든 노드는 검정이거나 빨강 ② 루트 노드와 리프 노드는 검정(단, 모든 리프 노드는 NULL 노드) ③ 빨강 노드의 부모 노드는 항상 검정 → 빨강 노드가 연달아 나타나지 않음 ④ 임의의 노드로부터 리프 노드까지의 경로상에는 동일한 개수의 검정 노드가 존재 ⦁ 탐색 연산 → 이진 탐색 트리의 탐색 방법과 동일 ⦁ 삽입 연산 → 탐색이 실패한 NULL 노드에 빨강 노드로 추가하고 두 자식 노드를 NULL 노드로 만듦 - 이때 빨강 노드가 연달아 나타나면 레드-블랙 트리의 성질을 만족..