[자료구조 트리] 트리(Tree)

  트리(Tree)란 실제 트리를 거꾸로 세워 놓은 형태의 자료구조입니다. 노드와 링크로 구성되어 있습니다. 하나의 노드에서 다른 노드로 이동하는 경로가 유일하며, 모든 노드는 서로 연결되어 있습니다.

  배열이나 연결 리스트는 데이터를 일렬로 저장하기 때문에 일반적으로 탐색 연산이 순차적으로 수행되어야 한다는 단점을 가집니다. 트리는 이러한 문제점을 보완하여 다양한 형태로 광범위하게 응용됩니다.

  일반적인 트리(General Tree)는 HTML과 XML의 문서 트리, 자바 클래스 계층구조, 운영체제의 파일 시스템, 탐색 트리, 이항 힙, 피보나치 힙과 같은 우선순위 큐에서도 사용됩니다. 이를 메모리에 저장하려면 각 노드에 키와 자식 수만큼의 레퍼런스를 저장해야 합니다. 따라서 트리 노드의 최대 차수가 k라면, k개의 레퍼런스 필드를 선언해야 합니다.

 

  트리에서의 용어

• 루트(Root): 트리의 최상위에 있는 노드
• 자식(Child): 노드 하위에 연결된 노드
• 차수(Degree): 자식 수
• 부모(Parent): 노드의 상위에 연결된 노드
• 이파리(Leaf): 자식이 없는 노드
• 형제(Sibling): 동일한 부모를 가지는 노드
• 조상(Ancestor): 루트까지 경로상에 있는 모든 노드의 집합
• 후손(Descendant): 노드 아래로 매달린 모든 노드의 집합
• 서브트리(Subtree): 노드 자신과 후손으로 구성된 트리
• 레벨(Level): 레벨 1인 루트를 중심으로 아래로 내려갈 수록 레벨이 1씩 증가하며, 깊이(Depth)와 같음
• 높이(Height): 트리의 최대 레벨
• 키(Key): 탐색에 사용되는 노드에 저장된 정보

 

  ※ "자바와 함께하는 자료구조의 이해"라는 책을 참고하여 쓴 게시글입니다. 책에는 없는 내용을 추가하여 작성된 부분이 있습니다. 문제가 되거나 부정확한 부분이 있다면 알려주시면 감사하겠습니다.

  ※ 책은 게시글보다 정확한 내용을 담고 있으며 코드, 그림, 예제를 이용하여 개념을 자세히 설명합니다.