[algorithm] Avl 트리 위에 레드 블랙 트리
AVL 및 레드 블랙 트리는 노드의 레드 및 블랙 색상을 제외하고 모두 자체 균형을 유지합니다. AVL 트리 대신 레드 블랙 트리를 선택하는 주된 이유는 무엇입니까? 레드 블랙 트리의 용도는 무엇입니까?
답변
AVL 트리 대신 레드 블랙 트리를 선택하는 주된 이유는 무엇입니까?
두 빨강 – 검정 나무 와 AVL 나무는 가장 일반적으로 사용되어 균형 이진 검색 나무 와 보장에 그들은 삽입, 삭제 및 룩업을 지원합니다 O(logN) time. 그러나 둘 사이에는 다음과 같은 비교 지점이 있습니다.
- AVL 트리는 더 견고하게 균형을 이루므로 더 빠른 조회를 제공합니다. 따라서 조회 집약적 인 작업의 경우 AVL 트리를 사용합니다.
- 삽입 집약적 인 작업의 경우 Red-Black 트리를 사용하십시오.
- AVL 트리는 각 노드에 균형 요소를 저장합니다.
O(N)추가 공간 이 필요 합니다. 그러나 트리에 삽입 될 키가 항상 0보다 크다는 것을 알고 있다면 키의 부호 비트를 사용하여 빨강-검정 트리의 색상 정보를 저장할 수 있습니다. 따라서 이러한 경우 적-흑색 트리는 추가 공간을 차지하지 않습니다.
레드 블랙 트리의 적용은 무엇입니까?
빨강-검정 나무가 더 일반적인 용도입니다. 추가, 제거 및 조회에서 비교적 잘 수행되지만 AVL 트리는 느린 추가 / 제거 비용으로 더 빠른 조회를 제공합니다. 레드-블랙 트리는 다음에 사용됩니다.
- 자바 :
java.util.TreeMap,java.util.TreeSet - C ++ STL (대부분의 구현에서) : 맵, 멀티 맵, 멀티 세트
- Linux 커널 : 완전히 공정한 스케줄러, linux / rbtree.h
답변
이 기사를 읽어보십시오
차이점, 유사성, 성능 등에 대한 좋은 통찰력을 제공합니다.
다음은 기사의 인용문입니다.
RB- 트리는 AVL 트리와 마찬가지로 자체 균형을 유지합니다. 둘 다 O (log n) 조회 및 삽입 성능을 제공합니다.
차이점은 RB- 트리는 삽입 작업 당 O (1) 회전을 보장한다는 것입니다. 이것이 실제 구현에서 실제로 성능을 저하시키는 것입니다.
단순화 된 RB- 트리는 동적 노드 구조의 오버 헤드를 처리하지 않고 개념적으로 2-3 개의 트리가 됨으로써 이러한 이점을 얻습니다. 물리적으로 RB- 트리는 이진 트리로 구현되고, 빨간색 / 검은 색 플래그는 2-3 개의 동작을 시뮬레이션합니다.
내 자신이 이해하는 한, AVL 트리와 RB 트리는 성능 측면에서 그리 멀지 않습니다. RB 트리는 단순히 B- 트리의 변형이며 밸런싱은 AVL 트리와 다르게 구현됩니다.
답변
성능 차이에 대한 우리의 이해는 수년에 걸쳐 향상되었으며 이제 AVL에 대해 레드-블랙 트리를 사용하는 주된 이유는 아마도 CLRS에서 다루지 않기 때문에 약간 덜 일반적이기 때문에 좋은 AVL 구현에 액세스 할 수 없기 때문입니다.
이제 두 나무 모두 랭크 균형 나무의 형태로 간주 되지만 적-검은 나무는 실제 테스트에서 지속적으로 약 20 % 느립니다 . 또는 순차 데이터가 삽입 될 때 30-40 % 더 느립니다 .
따라서 적-흑 나무를 연구했지만 AVL 나무를 연구하지 않은 사람들은 적-흑 나무를 선택하는 경향이 있습니다. 빨강-검정 나무의 주요 용도는 Wikipedia 항목에 자세히 설명되어 있습니다 .
답변
여기의 다른 답변은 RB 및 AVL 트리의 장단점을 잘 요약하지만이 차이점이 특히 흥미 롭다는 것을 알았습니다.
AVL 트리는 지속적인 상각 업데이트 비용을 지원하지 않습니다. [그러나 빨강-검정 트리는 지원]
출처 : Mehlhorn & Sanders (2008) (섹션 7.4)
RB와 AVL 나무를 모두 보장하면서 그래서, O (로그 (N)) 조회, 삽입 및 삭제의 AVL / RB 속성 복원 최악의 경우 시간 후 노드를 삽입하거나 삭제가 O 수행 할 수 있습니다 (1) 시간을 상각 에 대한 빨강-검정 나무.
답변
프로그래머는 일반적으로 메모리를 동적으로 할당하는 것을 좋아하지 않습니다. avl 트리의 문제는 “n”요소에 대해 트리의 높이를 저장하기 위해 최소한 log2 (log2 (n)) … (height-> log2 (n)) 비트가 필요하다는 것입니다! 따라서 방대한 데이터를 처리 할 때 각 노드에 높이를 저장하기 위해 할당 할 비트 수를 알 수 없습니다.
예를 들어 높이를 저장하기 위해 4 바이트 int (32 비트)를 사용하는 경우. 최대 높이는 2 ^ 32 일 수 있으므로 트리에 저장할 수있는 최대 요소 수는 2 ^ (2 ^ 32)입니다 .– (매우 큰 것처럼 보이지만이 데이터 시대에는 너무 큰 것은 없습니다). 따라서이 제한을 초과하여 촬영하면 높이를 저장하기 위해 더 많은 공간을 동적으로 할당해야합니다.
이것은 저에게 합리적이라고 생각되는 제 대학의 교수가 제안한 대답입니다! 이해가 되길 바랍니다.
편집 : AVL 트리는 Red Black Tree에 비해 균형이 잘 잡혀 있지만 삽입 및 삭제 중에 더 많은 회전이 발생할 수 있습니다. 따라서 애플리케이션에 자주 삽입 및 삭제가 포함되는 경우 Red Black 트리가 선호됩니다. 그리고 삽입과 삭제가 덜 빈번하고 검색이 더 빈번하다면 Red Black Tree보다 AVL 트리를 선호해야합니다. -소스 GEEKSFORGEEKS.ORG
답변
AVL 트리의 재조정은 아래 속성을 충족해야합니다. (위키 참조 -AVL 트리 )
AVL 트리에서 모든 노드의 두 하위 하위 트리 높이는 최대 1만큼 다릅니다. 언제라도 둘 이상 차이가 나는 경우이 속성을 복원하기 위해 재조정이 수행됩니다.
따라서 이것은 AVL 트리의 전체 높이가 미쳐 갈 수 없다는 것을 의미합니다. 즉, AVL 트리에서 조회가 더 좋아질 것입니다. 그리고 높이가 떨어지지 않도록 추가 작업 (회전)을해야하므로 트리 수정 작업에 약간의 비용이들 수 있습니다.
답변
