레드-블랙 트리1 레드-블랙 트리 개념 각 노드에 한 비트의 color 필드가 추가로 있으며 아래 레드-블랙 특성을 모두 만족하는 이진 탐색 트리를 말한다. 레드-블랙 특성 각 노드 color는 '레드'이거나 '블랙'이다. 루트와 외부 노드(NIL)의 color는 블랙이다. 레드 노드의 부모 노드는 반드시 블랙이다. 임의의 노드 x에서 후손 리프까지 가는 경로에 있는 블랙 노드의 개수는 같다. 이것을 black-height(x)라고 한다. 트리의 높이 O(log n) n개의 키를 가진 레드-블랙 트리 T의 높이를 h라고 하면 h ≤ 2log(n+1) 이다. 높이차는 최대 2배 이상 커지지 않는다. 연산 O(log n) 탐색 최소값 찾기 최대값 찾기 선행자 후행자 삽입, 삭제 연산 알고리즘에서 수행하는 rotation은 최대 2회이다. 참.. 2021. 4. 11. 이전 1 다음