[자료구조] 트리(Tree)

🔻트리(Tree)

 트리(Tree)는 스택이나 큐와는 달리 비선형 자료구조이다. 노드들의 계층적 관계를 표현한다. 또한 트리안에 서브트리가 있고, 그 서브트리 안에또 서브트리가 있는 재귀적 자료구조이다.

 넓게 살펴보면 그래프의 한 종류라고 할 수 있다.

 위 그림처럼 노드들이 마치 나무 가지처럼 연결되어 있어서 트리라는 이름이 붙혀진 것 같다.

트리는 활용되는 범위가 무궁무진하다. 추후에 포스팅할 힙(Heap)도 트리를 이용한 자료구조이고, 용도에 맞게 트리에서 파생된 자료구조나 알고리즘이 많다. 기본적인 트리만 보면 굉장히 간단한 자료구조지만 깊게 파고들면 들수록 어려운 자료구조인 것 같다. 따라서 트리의 기본적인 요소들을 정리해보는 시간을 가지면 이후에 나올 자료구조나 알고리즘을 쉽게 익힐 수 있을 것이다.

 

💡 트리에서 사용되는 용어

◼ 노드(Node)

  ◽ 트리를 구성하는 기본 요소.

  ◽ 노드에는 데이터와 하위 노드에 대한 참조를 가지고 있다. (연결리스트와 유사하다.)

  ◽ 그래프에서 정점과 비슷한 개념이다.

 

◼ 간선(Edge)

  ◽ 노드와 노드를 잇는 선.

 

◼ 루트 노드(Root Node)

  ◽ 부모를 가지고 있지 않은 트리에서 최상위에 위치한 노드.

  ◽ 위 그림에서 A에 해당한다.

 

◼ 부모 노드(Parent Node)

  ◽ 자식을 가진 노드로써, 한 노드에 대해 상위에 있는 노드이다.

  ◽ 위 그림에서 E의 부모 노드는 B이다.

 

◼ 자식 노드(Child Node)

  ◽ 부모 노드의 하위노드.

  ◽ 위 그림에서 B의 자식노드는 E, F이다.

 

◼ 형제 노드(Sibling Node)

  ◽ 같은 부모를 가지는 노드.

  ◽ 위 그림에서 I와 J는 형제 노드이다.

 

◼ 리프 노드(Leaf Node) = 외부 노드(External node) = 단말 노드(Terminal Node)

  ◽ 자식 노드를 가지고 있지 않는 노드.

  ◽ 위 그림에서 E, G, I, J, K, L은 리프 노드이다.

 

◼ 내부 노드(Internal Node)

  ◽ 리프 노드와 반대로 자식을 하나 이상 가진 노드.

  ◽ 위 그림에서 A, B, C, D, F, H는 내부 노드이다.

 

◼ 깊이(depth)

  ◽ 루트 노드에서 해당 노드까지 도달하는데 사용하는 간선의 수.

  ◽ 위 그림에서 G의 깊이는 2이다.

 

◼ 높이(height)

  ◽ 루트 노드에서 리프 노드까지의 거리.

  ◽ 그 중 가장 큰 값이 트리의 높이이다.

  ◽ 위 그림에서 트리의 높이는 4이다.

 

◼ 레벨(Level)

  ◽ 루트를 0으로 하여 아래로 내려갈수록 +1이 된다.(정의에 따라 루트를 level 1으로 하는경우도 있음)

 

◼ 차수(Degree)

  ◽ 노드의 자식 노드의 수

  ◽ 위 그림에서 A의 차수는 3이다.

 

◼ 넓이(Width)

  ◽ 레벨에 있는 노드 수

  ◽ 위 그림에서 Level 1의 넓이는 3이다.

 

 

 

🔻마치며

 이렇게 트리의 기본적인 외형과 용어에 대해서 알아보았고 앞으로 이진트리, 이진탐색트리, 힙, 레드블랙트리와 같은 트리를 이용한 자료구조에 대해 깊이 파고들 예정이다.