본문으로 건너뛰기
실습하기

트리(Tree)란?

트리는 계층적인 구조를 가진 자료 구조입니다. 각 노드가 자식 노드를 가리키는 방식으로 구성됩니다.

트리는 데이터의 계층적 구조를 표현하는 데 사용되며, 파일 시스템, 조직도, DOM(Documenet Object Model) 등 다양한 상황에 사용됩니다.


트리 핵심 요소

  1. 노드(Node):

    • 트리의 기본 단위로, 데이터와 다른 노드를 가리키는 참조(주로 자식 노드)를 포함합니다.

    • 예: 파일 시스템에서의 파일이나 폴더, 조직도에서의 직원

  2. 루트 노드(Root Node):

    • 트리 구조의 최상단에 위치하는 노드입니다.

    • 이 노드는 부모가 없으며, 트리의 출발점입니다.

  3. 자식 노드(Child Node):

    • 다른 노드(부모 노드)로부터 파생된 노드입니다.

    • 하나의 부모 노드는 여러 자식 노드를 가질 수 있습니다.

  4. 부모 노드(Parent Node):

    • 하나 이상의 자식 노드를 가지고 있는 노드입니다.
  5. 형제 노드(Sibling Node):

    • 동일한 부모 노드를 공유하는 노드들입니다.
  6. 잎 노드(Leaf Node) / 단말 노드(Terminal Node):

    • 자식 노드가 없는 노드입니다.

    • 트리의 가장 아래쪽에 위치합니다.

  7. 서브트리(Subtree):

    • 트리 내의 노드와 그 자손 노드들로 구성된 트리입니다.
  8. 깊이(Depth):

    • 루트 노드로부터 특정 노드까지의 거리입니다.
  9. 높이(Height):

    • 트리에서 가장 깊은 노드의 깊이입니다.

파이썬 구현

트리를 구현하는 기본적인 방법은 클래스와 객체를 사용하는 것입니다. 각 노드는 객체로 표현되며, 각 객체는 자식 노드에 대한 참조를 포함합니다.

  1. 노드 클래스(Node Class):

    • 데이터와 자식 노드에 대한 참조를 저장합니다.
  2. 트리 생성과 순회:

    • 루트 노드에서 시작하여 필요에 따라 노드를 추가하고, 순회 방법에 따라 트리를 탐색합니다.

트리의 구현은 트리의 종류와 사용 목적에 따라 다양하게 변형될 수 있습니다. 예를 들어, 이진 탐색 트리는 데이터의 삽입, 삭제, 검색에 특화되어 있으며, 균형 트리는 탐색 시간을 최적화하기 위해 사용됩니다.

다음 내용이 궁금하다면?

코드프렌즈 PLUS 멤버십 가입 or 강의를 등록해 주세요!