레드 블랙 트리
-
레드 블랙 트리 구현 및 테스트프로그래밍 기초/알고리즘 2021. 9. 19. 17:03
레드 블랙 트리 이진 검색 트리를 기반으로 노드에 색상을 추가하여 색상 규칙을 기준으로 트리의 균형을 유지한다. ※ 레드 블랙 트리는 노드의 수가 n일 때 최대 깊이가 Ο(logn)이 되게 된다. 레드 블랙 트리의 삽입 알고리즘 레드 블랙 트리의 삽입에서는 먼저 삽입하는 노드의 색상을 레드로 간주하고 삽입을 진행하며 삽입한 노드를 x, 부모 노드를 p, 형제 노드를 s라고 할 때 발생 가능한 모든 경우는 다음과 같다. p가 블랙인 경우 삽입 연산을 종료한다. s가 레드인 경우 p와 s를 블랙으로 바꾸고 p²을 레드로 바꾼다. 만약 p²가 루트면 p²를 블랙으로 바꾸고 종료한다. 연산 결과 p²이 레드이면 p²을 문제 발생 노드로 두고 재귀적으로 처리한다. s가 블랙인 경우 삽입된 위치에 따른 추가 연산을..