이진 힙 vs 이진 탐색 트리

[joonleesky]

안녕하세요.

책 455쪽에 Heap과 BST에 대한 time complexity analysis가 소개 되어 있는데요, BST에 비한 Heap의 장점은 find maximum value의 시간이 Heap은 O(1), BST는 O(logN)으로 빠르다는 점을 알려주셨습니다.

하지만, BST에서도 단순히 maximum or minimum value를 tracking하고 있으면 O(1) complexity로 조회가 가능하지 않나요? BST에 비해 Heap의 장점은 average insertion complexity가 대부분의 노드가 아래쪽에 있기 때문에 O(1)이라는 점이 아닐까 싶습니다.

감사합니다. ref: https://stackoverflow.com/questions/6147242/heap-vs-binary-search-tree-bst

[likejazz]

안녕하세요.

실무에서는 말씀하신대로 max value를 별도 변수에 보관한다던지 하는 방법으로 O(1)에 조회할 수 있습니다. 그러나 그렇게 하면 그 자료형은 BST가 아니라 BST를 기반으로 하는 어떤 복합 자료형이 되겠죠. 링크해주신 스택오버플로 글도 읽어봤는데요. 거기서도 Balanced BST로 modification을 언급하는 것이지, 책에서 얘기하는 것은 순수 BST의 경우이므로 조금 다른 경우라 할 수 있을거 같아요.

감사합니다.