728x90
Red-Black Tree
-
[자료구조] 레드-블랙 트리(Red-Black Tree)Computer Science/Data Structure 2023. 2. 27. 16:47
Red-Black Tree 자가 균형 이진 탐색 트리(self-balancing binary search tree) 로서, 대표적으로 연관 배열 등을 구현하는 데 쓰이는 자료구조입니다. 트리에 N개의 원소가 있을 때 O(log N)의 시간 복잡도를 삽입, 삭제, 검색을 할 수 있습니다. 레드-블랙 트리는 복잡한 자료구조이지만, 실 사용에서 효율적이고, 최악의 경우에도 일정한 실행 시간을 보장하여 실시간 처리와 같은 실행 시간이 중요한 경우에 유용하게 사용됩니다. 특성 Red-Black Tree는 각각의 노드가 Red, Black 두가지의 색상 속성을 가지고 있는 이진 탐색 트리입니다. 각 구성 원소는 in-order traversal(중위순회) 연산을 수행합니다. - in-order traversal(중..