레드 - 블랙 트리 - 위키백과, 우리 모두의 백과사전 레드 - 블랙 트리 위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 이 문서는 다른 언어판 위키백과의 문서 ( en : Red - black tree ) 를 번역 중이며, 한국어로 좀 더 다듬어져야 합니다. 번역에 이상이 있다면 직접 편집하시거나, 해당 글의 토론 문서에 의견을 남겨주세요. 레드 - 블랙 트리 ( Red - black tree ) 는 자가 균형 이진 탐색 트리 ( self - balancing binary search tree ) 로써, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조다. 1978년 레오 귀바스 ( Leo J. Guibas ) 와 로버트 [UNK] 1972년 루돌프 바이어가 창안한 " 대칭형 이진 B - 트리 " 를 발전시켜 만들었다. 레드 - 블랙 트리는 복잡한 자료구조
블랙 노드만이 레드 노드의 부모 노드가 될 수 있다 ) 어떤 노드로부터 시작되어 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다. 위 조건들을 만족하게 되면, 레드 - 블랙 트리는 가장 중요한 특성을 나타내게 된다 : 루트 노드부터 가장 먼 경로까지의 거리가, 가장 가까운 경로까지의 거리의 두 배 보다 항상 작다. 다시 말해서 레드 - 블랙 트리는 개략적 ( roughly ) 으로 균형이 잡혀 있다 ( balanced ). 따라서, 삽입, 삭제, 검색시 최악의 경우 ( worst - case ) 에서의 시간복잡도가 트리의 높이 ( 또는 깊이 ) 에 따라 결정되기 때문에 보통의 이진 탐색 트리에 비해 효율적이라고 할 수 있다. 왜 이런 특성을 가지는지 설명하기
중요한 경우에 유용하게 쓰일 뿐만 아니라, 일정한 실행 시간을 보장하는 또 다른 자료구조를 만드는 데에도 쓸모가 있다. 예를 들면, 각종 기하학 계산에 쓰이는 많은 자료 구조들이 레드 - 블랙 트리를 기반으로 만들어져 있다. AVL 트리는 레드 - 블랙 트리보다 더 엄격하게 균형이 잡혀 있기 때문에, 삽입과 삭제를 할 때 최악의 경우에는 더 많은 회전 ( rotations ) 이 필요하다. 레드 - 블랙 트리는 함수형 프로그래밍에서 특히 유용한데, 함수형 프로그래밍에서 쓰이는 연관 배열이나 집합 ( set ) 등을 내부적으로 레드 - 블랙 트리로 구현해 놓은 경우가 많다. 이런 구현에는 삽입, 삭제시 O ( log n ) 만큼의 시간이 필요하다. 레드 - 블랙 트리는 2 - 3 - 4 트리와 등장변환이 가능하다 (
탐색 트리는, 모든 노드에 대해'자신이 가진 자료는 자신보다 오른쪽에 위치한 부분트리가 가지고 있는 모든 자료보다 작거나 같고, 자신보다 왼쪽에 위치한 부분트리가 가지고 있는 모든 자료보다 크거나 같다'라는 조건을 만족한다. 이런 특성 때문에 특정 값을 빠르게 찾아 낼 수 있으며, 각 구성원소 ( elements ) 간의 효율적인 in - order traversal이 가능하다. 용도와 장점 [ 편집 ] 레드 - 블랙 트리는 자료의 삽입과 삭제, 검색에서 최악의 경우에도 일정한 실행 시간을 보장한다 ( worst - case guarantees ). 이는 실시간 처리와 같은 실행시간이 중요한 경우에 유용하게 쓰일 뿐만 아니라, 일정한 실행 시간을 보장하는 또 다른 자료구조를 만드는 데에도 쓸모가 있다.
로버트 [UNK] 1972년 루돌프 바이어가 창안한 " 대칭형 이진 B - 트리 " 를 발전시켜 만들었다. 레드 - 블랙 트리는 복잡한 자료구조지만, 실 사용에서 효율적이고, 최악의 경우에도 상당히 우수한 실행 시간을 보인다 : 트리에 n개의 원소가 있을 때 O ( log n ) 의 시간복잡도로 삽입, 삭제, 검색을 할 수 있다. 목차 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 병렬 알고리즘 ( Par
고 나서는 두 번 보다 많은 횟수의 추가적인 회전은 일어나지 않기 때문에 모두 합쳐서 3번보다 많은 수의 회전은 일어나지 않는다. 비대칭 경계의 증명 ( Proof of asymtotic bounds ) [ 편집 ] 이 문단은 비어있습니다. 내용을 추가해 주세요. 병렬 알고리즘 ( Parallel algorithms ) [ 편집 ] 아이템의 수에 비례하여 컴퓨터 프로세서를 이용할 수 있다면, 정렬되어 있는 아이템을 가지고 레드 - 블랙 트리를 만드는 병렬 알고리즘은 상수시간이나 O ( log log n ) { [UNK] displaystyle O ( [UNK] log [UNK] log n ) } 시간으로 구현될 수 있다. 빠른 검색, 삽입, 삭제를 위한 병렬 알고리즘 또한 알려져 있다. [ 3 ] 각주 [ 편집 ] ↑ en : Thomas H. Cormen ; Charles E. Le
교과서들이 레드 - 블랙 트리가 나오기 바로 전에 2 - 3 - 4 트리를 소개하고 있다. 특성 ( Properties ) [ 편집 ] 레드 - 블랙 트리의 예 레드 - 블랙 트리는 각각의 노드가 레드 나 블랙 인 색상 속성을 가지고 있는 이진 탐색 트리이다. 이진 탐색 트리가 가지고 있는 일반적인 조건에 다음과 같은 추가적인 조건을 만족해야 유효한 ( valid ) 레드 - 블랙 트리가 된다 : [ 1 ] 노드는 레드 혹은 블랙 중의 하나이다. 루트 노드는 블랙이다. 모든 리프 노드들 ( NIL ) 은 블랙이다. 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. ( 즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다 ) 어떤 노드로부터 시작되어 리프 노드에 도달하는 모든 경로에
복잡한 동작이지만, 그 복잡도는 여전히 O ( log n ) 이다. 삽입 ( Insertion ) [ 편집 ] 레드 - 블랙 트리의 삽입은 단순 이진 탐색 트리에서 하는 것과 같이 노드를 삽입하고, 색을 붉은색으로 정하는 것으로 시작한다. 그 다음 단계는, 그 주위 노드의 색에 따라 달라진다. 여기서'삼촌 노드 ( uncle node )'를 도입할텐데, 이는 같은 높이에 있는 옆 노드 ( 다시 말해, 사촌 ) 의 부모 노드 ( 삼촌 ) 를 뜻한다. 여기서 레드 - 블랙 트리의 특성이 추가된다 : 특성 3 ( 모든 리프 노드들은 검정색이다 ) 은 언제나 변하지 않는다. 특성 4 ( 적색 노드의 모든 ( 두 ) ( 두 ) 자식은 검정색이다 ) 는 적색 노드의 추가, 검정색 노드의 적색 노드로의 전환, 회전
삭제 ( Removal ) 4. 3 비대칭 경계의 증명 ( Proof of asymtotic bounds ) 4. 4 병렬 알고리즘 ( Parallel algorithms ) 5 각주 용어 [ 편집 ] 레드 - 블랙 트리는 이진 트리의 특수한 형태로서, 컴퓨터 공학 분야에서 숫자 등의 비교 가능한 자료를 정리하는 데 쓰이는 자료구조이다. 이진 트리에서는 각각의 자료는'노드 ( node, 분기점 )'에 저장이 된다. 자료를 트리 구조로 저장할 때, 노드들 중 최상위에 있는 노드를 루트 노드 ( root node ) 라고 부른다. 이진 트리에서 노드는 최대 두 개의 자식 노드를 가질 수 있다. 각각의 자식 노드도 역시 최대 두 개의 자식 노드를 가질 수 있으며, 이런식으로 계속 연결된다. 그러므로, 어떤 트리도 루트 노드로부터 그
덱 리스트 멀티맵 우선순위 큐 큐 집합 멀티셋 분리 집합 스택 배열 비트 배열 환형 배열 동적 배열 해시 테이블 해시드 어레이 트리 희소 배열 ( Sparse array ) 연결형 연관 리스트 연결 리스트 트리 B 트리 이진 탐색 트리 AA AVL 레드 - 블랙 자가 균형 splay 힙 이진 힙 피보나치 R 트리 R * R 힐버트 트리 해시 트리 그래프 이진 결정 다이어그램 자료 구조의 목록 원본 주소 " " 분류 : 트리 구조숨은 분류 : 번역 중인 문서빈 문단이 포함된 문서 둘러보기 메뉴 개인 도구 로그인하지 않음토론기여계정 만들기로그인 이름공간 문서토론 변수 보기 읽기편집역사 보기 더 보기 검색 둘러보기 대문사용자 모임요즘 화제최근 [UNK] 문서 보기임의 문서로도움말기부 도구 여기를 가리키는 문서가리키는 글의 최근 [UNK] 올리기특수 문서 목록고유 링크문
레드-블랙 트리(red-black tree)는 자가 균형 이진 탐색 트리(self-balancing binary search tree)로서, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조다. 1978년 레오 귀바스(Leo J. Guibas)와 로버트 세지윅이 1972년 루돌프 바이어가 창안한 "대칭형 이진 B-트리"를 발전시켜 만들었다. 레드-블랙 트리는 복잡한 자료구조지만, 실 사용에서 효율적이고, 최악의 경우에도 상당히 우수한 실행 시간을 보인다: 트리에 n개의 원소가 있을 때 O(log n)의 시간복잡도로 삽입, 삭제, 검색을 할 수 있다.