TechCodeview

내용을 이해하기 전에 레드-블랙 트리와 AVL 트리 차이점이 있으므로 Red-Black 트리와 AVL 트리에 대해 별도로 알아야 합니다.

자바 지도

레드-블랙 트리란 무엇입니까?

레드-블랙 트리는 자기 균형 트리입니다. 이진 검색 트리 각 노드에는 노드의 색상을 나타내는 하나의 추가 정보 비트가 포함됩니다. 노드의 색상은 노드에 저장된 비트 정보에 따라 빨간색 또는 검은색이 될 수 있습니다.

속성

다음은 레드-블랙 트리와 관련된 속성입니다.

• 트리의 루트 노드는 검정색이어야 합니다.
• 레드 노드는 블랙 자식만 가질 수 있습니다. 또는 인접한 두 노드가 빨간색일 수 없다고 말할 수 있습니다.
• 노드에 왼쪽 또는 오른쪽 자식이 없으면 해당 노드를 리프 노드라고 합니다. 그래서 우리는 왼쪽과 오른쪽 자식을 다음과 같은 리프 노드 아래에 배치합니다. 무

리프 노드의 블랙 깊이 또는 블랙 높이는 리프 노드에서 루트 노드로 이동할 때 만나는 블랙의 수로 정의할 수 있습니다. 레드-블랙 트리의 주요 속성 중 하나는 모든 리프 노드가 동일한 블랙 깊이를 가져야 한다는 것입니다.

예를 통해 이 속성을 이해해 보겠습니다.

위의 트리에는 5개의 노드가 있는데, 그 중 하나는 Red이고 다른 4개의 노드는 Black입니다. 위 트리에는 세 개의 리프 노드가 있습니다. 이제 각 리프 노드의 블랙 깊이를 계산합니다. 우리가 관찰할 수 있듯이 세 리프 노드 모두의 검은색 깊이는 2입니다. 그러므로 그것은 레드-블랙 트리이다.

트리가 위의 세 가지 속성 중 어느 하나도 따르지 않으면 레드-블랙 트리가 아닙니다.

레드-블랙 트리의 높이

자바 while 루프

h를 n개의 노드를 갖는 트리의 높이로 간주합니다. n의 가장 작은 값은 무엇입니까? n의 값은 모든 노드가 검은색일 때 가장 작습니다. 트리에 모든 검정색 노드가 포함되어 있으면 트리는 완전한 이진 트리가 됩니다. 완전한 이진 트리의 높이가 h이면 트리의 노드 수는 다음과 같습니다.

n = 2h -1

n의 가장 큰 값은 무엇입니까?

n의 값은 모든 검정색 노드가 두 개의 빨간색 자식을 가질 때 가장 크지만, 빨간색 노드는 빨간색 자식을 가질 수 없으므로 검정색 자식을 갖게 됩니다. 이런 식으로 검은색 자식과 빨간색 자식이 번갈아 가며 존재하게 됩니다. 따라서 검은색 레이어의 개수가 h이면 빨간색 레이어의 개수도 h입니다. 따라서 트리의 전체 높이는 2h가 됩니다. 총 노드 수는 다음과 같습니다.

n = 2*2h-1

AVL 트리란 무엇입니까?

안 AVL 트리 이진 검색 트리와 균형 트리인 아래 사례를 관찰하면 자체 균형 이진 검색 트리입니다.

오라클 테이블 생성

위의 트리에서 요소 검색에 대한 최악의 시간 복잡도는 O(h), 즉 트리의 높이입니다. 위의 경우 17개 요소를 검색하기 위한 비교 횟수는 4회이고, 트리 높이도 4회이다.

아래와 같이 왜곡된 이진 트리를 고려하면:

위의 오른쪽 치우친 트리에서 17개의 요소를 검색하기 위해 수행된 비교 횟수는 5이고, 트리에 존재하는 요소의 수도 5입니다. 따라서 트리가 치우친 이진 트리라면 시간 복잡도는 다음과 같습니다. O(n)이 됩니다.

이제 우리는 시간 복잡도가 O(h)가 되도록 왜곡된 트리의 균형을 맞춰야 합니다. 이라는 용어가 있습니다. 균형 요소 , 이진 검색 트리의 자체 균형을 맞추는 데 사용됩니다. 균형 요소는 다음과 같이 계산할 수 있습니다.

균형 요소의 값은 1, 0 또는 -1일 수 있습니다. 이진 트리의 각 노드가 1, 0 또는 -1의 값을 갖는 경우 해당 트리는 균형 트리라고 합니다. 이진 트리 또는 AVL 트리.

각 노드의 균형 인자가 0이면 트리는 완벽하게 균형 잡힌 트리로 알려져 있습니다. AVL 트리는 트리의 각 노드가 1, 0 또는 -1의 균형 인자 값을 갖기 때문에 거의 균형 잡힌 트리입니다.

레드-블랙 트리와 AVL 트리의 차이점

Red-Black 트리와 AVL 트리의 차이점은 다음과 같습니다.

날짜를 문자열로 변환

이진 검색 트리

Red-Black 트리는 이진 검색 트리이고, AVL 트리도 이진 검색 트리입니다.

규칙

레드-블랙 트리에는 다음 규칙이 적용됩니다.

1. 레드-블랙 트리의 노드는 색상이 빨간색이거나 검은색입니다.
2. 루트 노드의 색상은 검정색이어야 합니다.
3. 인접한 노드는 빨간색이 아니어야 합니다. 즉, 레드 노드는 레드 자식을 가질 수 없지만, 블랙 노드는 블랙 자식을 가질 수 있다고 말할 수 있습니다.
4. 모든 경로에는 동일한 수의 블랙 노드가 있어야 합니다. 그러면 오직 하나의 트리만이 레드-블랙 트리로 간주될 수 있습니다.
5. 외부 노드는 항상 검은색인 nil 노드입니다.

AVL 트리의 규칙:

모든 노드의 균형 요소는 -1, 0 또는 1이어야 합니다.

예

위 그림에서 우리는 트리가 Red-Black 트리인지 아닌지를 확인해야 합니다. 이를 확인하기 위해서는 먼저 트리가 이진 탐색 트리인지 아닌지를 확인해야 합니다. 위 그림에서 볼 수 있듯이 이진 검색 트리의 모든 속성을 만족합니다. 따라서 이진 검색 트리입니다. 둘째, 위의 규칙을 만족하는지 여부를 확인해야 합니다. 위의 트리는 위의 5가지 규칙을 모두 만족합니다. 따라서 위의 트리는 Red-Black 트리라고 결론을 내립니다.

위 그림에서 트리가 AVL 트리인지 여부를 확인해야 합니다. 각 노드에는 -1, 0 또는 1의 균형 요소 값이 있으므로 AVL 트리입니다.

어떻게 나무가 균형 잡힌 나무로 간주될 수 있습니까?

Red-Black 트리의 경우 위의 규칙을 모두 만족하고 트리가 이진 검색 트리인 경우 해당 트리를 Red-black 트리라고 합니다.

AVL 트리의 경우 균형 요소가 -1, 0 또는 1이면 위 트리를 AVL 트리라고 합니다.

균형을 맞추는 데 사용되는 도구

트리의 균형이 맞지 않으면 Red-Black 트리에서 트리 균형을 맞추기 위해 두 가지 도구가 사용됩니다.

다시 칠하기 회전

트리의 균형이 맞지 않으면 AVL 트리에서 트리 균형을 맞추기 위해 하나의 도구가 사용됩니다.

마지막 커밋 실행 취소

회전

어떤 작업에 효율적인가요?

Red-Black 트리의 경우 삽입 및 삭제 작업이 효율적입니다. 다시 칠하기를 통해 트리의 균형이 맞춰지면 Red-Black 트리에서는 삽입 및 삭제 작업이 효율적입니다.

AVL 트리의 경우 트리 균형을 맞추는 데 하나의 도구만 필요하므로 검색 작업이 효율적입니다.

시간 복잡도

Red-Black 트리의 경우 삽입, 삭제, 검색 등 모든 연산의 시간복잡도는 O(logn)이다.

AVL 트리의 경우 삽입, 삭제, 검색 등 모든 연산의 시간복잡도는 O(logn)이다.

표 형식의 차이점을 이해해 봅시다.