포인터를 신경 쓰지 않고 균형 이진 검색 트리에서 O (1) 시간을 최소 및 최대로 유지하는 방법은 무엇입니까?

Question

"알고리즘 디자인 매뉴얼"책에 소비세 3-7는 말한다 :

가, 삽입, 삭제, 최소, 최대, 후계자 당신이 작업 검색의 각을 지원하는 균형 잡힌 사전 데이터 구조에 액세스 할 수 있습니다 가정 , O (log n) 시간의 전임자. 삽입 및 삭제 작업을 수정하여 O (log n)을 사용하지만 최소 및 최대 소요 O (1) 시간을 유지하는 방법을 설명하십시오. , 힌트없이

을 (힌트. 추상 사전 작업을 사용하는 대신 포인터 등에 대한 일 처리의 관점에서 생각 )이 질문은 매우 쉽게 생각합니다. 난 그냥 분은 항상 최소를 가리키는 포인터를 유지, 나무에 대한

, 다른 포인터 최대 항상 최대를 가리키는 :

여기 내 솔루션입니다.

x를 삽입 할 때 min.key와 x.key, if min.key > x.key, then min = x;을 비교하고 필요한 경우 max에 대해 이렇게하십시오.

X를 삭제

, if min==x, then min = successor(x); if max==x, then max = predecessor(x);

는하지만 힌트는 내가 포인터 등에 대한 일 처리 수 없다고. 내 솔루션 포인터에 대해 머뭇 거리는가?

추가 점수를 사용할 수없는 경우 최소 및 최대 O (1)은 어떻게받을 수 있습니까?

감사합니다.

Answer 1

를 사용하여 최소/최대 값을 얻기 위해 삭제하고 일정 시간 수 - 당신이 포인터 장난 아니에요 , 당신은 단지 최소/최대 값을 저장하고 있습니다.

그래서, 그냥 :) 더 확신 할 수

Answer 2

나는 최대 및 최소 모두 O (1)을 얻을 수 있다고 생각하지 않습니다.

어쨌든,이 책은 귀하가 직접 binary heaps을 발견하기를 원합니다. 링크를 직접 보지 않으려면 링크를 보지 마십시오. 이 힌트 만 고려하십시오. "트리의 루트에는 항상 최소값이 포함됩니다."(또는 "최대 값"을 O (1)으로 지정하려면 최대 값이 포함됩니다).

Answer 3

당신은/업데이트 (N) 시간 기록을 달성 당신의 대답은 내가 줄 것 같은 하나입니다 Min-Max Heaps

Answer 4

나는 두 이진 힙 사용합니다 : A 최소 및 최대 힙. 각각 하나의 요소를 절반 만 저장하면 O (1) 시간에 최대 및 최소 모두 액세스 할 수 있습니다. 최소 힙에는 가장 작은 요소가있는 절반과 최대 힙에는 더 큰 요소가있는 절반이 들어 있습니다. 삽입/삭제 작업은 모두 여전히 O (로그 n)입니다. 새로운 요소를 삽입 할 때 어떤 힙에 가야하는지 확인하십시오.

Answer 5

최대 값과 최소값의 두 값을 저장하십시오. 이것들은 모든 삭제시에 점검되고 잠재적으로 업데이트 될 필요가 있습니다. 최소값이 삭제되는 경우 후속 호출을 호출하고 최소값을 업데이트하고 이전 항목을 삭제합니다.삽입시, 새로운 항목을 min/max로 비교하십시오. 어느 쪽이든 하나를 최소/최대로 바꾸면