CS 자료구조 Tree(트리)

 

트리는 계층적인 데이터를 표현하는 비선형 데이터 구조다. 나무를 거꾸로 뒤집어 놓은 모양과 유사하다. 
트리는 트리 내에 다른 하위 트리가 있고, 하위 트리 안에 또 다른 하위 트리가 있는 재귀적 자료구조다.

 

컴퓨터의 디렉토리 구조가 트리의 대표적인 예가 될 수 있다.

 

ㅇ 트리의 기본 용어

 

출처: https://yoongrammer.tistory.com/68

• 노드(Node)
  트리를 구성하고 있는 기본 요소
  노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있음
  A, B, C, D, E, F, G, H, I, J

 

• 간선(Edge)
  노드와 노드 간의 연결 선

 

• 루트 노드(Root Node)
  트리 구조에서 부모가 없는 최상위 노드
  A

 

• 부모 노드(Parent Node)
  자식 노드를 가진 노드
  H, I의 부모 노드 D

 

• 자식 노드(Child Node)
  부모 노드의 하위 노드
  D의 자식 노드 H, I

 

• 형제 노드(Sibling Node)
  같은 부모를 가지는 노드
  형제 노드 H, I

 

• 외부 노드(external node, outer node), 단말 노드 (terminal node), 리프 노드(leaf node)
  자식 노드가 없는 노드
  H, I, J, F, G

 

• 내부 노드 (internal node, inner node), 비 단말 노드 (non-terminal node), 가지 노드 (branch node)
  자식를 하나 이상 가진 노드
  A, B, C, D, E

 

• 깊이 (depth)
  루트에서 해당 노드까지의 간선 수
  루트 노드의 깊이는 0
  D의 깊이는 2

 

• 높이 (height)
  해당 노드에서 리프 노드까지 가장 긴 경로의 간선 수
  리프 노드의 높이는 0
  A 노드의 높이는 3

 

• Level
  루트에서 어떤 노드까지의 간선 수

 

• Degree
  노드의 자식 수
  리프노드의 Degree : 0 
  A의 Degree : 2

 

• Path
  한 노드에서 다른 한 노드에 이르는 길 사이에 놓여있는 노드들의 순서
  A ~ H 의 경로 A-B-D-H

 

• Path Length
  해당 경로에 있는 총 노드 수
  A ~ H : 4

 

• Size
  자신을 포함한 자손의 노드 수
  B의 size : 6

 

• Width
  레벨에 있는 노드 수
  Level 2 width : 4

 

• Breadth
  리프 노드의 수
  Breadth : 5

 

• Distance
  두 노드 사이의 최단 경로에 있는 간선 수
  D ~ J distance : 3

 

• Order
  부모 노드가 가질 수 있는 최대 자식의 수
  Order 3 = 부모가 최대 3명의 자식을 가질 수 있다.

 

ㅇ 트리의 특징

• 하나의 루트 노드와 0개 이상의 하위 트리로 구성되어 있다.
• 데이터를 순차적으로 저장하지 않기 때문에 비선형 구조다.
• 트리내에 또 다른 트리가 있는 재귀적 자료 구조다.
• 단순 순환을 갖지 않은 무방향 그래프 구조다.
• 노드 간 부모 자식 관계를 가지고 있는 계층형 자료구조, 자식 노드는 하나의 부모만 갖는다.
• 노드가 n개인 트리는 항상 n - 1의 간선을 가진다.

 

ㅇ 트리의 종류

• 편향 트리
  모든 노드들이 자식을 하나만 가진 트리
• 이진트리
  각 노드의 자식노드가 2이하인 트리
• 이진 탐색 트리
  순서화된 이진 트리
  노드의 왼쪽 자식은 부모값 보다 작은 값을, 오른쪽은 큰 값을 가진다.
• m원 탐색 트리
  최대 m개의 서브 트리를 갖는 탐색 트리
  이진 탐색 트리의 확장된 형태로 높이를 줄이기 위해 사용함
• 균형 트리
  m원 탐색 트리에서 높이 균형을 유지하는 트리