O (logn) 시간의 이진 검색 트리에서 최소/최대 값을 찾을 수 있습니다. 그러나 C++의 map은 일정 시간 동안 최소/최대 값을줍니다. 지도에서 최소 요소는 map::begin이고 최대 값은 map::rbegin입니다. 이 두 작업은 모두 일정한 시간이 걸립니다. 누구든지 최소 / 최대 O (1)을 찾는 방법을 제안 할 수 있습니까?O (1) 시간의 균형 이진 검색 시간의 최소/최대 요소
C++ map이 BST에 의해 구현되지 않았습니다. Red Black Tree가 구현했습니다. O (1)에 의해 BST에서 최소/최대를 찾고 싶다면 두 개의 포인터를 트리의 가장 왼쪽 노드와 가장 오른쪽 노드에 저장할 수 있습니다. 그렇지 않으면 minheap 또는 maxheap을 사용하여 O (1)에서 최소/최대를 찾을 수 있습니다.
예, 그렇게 할 수 있습니다. 그러나 최소/최대 노드를 삭제하면 포인터가 변경됩니다. 그래도 새로운 최소값/최대 값을 찾으려면 O (logn)이 필요합니다. –
아니요, O (1)에서 다시 수행 할 수 있습니다. 삭제하는 동안 min 노드 (가정)를 삭제하더라도 min 포인터를 inode 후미 노드로 업데이트 할 수 있습니다. 그래서, 언제든지 O (1)에서 분을 얻을 수 있습니다. 삭제시 복잡성이 증가하고 있다고 말할 수 있습니다. 하지만 여전히 O (logn)가됩니다. –
레드 블랙 트리도 그냥 이진 검색 트리입니다. – Exagon
루트와 함께 두 개의 포인터를 더 저장하십시오. – molbdnilo
std :: map은 일반적으로 검색 트리로 구현되므로 해시 맵을 통해 구현 된 std :: unordered_map을 의미합니다. hashmap은 순서를 신경 쓰지 않기 때문에 우리는 O (1)에서 min을 찾을 수 없습니다. 삭제하지 않고 O (1)에서 최소/최대 값을 얻으려는 경우 최소 힙 또는 최대 힙을 사용하는 것이 좋습니다. – Exagon
@Exagon : ordered_map을 의미합니다. map :: rbegin과 map :: begin을 살펴볼 수 있습니다. –