Programming/C DataStructure

Tree - 트리 구조 개념

양디 2016. 1. 17. 17:47




트리 구조란?

여태 배운 Stack, Queue, Linked List는 전부 선형 구조였다.


1 : 1로 노드가 연결되어 있는 구조라는 뜻이다.


트리 구조는 처음으로 비선형 구조, 1 : 多 데이터구조 이다.


트리라는 이름에서 알 수 있듯이 나무를 생각하면 이해하기가 편하다.

뿌리는 하나에, 수많은 가지가 나 있는 것을 상상해보자.


트리 구조는 우리가 일상 생활에서 매우 많이 접하고 있다.


계층 이 있는 부분이 바로 트리 구조라고 할 수 있다.


우리가 내컴퓨터 에 들어가면 볼 수 있는 디렉토리의 구조들도 트리 구조이다. 

 


혹은 회사에서 직속 상관과 부하 직원의 관계 또한 트리이다.


트리가 트리이기 위해선 한가지 제한 조건이 있다.


부모 노드는 단 하나여야 한다는 것.


1 : 多 구조 이지 , 多 : 多 구조가 아니기 때문이다 ! 꼭 기억해야 한다.


Tree 구성 요소

트리 구성 요소는 각각 고유한 성질에 따라 다르게 불린다.


여태 스택, 큐, 연결리스트 에서 써왔듯이 하나하나의 대상은 Node 인 것은 동일하다.


그러나 가장 처음에 나오는 Node 는 Root Node 라고 한다.


Node의 바로 아래 연결되어 있는 Node를 자식 노드 , 바로 위에 연결되어 있는 Node를 부모 노드 라고 한다.

또 같은 레벨의 노드를 형제 노드 라고 한다.


또 자식 노드 가 없는 노드를 잎 노드 (Leaf Node) 혹은 단말 노드 라고 한다.


방금 레벨이라는 단어를 썼는데, 이는 노드가 존재하는 층을 의미하고 루트 노드 노드는 레벨 0 이다.

루트 노드의 자식 노드들은 레벨 1, 그 노드들의 자식은 레벨 2 이런 식으로 이해할 수 있다.


Root 에서부터 가장 레벨이 큰 노드까지의 거리를 트리의 Height 혹은 Depth 라고 한다.


Degree 는 해당 노드가 갖고 있는 자식 노드의 개수이고,


트리의 Degree 는 가장 자식이 많은 노드의 Degree 가 된다.


트리의 노드 중 하나의 자식 노드와 그 아래의 노드들을 통째로 자르면 그것 또한 트리가 되는데, 이를 서브 트리 Sub Tree 라고 한다.


트리


출처 : http://www.stoimen.com/blog/wp-content/uploads/2012/06/2.-A-tree.png


위와 같은 구조가 트리 구조이다.


Root 노드는 a 이고, a의 자식 노드는 b와 c 이다.


레벨 2의 노드들은 d, 3, 9 , g 이다.


leaf node 는 각각 1, 2, 5, d, 4, f, j, m, g 이다.


좌측 d 아래의 3에서 노드를 뗴어내면 


3 - 5

  - d      모양의 서브 트리가 나온다.


레벨 1에서 우측 C의 차수는 3이며,


트리 전체의 차수는 최대 차수이므로 레벨 2 좌측 d 의 4가 최대 차수가 된다.


다음 시간에는 직접 구현해보자.





댓글