알고리즘에서 사용되는 바이너리 힙 및 이진 검색 트리 - 더미

특별한 종류의 트리 구조는 바이너리 힙 ()으로 각 노드 요소를 특별한 순서로 배치합니다. 검색 트리를 사용하여 데이터를 빠르게 찾을 수 있습니다. 데이터 항목을 가져 와서 트리에 정렬 된 순서로 배치 한 다음 해당 트리를 검색하는 것이 정보를 찾는 더 빠른 방법 중 하나입니다.

바이너리 힙에서 루트 노드는 항상 가장 작은 값을 포함합니다. 브랜치를 볼 때 상위 레벨 브랜치는 항상 하위 브랜치와 브랜치보다 작은 값을가집니다. 그 효과는 검색이 매우 효율적으로되도록 균형 잡힌 예측 가능한 순서로 나무를 유지하는 것입니다. 비용은 나무 균형을 유지하는 것입니다.

응용 프로그램에서 수행하는 모든 작업 중에서 검색은 시간이 많이 걸리고 가장 많이 요구되는 작업입니다. 데이터를 추가하고 나중에 정렬하는 데 약간의 시간이 걸리지 만 데이터 집합을 만들고 유지하는 이점은 데이터 집합을 사용하여 유용한 작업을 수행하는 것에서 비롯됩니다. 이는 중요한 정보를 검색하는 것을 의미합니다. 결과적으로 CRUD 기능의 효율성이 떨어지거나 정렬 루틴이 적합하지 않은 경우도있을 수 있지만 가능한 한 효율적으로 검색을 진행해야합니다. 유일한 문제는 절대적인 효율성으로 모든 작업을 수행하는 검색이 없으므로 검색 루틴의 일부로 수행 할 것으로 예상되는 것을 기준으로 옵션을 평가해야한다는 것입니다.

BST를 사용할 때의 키 배열.

키가 작은 숫자가 왼쪽에 나타나고 큰 숫자가 오른쪽에 나타나는 순서를 따르는 것에 유의하십시오. 루트 노드에는 키 범위의 중간에있는 값이 들어있어 BST가 키를 저장하는 데 쉽게 이해할 수있는 균형 잡힌 접근 방식을 제공합니다. 이 배열을 여기에 표시된 바이너리 힙과 대조하십시오.

바이너리 힙을 사용할 때 키 배열.

각 레벨은 이전 레벨보다 작은 값을 포함하고 루트는 트리의 최대 키 값을 포함합니다. 또한이 특별한 경우에는 왼쪽에 작은 값이 표시되고 오른쪽에 큰 값이 표시됩니다 (이 순서는 엄격하게 적용되지는 않지만). 그림은 실제로

바이너리 최대 힙을 묘사합니다. 루트가 가장 낮은 키 값을 포함하고 각 레벨이 더 높은 값으로 빌드되고 가장 높은 값이 리프의 일부로 나타나는 2 진 최소 힙 을 작성할 수도 있습니다. 앞서 언급했듯이 BST는 검색을 수행 할 때 바이너리 힙보다 몇 가지 장점이 있습니다. 다음 목록은 이러한 장점에 대한 몇 가지 주요 내용을 제공합니다. 요소 검색은 O (log n) 시간이 필요하며 이진 힙의 O (n) 시간과 대조됩니다.

요소를 순서대로 인쇄하려면 O (log n) 시간 만 필요하며 이진 힙의 경우 O (n log n) 시간과 대조됩니다.

• 바닥과 천장을 찾으려면 O (log n) 시간이 필요합니다.
• K 번째 가장 작은 / 가장 큰 요소를 찾으려면 트리가 올바르게 구성되어있을 때 O (log n) 시간이 필요합니다.
• 시간이 중요한지 여부는 신청서에 따라 다릅니다. BST는 검색에 더 많은 시간을 보내고 트리를 만드는 데 드는 시간을 줄이는 데 가장 적합합니다. 바이너리 힙은 키가 규칙적으로 변경되는 동적 상황에서 가장 잘 작동하는 경향이 있습니다. 바이너리 힙은 다음 목록에서 설명하는 것처럼 이점을 제공합니다.
• 바이너리 힙은 배열에 의존하기 때문에 필요한 구조를 만드는 데 필요한 리소스가 더 적습니다.

바이너리 힙을 구축하려면 O (n) 시간이 필요하며 BST와는 대조적으로 O (n log n) 시간이 필요합니다.

• 포인터를 사용하여 트리를 구현할 필요가 없습니다.
• 바이너리 힙 변형 (예: 피보나치 힙)은 O (1) 시간의 키 시간을 늘리거나 줄이는 것과 같은 이점을 제공합니다.