[1122] 자바 - 자료구조 (Tree)

# Tree

- Tree의 정의

  ▪ 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료 구조

 

- Tree의 구조, 특징 

  ▪ 맨 처음 데이터의 꼭짓점을 루트(Root)라고 한다.

  ▪ 루트에 여러 개의 데이터를 간선(edge)로 연결하며, 연결된 각 데이터를 노드(Node)라고 한다.

  ▪ 상하 계층으로 연결된 데이터들은 부모/자식 관계를 가진다.

  ▪ 상위 계층의 데이터를 부모 노드(Parent Node), 하위 계층에 있는 데이터들을 자식 노드(Child Node)라고 한다. 

  ▪ 자식이 없는 노드를 리프 노드(Leaf Node)라고 한다.

 

1. 깊이 (Depth)
   트리 구조에서 루트(꼭짓점 노드)로부터 하위 계층의 특정 노드까지의 깊이.
2. 레벨 (Level)
   같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현함. (ex. Depth가 0인 루트 노드의 level은 1, Depth가 1인 노드의 level은 2이다.)
   같은 레벨에 나란히 있는 노드를 형제 노드(Sibling Node)라고 한다.
3. 높이 (Height)
   리프 노드를 기준으로 루트까지의 높이를 말함. 리프 노드를 기준으로 높이가 설정된다. 리프 노드의 높이는 0으로 노드 하나층을 올라갈수록 1만큼 늘어난다.
4. 서브 트리 (Sub tree)
   트루 구조의 root에서 뻗어 나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리.

- Tree의 장점

  ▪ 효과적인 계층 구조 표현
    : 계층 구조를 나타내는 데에 효과적
  ▪ 정렬과 탐색에 활용

    : 이진 탐색 트리, 힙(Heap) 등과 같은 형태로 사용되어, 정렬과 탐색을 위한 알고리즘을 구현하는 데 사용됨.

  ▪ 삽입과 삭제가 용이

    : 노드의 삽입과 삭제가 쉬움. 삽입 및 삭제 시에 대항 노드의 부모와 자식 노드를 수정한다.

  ▪ 구조 파악이 용이

    : 쉽게 시각화 하여, 구조 이해하기에 도움됨

  ▪ 다양한 분야에서 활용

    : 데이터베이스, 알고리즘 등 다양한 분야에서 활용된다. (ex. 컴퓨터의 디렉토리 구조, 회사 조직도 등)