자료구조(16) - 트리 ( Tree )
- 트리 ( Tree )
: 그래프 중에서 사이클을 포함하지 않는 연결 그래프로서 임의의 노드에서 다른 노드로의
경로가 하나 밖에 없는 것. ( 계층적인 구조로 상위에서 하위로만 가는 구조인듯 하다. 안그러면
그림이 설명이 되지 않는다. )
: 노드중에는 단 하나의 루트 노드가 존재( / )하고 루트 노드에서 다른 하위 노드들이
간선으로 연결된 비선형 구조의 계층 구조이다.
: 트리의 종류로는
: 이진 트리, 포화 이진 트리, 완전 이진 트리, 방향(편향) 트리 등이 있다.
: 트리의 응용 분야로는
: 계층적인 조직이나 디렉토리 구조 및 인공지능에서 인간의 의사결정 구조를 표현하는 결정 트리를 표현하는 데 이용된다.
- 용어
: 트리 ( Tree )
: 상기의 전체를 트리라 한다.
: 노드 ( node ) 와 차수 ( dgree )
: 노드는 데이터와 링크를 통합적으로 표현.
: 노드의 차수는 한 노드가 가지고있는 서브 트리의 수를 말하며 노드 A의 차수는 3이고,
노드 B의 차수는 2가 된다.
: 단말 노드와 비 단말 노드
: 단말 노드는 차수가 0인 노드. 리프( leaf )노드, 터미널 ( terminal ) 노드라고도 함.
: 단말노드는 E, J, K, C, L , H, I가 해당된다.
: 비단말노드는 차수가 1 이상인 노드
: 비단말노드는 A, B, F, D, G가 해당된다.
: 부모 노드와 자식노드
: 노드의 부모노드는 어떤 하나의 노드에 대하여 상위에 연결된 노드를 말하며
자식노드는 어떤 노드에 대하여 하위에 연결된 노드를 의미.
같은 부모를 가지는 노드를 형제 노드라고 한다.
: 트리의 차수
: 트리에 있는 노드의 최대 차수를 칭한다.
: 트리 T의 차수는 A와 D의 차수가 3으로 T의 차수도 3이다.
: 노드의 레벨
: 노드의 레벨은 루트 노드가 레벨1에 대항하고, 자식 노드로 내려갈수록 레벨은 1씩 증가한다.
ex) G는 레벨 2
: 트리의 깊이
: 트리의 노드의 레벨이 최대 3이면, 트리의 높이는 3이다.이를 깊이라 하기도 한다.
: 트리에서 레벨 순서는 위에서 아래로, 같은 레벨에서는 왼쪽에서 오른쪽으로 순서를 부여한다.
: 포리스트 ( forest )
: 트리 T에서 루트 노드 A를 제거했을 경우에 만들어지는 트릳들을 포리스트라 한다.
그림으로는 이러하다.
- 트리의 표현
: 리스트 구조를 사용해 표현한다.
: 트리 T의 구조를 리스트 구조로 표현하면
: (A ( B ( E, F ( J, K ) ), C, D ( G ( L), H, I))로 표현할 수 있다.