Red-Black Tree1 Red-Black tree ( 레드-블랙 트리 ) 레드 블랙 트리가 나온 이유 Red-Black tree 는 이진 검색 트리를 기반으로 한 자료구조이다.이진 검색 트리는 한쪽으로 치우쳐 질 경우 검색에서의 시간 복잡도가 O(N)으로 증가하는 문제가 있다. 이를 해결하기 위한 것이 레드-블랙 트리이다. 레드 블랙 트리의 조건 각 노드는 자료구조의 이름에서 알 수 있듯이 검은색, 빨간색으로 표기되고 다음과 같은 조건을 만족한다. 1. 루트 노드는 검은색이다. 2. 모든 리프 노드들은 검은색이다. 3. 빨간색 노드의 자식은 검은색이다. ( 빨간색 노드가 연속으로 나올 수 없다. ) 4. 리프 노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수는 같다. 레드 블랙 트리의 장점 레드 블랙 트리는 리프 노드까지 경로의 노드 색을 제한함으로써 리프 노드.. 2023. 4. 12. 이전 1 다음