레드 블랙 트리
1 | 이진 트리의 불균형문제를 해결하여 균형있게 탐색할 수 있도록 정렬하는 알고리즘. |
조건
- 루트노드는 항상 블랙.
- 새로 추가되는 노드는 항상 레드.
- 모든 깊이의 차수는 항상 동일해야 한다.
- 레드 노드가 연속되어서는 안된다.
연속된 레드 노드를 바꿔주는 방법
- 연속된 레드 노드의 부모 노드를 기준으로 양쪽에 레드 노드가 있을 때
- 레드는 블랙으로 블랙은 레드로 바꾼다. 단 루트 노드는 항상 블랙
- 연속된 레드 노드의 부모 노드를 기준으로 한쪽에 블랙 노드가 있을 때
- 회전시킨다
- 일자일때, 자식-자식-부모 형태라고 한다면 가운데 자식 노드를 부모 노드로 올려 놓는다.
- 꺾인 모양일때, 자식-자식-부모 형태라고 한다면 맨 밑 자식을 부모 노드로 올려 놓는다.
정렬 알고리즘 애니메이션 => toptal