한화시스템 Beyond SW Camp/자료구조 알고리즘7 [자료구조] 레드-블랙 트리(Red-Black Tree) 레드 - 블랙 트리트리의 모양이 균형 잡히도록 각 노드들은 Red 혹은 Black의 색상을 가지고 모든 경우에서 O(lonN)의 시간 복잡도를 보장받는다.레드 - 블랙 트리 조건1. 루트 노드는 무조건 검은색이다.2. 연속된 빨간 노드는 올 수 없다. (No Double Red)3. 리프 노드(Nil)는 무조건 검은색이다.4. 모든 리프 노드에서 루트 노드까지 가는 검은색 수는 같다.5. 새로운 노드는 우선 빨간색으로 추가한다. 레드 - 블랙 트리 삽입 과정5를 삽입했다. 처음 데이터를 삽입했으니 루트 노드가 된다.1번 조건에서 루트 노드는 무조건 검은색이라 했으니 삽입된 5는 검은색이 된다. 2, 9를 삽입했다. 레드-블랙 트리는 이진 탐색 트리의 일종이기 때문에 기존 데이터보다 작으면 왼쪽, 크면 오.. 2025. 1. 16. 이전 1 2 다음
