관리 메뉴
목록2025/03/05 (1)
개발자공부일기
Red-Black Tree
레드-블랙 트리(Red-Black Tree) 레드-블랙 트리는 자가 균형 이진 탐색 트리이다. 레드-블랙 트리는 다음과 같은 조건들을 만족한다.1. 모든 노드는 빨간색 혹은 검은색이다.2. 루트 노드는 검은색이다.3. 모든 리프 노드(NIL)들은 검은색이다. (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드)4. 빨간색 노드의 자식은 검은색이다. == No Double Red(빨간색 노드가 연속으로 나올 수 없다)5. 모든 리프 노드에서 Black Depth는 같다. == 리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다.삽입우리는 삽입 후 밸런싱을 하기 위해 회전을 도구로 사용했습니다. Red-Black 트리에서 우리는 밸런싱을 하기 위해 두..
CS지식/자료구조
2025. 3. 5. 21:01