더북(TheBook)

3.5 |

 

(heap)은 컨테이너가 아니라 데이터를 구성하는 방식을 말한다. 힙은 매우 다양한 곳에 쓰이기 때문에 중요하다. 힙이 무엇인지 이해하려면 우선 트리(tree)가 무엇인지 알아야 한다. 따라서 여기서는 트리 데이터 구조가 의미하는 게 무엇인지부터 설명하겠다.

트리는 원소나 노드를 계층 구조로 나열한 것이다. 각 노드에는 키가 있고, 키는 노드에 저장된 객체를 말한다. 노드는 연결 리스트의 노드라고 생각하면 된다. 부모 노드는 하나 이상의 자식 노드를 갖는 노드를 말한다. 일반적으로 부모 노드는 자식 노드를 얼마든지 가질 수 있고, 트리에서 부모 노드가 갖는 자식 노드의 수가 같을 필요는 없다. 자식 노드가 없는 노드를 잎 노드(leaf)라고 부른다. 부모 노드의 키와 자식 노드의 키들 사이에 일정한 관계를 갖는다. 트리는 트리의 기반이 되는 루트 노드가 있고, 루트 노드에서 모든 자식 노드에 도달할 수 있다.

▲ 그림 3-4 이진 트리의 예

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.