단순한 배열을 트리로 간주하여(a[i]의 자식이 a[2i], a[2i+1]) 짜면 코딩 속도도, 실제 구현도 빠를 가능성이 높습니다.
동적 할당이 필요 없고, 참조 연산도 덜 필요하며, cache의 spatial locality 때문에 cache hit의 가능성이 높기 때문입니다.
단점은 명확합니다. 확장성이 별로 없습니다. 가독성 및 의미전달 정도도 좋지 않을 것입니다.
구조체로 각 노드를 구현하면 그 반대입니다. 짜는 것도 실행속도도 좀 느리겠지만 확장성이 있고 가독성 및 의미 부여가 더 잘 될 것입니다.
배열을 완전 이진 트리로 간주하고 코딩하는 방법이 문제 풀이(problem solving)에서는 훨씬 더 편할 것으로 생각됩니다. 여긴 빠르게 짜고 빠르게 돌아가면 되기 떄문입니다.
추가로 C++의 STL에는 우선순위 큐가 std::priority_queue로 구현되어 있습니다.
cdt416z 4년 전
학교에서 배운 자료구조론 책에선 완전 이진 트리를
typedef struct node *treePointer;
typedef struct{
int data;
treePointer leftChild, rightChild;
}
이렇게 정의 해놨는데요
단순한 배열을 트리처럼 취급해서 하는 것과 구조체를 사용하여 만든 트리의
속도 차이나 크기의 한계, 장단점이나 차이점이 궁금합니다.
우선순위 큐를 이번에 써보려고 하는데 어떤 방식이 더 나은지 모르겠어서 질문 드립니다