레드 - 블랙 트리 - 위키백과, 우리 모두의 백과사전 레드 - 블랙 트리 위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 이 문서는 다른 언어판 위키백과의 문서 ( en : Red - black tree ) 를 번역 중이며, 한국어로 좀 더 다듬어져야 합니다. 번역에 이상이 있다면 직접 편집하시거나, 해당 글의 토론 문서에 의견을 남겨주세요. 레드 - 블랙 트리 ( Red - black tree ) 는 자가 균형 이진 탐색 트리 ( self - balancing binary search tree ) 로써, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조다. 1978년 레오 귀바스 ( Leo J. Guibas ) 와 로버트 [UNK] 1972년 루돌프 바이어가 창안한 " 대칭형 이진 B - 트리 " 를 발전시켜 만들었다. 레드 - 블랙 트리는 복잡한 자료구조지만, 실 사용에서 효율적이고, 최악의 경우에도 상당히 우수한 실행 시간을 보인다 : 트리에 n개의 원소가 있을 때 O ( log n ) 의 시간복잡도로 삽입, 삭제, 검색을 할 수 있다. 목차 1 용어 2 용도와 장점 3 특성 ( Properties ) 4 동작 4. 1 삽입 ( Insertion ) 4. 1. 1 첫 번째 경우 4. 1. 2 두 번째 경우 4
하다. 용도와 장점 [ 편집 ] 레드 - 블랙 트리는 자료의 삽입과 삭제, 검색에서 최악의 경우에도 일정한 실행 시간을 보장한다 ( worst - case guarantees ). 이는 실시간 처리와 같은 실행시간이 중요한 경우에 유용하게 쓰일 뿐만 아니라, 일정한 실행 시간을 보장하는 또 다른 자료구조를 만드는 데에도 쓸모가 있다. 예를 들면, 각종 기하학 계산에 쓰이는 많은 자료 구조들이 레드 - 블랙 트리를 기반으로 만들어져 있다. AVL 트리는 레드 - 블랙 트리보다 더 엄격하게 균형이 잡혀 있기 때문에, 삽입과 삭제를 할 때 최악의 경우에는 더 많은 회전 ( rotations ) 이 필요하다. 레드 - 블랙 트리는 함수형 프로그래밍에서 특히 유용한데, 함수형 프로그래밍에서 쓰이는 연관 배열이나 집합 ( set ) 등을 내부적으로 레드 - 블랙 트리로 구현해 놓은 경우가 많다. 이런 구현에는 삽입, 삭제시 O ( log n ) 만큼의 시간이 필요하다. 레드 - 블랙 트리는 2 - 3 - 4 트리와 등장변환이 가능하다 ( isometry ). 다시 말해서, 모든 2 - 3 - 4 트리에는 구성 원소와 그 순서 ( order ) 가 같은 레드 - 블랙 트리가 최소한 하나 이상 존재한다는
은 M이 검은 노드이고 C가 붉은 노드일 때이다. 검은 노드를 단순 삭제해버릴 경우 특성 4 ( 모든 붉은 노드는 두 개의 검은 자식 노드를 갖는다 ) 와 특성 5 ( 특정 노드에서부터 leaf로 가는 모든 경로에서 같은 수의 검은 노드를 지난다. ) 를 위반할 수 있으나, 우리가 C를 검은색으로 다시 칠하면, 두 가지 특성은 모두 만족할 수 있다. 복잡한 상황은 M과 C가 모두 검은색 노드일 때이다. ( 이 상황은 두 개의 leaf 자식을 갖고 있는 검은 노드를 지우는 상황에서만 발생한다. 왜냐하면, 검은 노드 M이 검은색 non - leaf 자식을 한 쪽에 갖고 있고 다른 쪽에 leaf 자식을 갖고 있으면, 양 쪽의 검은 노드 개수가 달라지게 되므로 특성 5에 대한 위반이다. ) 일단, M을 자식 노드 C로 치환하자. 그리고 이 자식 노드를 N으로 다시 이름짓고, 이 노드의 형제노드 ( 새로운 부모의 다른 자식 노드 ) 를 S라고 이름짓자. ( S는 원래 M의 형제노드이다. ) 아래의 다이어그램을 보면, N의 새로운 부모를 P ( M의 옛 부모 ) 라고 표기하고, SL을 S의 왼쪽 자식,
. 모든 리프 노드들 ( NIL ) 은 블랙이다. 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. ( 즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다 ) 어떤 노드로부터 시작되어 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다. 위 조건들을 만족하게 되면, 레드 - 블랙 트리는 가장 중요한 특성을 나타내게 된다 : 루트 노드부터 가장 먼 경로까지의 거리가, 가장 가까운 경로까지의 거리의 두 배 보다 항상 작다. 다시 말해서 레드 - 블랙 트리는 개략적 ( roughly ) 으로 균형이 잡혀 있다 ( balanced ). 따라서, 삽입, 삭제, 검색시 최악의 경우 ( worst - case ) 에서의 시간복잡도가 트리의 높이 ( 또는 깊이 ) 에 따라 결정되기 때문에 보통의 이진 탐색 트리에 비해 효율적이라고 할 수 있다. 왜 이런 특성을 가지는지 설명하기 위해서는, 네 번째 속성에 따라서, 어떤 경로에도 레드 노드가 연이어 나타날 수 없다는 것만 알고 있어도 충분하다. 최단 경로는 모두 블랙 노드로만 구성되어 있다고 했을 때, 최장 경로는 블랙 노드와 레드 노
- > right - > color = BLACK ; rotate - left ( n - > parent ) ; } else { s - > left - > color = BLACK ; rotate - right ( n - > parent ) ; } } case 2를 통과하면 N과 S는 반드시 검은색 노드가 된다. case 2를 통과한 후에 남는 경우의 수는 아래와 같은데, 아래의 경우 모두 각각의 case에서 해결된다. ( P, SL, SR ) = ( 검, 검, 검 ) - case 3에서 해결, ( 빨, 검, 검 ) - case 4에서 해결, ( 검, 빨, 검 ) - case 5에서 해결, ( 빨, 빨, 검 ) - case 5에서 해결, ( 검, 검, 빨 ) - case 6에서 해결, ( 빨, 검, 빨 ) - case 6에서 해결, ( 검, 빨, 빨 ) - case 6에서 해결, ( 빨, 빨, 빨 ) - case 6에서 해결. case 1 - 6까지의 경우를 다 지나면 위와 같이 모든 경우의 수에 대해 커버됨을 확인할 수 있다. ( 역자 주 ) 다시 이야기하지만, 함수 콜은 모두 tail recursion 을 이용하므로, 알고리즘은 in - place 이다. 위
레드 노드가 연이어 나타날 수 없다는 것만 알고 있어도 충분하다. 최단 경로는 모두 블랙 노드로만 구성되어 있다고 했을 때, 최장 경로는 블랙 노드와 레드 노드가 번갈아 나오는 것이 될 것이다. 다섯 번째 속성에 따라서, 모든 경로에서 블랙 노드의 수가 같다고 했기 때문에 존재하는 모든 경로에 대해 최장 경로의 거리는 최단 경로의 거리의 두 배 이상이 될 수 없다. 트리 구조를 나타낼 때, 어떤 노드는 자식 ( child ) 를 하나만 가질 수 있고, 리프 노드는 데이터를 담을 수 있다. 레드 - 블랙 트리도 이와 같은 방법으로 나타내 볼 수 있지만, 그런 표현 방식으로는 레드 - 블랙 트리의 특성이 변하고, 알고리즘과 상충될 수 있다. 그래서, 이 문서에서는 " nil leaves " 나 " null leaves " 를 사용하고 있는데, 이 " null leaf " 는 위의 그림에서와 같이 자료를 갖지 않으며, 트리의 끝을 나타내는 데만 쓰인다. 트리 구조를 그림으로 표현할 때, 종종 이 " null leaf " 를 생략하고 그리는 경우가 많은데, 그러면 그림상으로는 레드 - 블랙 트리의 특성을 만족하지 못하는 것처럼 보일 수 있으나 실제로는 그렇지 않다. 이렇게 함으로써
else return g - > left ; } 첫 번째 경우 [ 편집 ] N 이라고 하는 새로운 노드가 트리의 시작 ( root ) 에 위치한다. 이 경우, 레드 - 블랙 트리의 첫 번째 속성 ( 트리의 시작은 검정색이다 ) 을 만족하기 위해서, N을 검정색으로 표시한다. 이 경우, 시작점으로부터 뻗어나가는 모든 경로에 검정색 노드를 하나 추가한 셈이 되기 때문에 레드 - 블랙 트리의 다섯 번째 속성 ( 한 노드에서부터 뻗어나가는 모든 경로에 대해 검정색 노드의 수는 같다 ) 은 여전히 유효하다. void insert - case1 ( struct node * n ) { if ( n - > parent = = NULL ) n - > color = BLACK ; else insert - case2 ( n ) ; } 두 번째 경우 [ 편집 ] 새로운 노드의 부모 노드 P가 검정색이므로, 레드 - 블랙 트리의 네 번째 속성 ( 붉은색 노드의 모든 자식 노드는 검정색이다 ) 은 유효하다. 그러므로 두 번째 경우에도 이 트리는 적절한 레드 - 블랙 트리이다. 레드 - 블랙 트리의 다섯 번째 속성 ( 한 노드에서부터 뻗어나가는 모든 경로에 대해 검정색 노드의 수는 같다 )
차 1 용어 2 용도와 장점 3 특성 ( Properties ) 4 동작 4. 1 삽입 ( Insertion ) 4. 1. 1 첫 번째 경우 4. 1. 2 두 번째 경우 4. 1. 3 세 번째 경우 4. 1. 4 네 번째 경우 4. 1. 5 다섯 번째 경우 4. 2 삭제 ( Removal ) 4. 3 비대칭 경계의 증명 ( Proof of asymtotic bounds ) 4. 4 병렬 알고리즘 ( Parallel algorithms ) 5 각주 용어 [ 편집 ] 레드 - 블랙 트리는 이진 트리의 특수한 형태로서, 컴퓨터 공학 분야에서 숫자 등의 비교 가능한 자료를 정리하는 데 쓰이는 자료구조이다. 이진 트리에서는 각각의 자료는'노드 ( node, 분기점 )'에 저장이 된다. 자료를 트리 구조로 저장할 때, 노드들 중 최상위에 있는 노드를 루트 노드 ( root node ) 라고 부른다. 이진 트리에서 노드는 최대 두 개의 자식 노드를 가질 수 있다. 각각의 자식 노드도 역시 최대 두 개의 자식 노드를 가질 수 있으며, 이런식으로 계속 연결된다. 그러므로, 어떤 트리도 루트 노드로부터 그 트리에 속한 모든 노드에 도달할 수 있다. 어떤 노드에 자식 노드가 없다면, 그 노
는 부모 노드 P가 할아버지 노드 G의 왼쪽 자식이라고 가정하고 진행한다. 만약 P가 G의 오른쪽 자식이라고 했을 때는 네 번째, 다섯 번째 경우에서 왼쪽과 오른쪽을 바꿔서 진행하면 된다. 소스 코드에서는 이를 이미 고려해서 작성되었다. 네 번째 경우 [ 편집 ] 네 번째 경우의 도식 부모 노드 P가 붉은색인데, 삼촌 노드 U는 검정색이다 ; 또한 새로운 노드 N은 P의 오른쪽 자식 노드이며, P는 할아버지 노드 G의 왼쪽 자식 노드이다. 이 경우, N과 P의 역할을 변경하기 위해서 왼쪽 회전을 한다 ; 그 후, 부모 노드였던 P를 다섯 번째 경우에서 처리하게 되는데, 이는 레드 - 블랙 트리의 네 번째 속성 ( 붉은색 노드의 모든 자식은 검정색 노드이다 ) 을 아직 만족하지 않기 때문이다. 회전 작업은 몇몇 경로들 [ 2 ] 이 이전에는 지나지 않았던 노드를 지나게 하는데, 그럼에도 양쪽 노드가 모두 붉은색이므로, 레드 - 블랙 트리의 다섯 번째 속성 ( 한 노드에서부터 뻗어나가는 모든 경로에 대해 검정색 노드의 수는 같다 ) 을 위반하지 않는다. void insert - case4 ( struct node * n ) { struct node * g
는 G가, 바뀐 후에는 P가 P, G, N중 유일한 검정색 노드이다. void insert - case5 ( struct node * n ) { struct node * g = grandparent ( n ) ; n - > parent - > color = BLACK ; g - > color = RED ; if ( n = = n - > parent - > left ) rotate - right ( g ) ; else rotate - left ( g ) ; } 삽입 동작은 치환 작업인데, 이는 모든 호출 ( call ) 이 tail recursion이기 때문이다. 삭제 ( Removal ) [ 편집 ] 통상적인 이진검색트리에서 두 개의 non - leaf 자식을 가진 노드를 지울 때, 우리는 노드의 왼쪽 서브트리에서 최댓값 ( 중위 순회시 바로 전값 ) 을 찾거나, 오른쪽 서브트리에서 최솟값 ( 중위 순회시 바로 뒤에 값 ) 을 찾아 해당 값을 지우고자 하는 노드로 옮긴다. ( 여기 에서 처럼 ) 그리고 나서 우리는 값을 복사해온 노드를 지우는데, 이 노드는 반드시 2개보다 적은 non - leaf 자식을 갖고 있다. ('자식'이 아니라'non - leaf 자식'이라
레드-블랙 트리(red-black tree)는 자가 균형 이진 탐색 트리(self-balancing binary search tree)로서, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조다. 1978년 레오 귀바스(Leo J. Guibas)와 로버트 세지윅이 1972년 루돌프 바이어가 창안한 "대칭형 이진 B-트리"를 발전시켜 만들었다. 레드-블랙 트리는 복잡한 자료구조지만, 실 사용에서 효율적이고, 최악의 경우에도 상당히 우수한 실행 시간을 보인다: 트리에 n개의 원소가 있을 때 O(log n)의 시간복잡도로 삽입, 삭제, 검색을 할 수 있다.