이진 검색 트리/연결된 목록을 사용하여 두 번 끝난 우선 순위 큐 구현

Question

이중 연결 목록과 이진 검색 트리를 모두 사용하여 두 배로 끝나는 우선 순위 큐를 구현해야합니다. O의 최소 및 최대 요소를 얻을 수있는 아이디어 (1) 하나의 작은 요소를 삽입하는 것입니다

주요 기능은 이중 연결리스트를 사용 getMin()와 getMax()

1. 해야한다 목록의 측면과 더 큰 요소가 있지만 요소가 삽입 될 때마다 문제가있을 것입니다. (그러면 O (1)이 아님) 더 좋은 방법이 있습니까? 내가 BST에 getMin()와 getMax()를 구현할 수있을 것입니다 방법을 이해할 수 없었다 : BST를 사용

2. .

Answer 1

보통 우선 순위 큐는 일반적으로 우리가 O에 쉽게 최고 가치를 (1)와 O (logn)에 새로운 요소를 삽입 할 수 있습니다 힙을 사용하여 구현된다. 거기에 같은 asymtoptical 복잡성을 가져 오는 이중 연결된 목록을 사용하여 우선 순위 큐를 구현할 수있는 방법이 의심 스럽지만, 이중 양면 우선 순위 대기열 (나는 잘못 될 수 있음)은 말할 것도 없습니다. 우리가 O에서 두 작업을 할 수있는 BST 사용 (logn) :

• 삽입과 삭제가 평소 BST과 동일
• , 최소 값을 가져 루트에 순회를 시작하고 다음의 제품에 모든 현재 노드에 왼쪽 자식이 없을 때까지 왼쪽으로 이동합니다. 마지막으로 방문한 노드에 최소값이 포함되어 있습니다.
• 최대 값을 얻으려면 루트에서 순회를 시작하고 현재 노드에 올바른 자식이 없어 질 때까지 오른쪽으로 이동하십시오. 방문한 마지막 노드는 최대 값 물론

에게, getMin 및 getMax 것 전용으로 O (logn)이 BST 균형 경우, 그렇지 않으면

Answer 2

(n)이 O에 퇴화 할 수 삽입을 포함 (O (1)이 아닐 것입니다.) 더 좋은 방법이 있습니까?

기본적으로하는 것은 O (1)에서 수행 할 수없는 순서로 첫 번째 큰 요소를 검색하는 것입니다. 선형 검색 (하나씩 요소를 통과하는 것을 의미 함)이 아마도 가장 좋은 방법 일 것입니다. 거대한 목록이 있고 효율성에 초점을 맞추려면 exponential search 또는 interpolation search(보간은 저장된 키의 확률을 알고있는 경우에만 작동)O (loglog (n))보다 가까워 질 수는 없습니다..

BST에서 getMin() 및 getMax()를 구현하는 방법을 이해할 수 없었습니다. 당신이 다음 BST에 분을 얻을 수있는 유일한 방법을 추가 구조를 추가 할 수 없습니다하고 있으며 루카스 Sampaio 이미 언급 한 바와 같이 최대가 통과하는 경우

.

비교는 관련 상당히 비싼하지 않는 한, 연결리스트에 기하 급수적으로 검색 또는 보간 검색을 수행하기 위해 그들에게 무의미한의 빠른