빨강 - 검정 나무는 어떻게 작동합니까?

Question

붉은 검정 나무 주위에는 많은 질문이 있지만 그 중 누구도 어떻게 작동하는지 대답하지 않습니다. 왜 그것은 적 - 흑인이라고 불 렸을까요? 이렇게하면 나무가 균형을 유지하게됩니다 (따라서 불균형 일반 이진 검색 트리보다 성능이 향상됩니까)? 어떻게 그리고 왜 그것이 작동하는지에 대한 개요를 찾고 있습니다.

Answer 1

검색 및 순회의 경우 이진 트리와 동일합니다.

삽입 및 삭제의 경우 트리가 너무 불균형을 일으키지 않도록보다 정교한 알고리즘이 적용됩니다. 이것들은 모든 단일 항목 연산이 최악의 O (log n) 시간에 항상 실행된다는 것을 보장하지만, 간단한 이진 트리에서는 이진 트리가 너무 불균형 해져서 사실상 연결된 목록이므로 O (n) 최악의 경우 성능을 제공합니다. 각각의 단일 항목 작업.

레드 - 블랙 트리의 기본 아이디어는 노드 당 최대 3 개의 키와 4 개의 자식으로 B- 트리를 모방하는 것입니다. B- 트리 (또는 B + 트리와 같은 변형)는 주로 데이터베이스 인덱스 및 하드 디스크에 저장된 데이터에 사용됩니다.

각 이진 트리 노드에는 빨간색 또는 검은 색 "색상"이 있습니다. 각 검은 노드는 B- 트리 유추에서 해당 B- 트리 노드에 맞는 하위 트리의 하위 트리 루트입니다. 이 노드에 빨간 하위 노드가 있으면 동일한 B-tree 노드의 일부로 간주됩니다. 따라서 (실제로는 이루어지지 않았지만) 빨강 - 검정 트리를 B- 트리로 변환하고 (대부분의) 구조를 보존 할 수 있습니다. 가능한 유일한 예외는 B- 트리 노드에 두 개의 키와 세 개의 자식이있는 경우 해당하는 빨강 - 검정 트리의 검정 노드에서 어떤 키를 선택해야 하는지를 선택할 수 있습니다.

예를 들어 빨강 - 검정 나무의 경우 루트에서 잎까지의 모든 줄에는 같은 수의 검은 색 노드가 있습니다. 이 규칙은 모든 리프 노드가 동일한 깊이에 있다는 B- 트리 규칙에서 파생됩니다.

빨강 - 검정 나무가 파생되는 기본 개념이지만 실제로 삽입 및 삭제에 사용되는 알고리즘은 모든 B- 트리 규칙을 적용하도록 수정됩니다 (사소한 예외가있을 수 있습니다 - 잊어 버렸습니다). 업데이트하지만 바이너리 트리 형식에 맞게 조정됩니다. 즉, 빨간색 - 검정색 트리 삽입 또는 삭제를 수행하면 B- 트리 삽입 또는 삭제를 수행 할 때와 비교하여 예상되는 결과와 다른 구조가 제공 될 수 있습니다.

자세한 내용은 MigDus가 이미 제공 한 Wikipedia link을 따르십시오.

Answer 2

빨강 - 검정 나무는 각 정점이 빨간색 또는 검은 색으로 표시된 순서가 지정된 이진 트리입니다. 직관은 빨간색 꼭지점이 상위과 동일한 높이로 표시되어야한다는 것입니다 (즉, 빨간색 꼭지점의 가장자리는 "내림차순"이 아닌 "가로"로 간주됩니다).

는 [I는 위키 백과의 항목이 분명이 점을하게 생각하지 않습니다.]

레드 - 블랙 트리에 대한 일반적인 규칙은 빨간색 정점 결코 다른 빨간 정점을 가리되지해야합니다. 즉, 검은 꼭지점 (bbb, bbr, rbb, rbr - [왼쪽 자식] [루트] [오른쪽 자식])을 루트로하는 모든 하위 트리에 대해 가능한 버텍스 배열이 234 개의 나무에 해당합니다.

빨강 - 검정 나무를 검색하는 것은 일반 이진 트리를 검색하는 것과 같습니다. 적색 - 검은 색 불변량을 보존하기 위해 어느 지점에서 "수정 (fix-up)"회전이 필요할 수도 있다는 점을 제외하면 삽입 및 삭제는 비슷합니다.

건배!