##드 C라고 부르겠다. 만약 M이 붉은 노드이면, 우리는 단순히 특성 4에 의해 검은 노드여야 할 자식 노드 C를 M대신 치환하면 된다. ( 이 상황은 M이 두 개의 leaf 자식을 갖고 있을 때에만 발생한다. 왜냐하면 만약 M이 한 쪽에는 검은 non - leaf 자식 노드를 갖고 있고, 다른 쪽에 검은 leaf 자식 노드를 갖고 있다면, 양쪽의 검은 노드 개수가 달라지게 되어 특성 5를 위반하게 되기 때문이다. ) 삭제된 노드를 지나는 모든 path는 단순히 붉은 노드 하나만 없어지게 되고, 삭제된 노드의 부모와 자식 모두 검은 노드이므로, 특성 3 ( 모든 leaf들은 검은 노드 ) 과 특성 4 ( 모든 붉은 노드는 두 개의 검은 자식 노드를 갖는다 ) 는 여전히 유효하다. 또 다른 간단한 상황은 M이 검은 노드이고 C가 붉은 노드일 때이다. 검은 노드를 단순 삭제해버릴 경우 특성 4 ( 모든 붉은 노드는 두 개의 검은 자식 노드를 갖는다 ) 와 특성 5 ( 특정 노드에서부터 leaf로 가는 모든 경로에서 같은 수의 검은 노드를 지난다. ) 를 위반할 수 있
균형 splay 힙 이진 힙 피보나치 R 트리 R * R 힐버트 트리 해시 트리 그래프 이진 결정 다이어그램 자료 구조의 목록 원본 주소 " " 분류 : 트리 구조숨은 분류 : 번역 중인 문서빈 문단이 포함된 문서 둘러보기 메뉴 개인 도구 로그인하지 않음토론기여계정 만들기로그인 이름공간 문서토론 변수 보기 읽기편집역사 보기 더 보기 검색 둘러보기 대문사용자 모임요즘 화제최근 문서 보기임의 문서로도움말기부 도구 여기를 가리키는 문서가리키는 글의 최근 올리기특수 문서 목록고유 링크문서 정보위키데이터 항목이 문서 인용하기 다른 프로젝트 공용 인쇄 / 내보내기 책 만들기PDF로 다운로드인쇄용 판 다른 언어 IndonesiaItaliano 日 本 語 / 中 文 - - 링크 편집 이 문서는 2019년 7월 1일 ( 월 ) 15 : 10에 마지막으로 편집되었습니다. 모든 문서는 크리에이티브 커먼즈 저작자표시 - 동일조건변경허락 3. 0에 따라 사용할 수 있으며, 추가적인 조건이 적용될 수 있습니다. 자세한 내용은 이용 약관을 참고하십시오. 미국 및 다른 국가에 등록되어 있는 Wikimedia Foundation, Inc. 소유의 등록 상표
않기 때문에 모두 합쳐서 3번보다 많은 수의 회전은 일어나지 않는다. 비대칭 경계의 증명 ( Proof of asymtotic bounds ) [ 편집 ] 이 문단은 비어있습니다. 내용을 추가해 주세요. 병렬 알고리즘 ( Parallel algorithms ) [ 편집 ] 아이템의 수에 비례하여 컴퓨터 프로세서를 이용할 수 있다면, 정렬되어 있는 아이템을 가지고 레드 - 블랙 트리를 만드는 병렬 알고리즘은 상수시간이나 O ( log log n ) { displaystyle O ( log log n ) } 시간으로 구현될 수 있다. 빠른 검색, 삽입, 삭제를 위한 병렬 알고리즘 또한 알려져 있다. [ 3 ] 각주 [ 편집 ] ↑ en : Thomas H. Cormen ; Charles E. Leiserson ; Ronald L. Rivest ; en : Clifford Stein ( 2009 ). 《 Introduction to Algorithms ( 3rd ed. ) 》. MIT Press. 308 - 309쪽. ISBN 978 - 0 - 262 - 03384 - 8. ↑ " 1 " 이라는 이름이 붙어 있는 부분 트리 ( sub - tree ) ↑ Park, Heejin ; Park, Kunsoo ( 2001 ). " Parallel alg
node * 형식으로 하나 만들어주고 사용하면 된다. 이 노드는 색깔이 검정색이고, 자식은 가질 수 없고 오직 부모만 가질 수 있다. * / return ( n = = LEAF ) 1 : 0 ; } void replace - node ( struct node * n, struct node * child ) { / * * 앞에서 n의 부모가 NULL이 되는 경우를 delete - case에 오지 않게 미리 처리해주면 된다. * / child - > parent = n - > parent ; if ( n - > parent - > left = = n ) n - > parent - > left = child ; else if ( n - > parent - > right = = n ) n - > parent - > right = child ; } void delete - one - child ( struct node * n ) { / * * 선제조건 : n이 최대 하나의 non - null 자식을 갖고 있음. * / struct node * child = is - leaf ( n - > right ) n - > left : n - > right ; replace - node ( n, child ) ; if ( n - > color
##지 않았던 노드를 지나게 하는데, 그럼에도 양쪽 노드가 모두 붉은색이므로, 레드 - 블랙 트리의 다섯 번째 속성 ( 한 노드에서부터 뻗어나가는 모든 경로에 대해 검정색 노드의 수는 같다 ) 을 위반하지 않는다. void insert - case4 ( struct node * n ) { struct node * g = grandparent ( n ) ; if ( ( n = = n - > parent - > right ) ( n = = n - > parent - > right ) & & ( n - > parent = = g - > left ) ) { rotate - left ( n - > parent ) ; n = n - > left ; } else if ( ( n = = n - > parent - > left ) ( n = = n - > parent - > left ) & & ( n - > parent = = g - > right ) ) { rotate - right ( n - > parent ) ; n = n - > right ; } insert - case5 ( n ) ; } static void rotate - left ( struct node * n ) { struct node * c = n - > right ; struct node
- > color = = RED ) ( n - > parent - > color = = RED ) & & ( s - > color = = BLACK ) & & ( s - > left - > color = = BLACK ) & & ( s - > right - > color = = BLACK ) ) { s - > color = RED ; n - > parent - > color = BLACK ; } else delete - case5 ( n ) ; } Case 5 : S가 검정, S의 왼쪽 자식이 빨강, S의 오른쪽 자식이 검정이며, N이 부모의 왼쪽 자식인 경우. 이 경우 우리는 S를 오른쪽으로 회전시켜서 S의 왼쪽 자식이 S의 부모노드이자 N의 새로운 형제 노드가 되도록 만든다. 그리고 나서 우리는 S의 색을 부모 노드의 색깔과 바꾼다. 모든 경로는 여전히 같은 수의 검은 노드수를 가지나, 이제 N이 오른쪽에 붉은 노드를 자식으로 둔 검은색 형제노드를 갖게 되었으므로, 6번째 case로 진행하면 된다. N이나 N의 부모노드는 이 변형에 아무런 영향을 받지 않는다. ( 다시 말하지만, N의 새로운 형제 노드를 6번째 case에서 S라고 부르도록 할 것이다
( n - > parent - > color = = BLACK ) ( n - > parent - > color = = BLACK ) & & ( s - > color = = BLACK ) & & ( s - > left - > color = = BLACK ) & & ( s - > right - > color = = BLACK ) ) { s - > color = RED ; delete - case1 ( n - > parent ) ; } else delete - case4 ( n ) ; } Case 4 : S와 S의 자식들은 검은색이지만, P는 빨강인 경우. 이 경우, 우리는 단순히 S와 P의 색을 바꾸면 된다. 이는 S를 지나는 경로의 검은 노드 개수에 영향을 주지 않지만, N을 지나는 경로에 대해서는 검은 노드의 개수를 1개 증가시킨다. 이는 원래 삭제된 검은 노드의 개수를 보충해준다. void delete - case4 ( struct node * n ) { struct node * s = sibling ( n ) ; if ( ( n - > parent - > color = = RED ) ( n - > parent - > color = = RED ) & & ( s - >
##ft ( struct node * n ) { struct node * c = n - > right ; struct node * p = n - > parent ; if ( c - > left! = NULL ) c - > left - > parent = n ; n - > right = c - > left ; n - > parent = c ; c - > left = n ; c - > parent = p ; if ( p! = NULL ) { if ( p - > left = = n ) p - > left = c ; else p - > right = c ; } } static void rotate - right ( struct node * n ) { struct node * c = n - > left ; struct node * p = n - > parent ; if ( c - > right! = NULL ) c - > right - > parent = n ; n - > left = c - > right ; n - > parent = c ; c - > right = n ; c - > parent = p ; if ( p! = NULL ) { if ( p - > right = = n ) p - > right = c ; else p - > left = c
##에 대해 최장 경로의 거리는 최단 경로의 거리의 두 배 이상이 될 수 없다. 트리 구조를 나타낼 때, 어떤 노드는 자식 ( child ) 를 하나만 가질 수 있고, 리프 노드는 데이터를 담을 수 있다. 레드 - 블랙 트리도 이와 같은 방법으로 나타내 볼 수 있지만, 그런 표현 방식으로는 레드 - 블랙 트리의 특성이 변하고, 알고리즘과 상충될 수 있다. 그래서, 이 문서에서는 " nil leaves " 나 " null leaves " 를 사용하고 있는데, 이 " null leaf " 는 위의 그림에서와 같이 자료를 갖지 않으며, 트리의 끝을 나타내는 데만 쓰인다. 트리 구조를 그림으로 표현할 때, 종종 이 " null leaf " 를 생략하고 그리는 경우가 많은데, 그러면 그림상으로는 레드 - 블랙 트리의 특성을 만족하지 못하는 것처럼 보일 수 있으나 실제로는 그렇지 않다. 이렇게 함으로써, 모든 노드들은 설령 하나 또는 두개의 자식이 " null leaf " 일지라도, 두개의 자식 ( children ) 을 가지게 된다. 간혹 레드 - 블랙 트리를 노드가 아닌 붉은색 또는 검은색 선분 ( edge ) 으로 설명하기도 하는데, 실제로는 같은 이야기이다. 어떤 노드의 색은 노드와 그 부모를 연결하
) 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 ) 라고 부른다. 이진 트리에서 노드는 최대 두 개의 자식 노드를 가질 수 있다. 각각의 자식 노드도 역시 최대 두 개의 자식 노드를 가질 수 있으며, 이런식으로 계속 연결된다. 그러므로, 어떤 트리도 루트 노드로부터 그 트리에 속한 모든 노드에 도달할 수 있다. 어떤 노드에 자식 노드가 없다면, 그 노드를 리프 노드 ( leaf node ) 라고
레드-블랙 트리(red-black tree)는 자가 균형 이진 탐색 트리(self-balancing binary search tree)로서, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조다. 1978년 레오 귀바스(Leo J. Guibas)와 로버트 세지윅이 1972년 루돌프 바이어가 창안한 "대칭형 이진 B-트리"를 발전시켜 만들었다. 레드-블랙 트리는 복잡한 자료구조지만, 실 사용에서 효율적이고, 최악의 경우에도 상당히 우수한 실행 시간을 보인다: 트리에 n개의 원소가 있을 때 O(log n)의 시간복잡도로 삽입, 삭제, 검색을 할 수 있다.