인프런 커뮤니티 질문&답변

안녕하세요 ㅎㅎ

 예를 들어 참조의 경우 루트노드에 대한 접근이 O(1)이라는 말씀이실까요??자식노드에 대한 접근까지 내려가면 O(logn)이거나 O(n)일거 같은데.. 아니면 제가 참조와 탐색에 대한 개념을 잘못 잡고 있는것일까요.. 

>> 네 맞습니다.

힙의 경우 맨 위쪽 노드 - 루트노드만 참조가 가능합니다. 아래노드까지 참조에 대한 인터페이스 자체가 없습니다. 그리고 맨 위쪽 노드만 참조했을 때의 시간복잡도가 O(1)이기 때문에 O(1)의 시간복잡도를 가진다고 보시면 됩니다.

힙을 통해서 탐색하는 경우는 없습니다. 힙이란 가장 높은 또는 낮은 요소가 맨 위쪽으로 참조가 가능하도록 자동 정렬된 트리라고 보시면 됩니다.

이부분과 착각 하시는것 같아 예를 들면요.

예를 들어 BST 같은 경우 참조가 아니라 탐색위주로 보시면 됩니다. BST는 모든 노드에 대한 참조가 가능합니다. 힙처럼 루트노드만이 아니구요. ㅎㅎ

다만 이 BST는 가장 낮은 요소 또는 높은 요소가 맨 상단에 위치해 있지 않습니다. 그저 왼, 오로 정렬만 되어있을 뿐이죠. 만약 가장 낮은 요소 또는 높은 요소를 찾으려면 탐색을 통해 가장 아래노드까지 찾아가야 하는 자료구조입니다. 이부분이 서로 다릅니다.

이진트리로 구성된 Map이나 Set의 참조 시간복잡도가 O(logn)인데조금 다른 트리긴 해도 Heap의 참조 시간복잡도가 O(1)인게 이해가 안되는데Heap의 참조와 탐색 시간복잡도에 대해서조금 더 자세히 설명해 주실수 있으신지 해서 질문 드립니다. 예를 들어 참조의 경우 루트노드에 대한 접근이 O(1)이라는 말씀이실까요??자식노드에 대한 접근까지 내려가면 O(logn)이거나 O(n)일거 같은데.. 아니면 제가 참조와 탐색에 대한 개념을 잘못 잡고 있는것일까요..