C++의 이진 힙과 이진 검색 트리

C++ 프로그래밍에서 이진 힙과 이진 검색 트리는 일반적으로 사용되는 두 가지 데이터 구조로 유사점이 있지만 차이점도 있습니다. 이 기사에서는 이진 힙 및 이진 검색 트리의 개념, 기본 작업 및 응용 시나리오를 각각 소개합니다.

1. 이진 힙

1.1 개념

이진 힙은 다음 두 가지 속성을 만족하는 완전한 이진 트리입니다.

1.1.1 힙 순서

힙 순서는 이진 힙에서 각각의 값 노드는 상위 노드의 값보다 크거나 작지 않습니다. 여기서는 최대 힙을 예로 들어 보겠습니다. 즉, 루트 노드의 값은 전체 트리에서 가장 큰 값이고 모든 하위 노드의 값은 루트 노드의 값보다 작거나 같습니다.

1.1.2 완전한 이진 트리 속성

최하위 레이어를 제외하고 다른 모든 레이어는 채워져야 하며 모든 노드는 왼쪽에 정렬되어야 합니다.

여기서 다음 배열은 최대 힙을 나타내는 데 사용됩니다.

[ 16, 14, 10, 8, 7, 9, 3, 2, 4 , 1 ]

해당 힙은 아래와 같습니다.

16

/
14 10
/ /
8 7 9 3
/
2 4

1

1.2 기본 작업

1.2.1 삽입 작업

"을 사용하여 바이너리 힙에 새 요소를 삽입하는 작업"을 사용하여 조정 "sift up" 방법:

• 새 요소를 힙 하단의 가장 왼쪽 빈 공간에 삽입합니다.
• 새 요소의 값이 상위 노드보다 큰 경우 새 요소를 상위 노드와 비교합니다. 그런 다음 두 요소의 위치를 ​​바꾸고 새 요소가 더 이상 상위 노드보다 크지 않거나 힙의 맨 위에 도달할 때까지 이 프로세스를 반복합니다.

1.2.2 삭제 작업

이진 힙에서 힙의 최상위 요소를 삭제하는 작업은 "sift down" 방법을 사용하여 조정됩니다.

• 힙의 최상위 요소와 힙의 가장 오른쪽 요소 힙의 맨 아래 요소가 조정되었습니다.
• 힙의 원래 맨 위 요소를 삭제합니다.
• 해당 값이 자식 노드의 최대 값보다 작은 경우 힙의 새 맨 위 요소를 계층별로 비교합니다. 노드의 최대값과 비교하여 값을 교환하고 힙 순서가 만족될 때까지 이 과정을 반복합니다.

1.3 애플리케이션 시나리오

이진 힙은 힙 정렬, topK 문제 등과 같은 우선 순위 큐 및 힙 기반 정렬 알고리즘을 구현하는 데 자주 사용됩니다.

2. 이진 검색 트리

2.1 개념

이진 검색 트리(BST)는 다음 속성을 만족하는 순서 트리입니다.

2.1.1 왼쪽 하위 트리에 있는 모든 노드의 값은 같습니다. 루트 노드의 값.

2.1.2 오른쪽 하위 트리에 있는 모든 노드의 값은 해당 루트 노드의 값보다 큽니다.

2.1.3 왼쪽과 오른쪽 하위 트리도 각각 이진 검색 트리입니다.

다음 트리를 예로 들어 보겠습니다.

    6
  /   
 2     7

/
1 4 9

   /    /
  3   5 8

그러면 이진 검색 트리입니다.

2.2 기본 작업

2.2.1 검색 작업

이진 검색 트리에서 노드를 찾는 작업의 본질은 찾고자 하는 노드 값의 크기를 현재 노드 값과 지속적으로 비교하여 따라가는 것입니다. 왼쪽/오른쪽 하위 트리 재귀 검색.

2.2.2 삽입 작업

이진 검색 트리에 새 노드를 삽입하는 작업은 루트 노드부터 비교를 시작하여 삽입해야 할 위치를 찾는 작업이 필요하며, 이진 검색 트리의 속성은 다음과 같습니다. 만족하다.

2.2.3 삭제 작업

이진 검색 트리에서 노드를 삭제하는 작업은 세 가지 상황으로 나눌 수 있습니다.

• 삭제할 노드가 리프 노드이므로 직접 삭제하면 됩니다. one node to delete
• 삭제할 노드에 두 개의 자식 노드가 있는 경우 해당 노드를 해당 노드의 오른쪽 하위 트리에서 가장 작은 노드로 교체하고 해당 노드의 오른쪽 하위 트리에서 가장 작은 노드를 삭제합니다.
• 2.3 응용 시나리오

이진 검색 트리는 사전 및 기호 테이블과 같은 검색 및 삽입 작업이 포함된 시나리오를 구현하는 데 자주 사용됩니다. 검색 성능은 데이터 분포와 관련이 있습니다.

3. 이진 힙과 이진 검색 트리의 비교

3.1 유사점

이진 힙과 이진 검색 트리는 모두 이진 트리이며 일부 동일한 속성을 갖습니다.

루트 노드의 초기 위치는 다음과 같습니다.

• 모든 노드를 사용하여 우선순위 대기열을 구현할 수 있습니다.
• 삽입과 삭제의 시간 복잡도는 O(logn)입니다.
• 3.2 차이점

이진 힙과 이진 검색 트리 사이에는 몇 가지 명백한 차이점도 있습니다.

3.2.1 데이터 배포

이진 힙에서는 요소가 규칙성 없이 노드 간에 배포됩니다. 이진 검색 트리에서 각 노드가 힙 순서를 충족하는지 확인하기 위해 요소의 크기에는 특정 정렬 규칙이 있습니다. 즉, 작은 왼쪽과 큰 오른쪽의 속성을 충족합니다.

3.2.2 최소값/최대값 접근

바이너리 힙에서는 O(1) 시간, 즉 루트 노드에서 얻을 수 있는 최대값/최소값에 접근할 수 있지만, 다른 값에 접근하는 시간 복잡도 요소는 O(logn)입니다. 이진 검색 트리에서 최소/최대 값을 찾으려면 하위 트리를 순회해야 하며 시간 복잡도도 O(logn)입니다.

3.2.3 삭제 및 삽입 작업

이진 힙에서 각 삭제 및 삽입 작업은 힙 순서, 즉 이진 검색 트리에서 O(logn)의 시간 복잡도를 따라야 합니다. 노드를 삽입하고 새 노드를 삽입하는 것은 트리의 높이와 관련이 있으므로 최악의 경우 O(n) 시간 복잡도가 필요할 수 있습니다.

3.3 선택 제안

이진 힙과 이진 검색 트리를 선택할 때는 응용 시나리오의 특정 조건에 따라 선택해야 합니다.

최소/최대 값을 빠르게 가져와야 하고 요소 크기에 대한 특별한 요구 사항이 없는 경우 바이너리 힙에 우선 순위를 부여할 수 있습니다.

요소를 빠르게 삽입/삭제해야 하고 요소의 크기를 특정 순서로 정렬해야 하는 경우 이진 검색 트리 선택을 고려해 볼 수 있습니다.

IV. 결론

요약하자면, 이진 힙과 이진 검색 트리는 모두 중요한 데이터 구조이며 다양한 시나리오에서 고유한 장점과 단점이 있습니다. 이진 힙 및 이진 검색 트리의 개념, 기본 작업 및 응용 시나리오를 이해하는 것은 효율적인 프로그램을 작성하는 데 매우 중요합니다.

위 내용은 C++의 이진 힙과 이진 검색 트리의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!