[트리 1일차] 트리의 정의 및 용어

트리의 정의 및 용어

[ 트리의 정의 ]

- 아래 그림과 같이 마치 나무를 거꾸로 한 모양 같은 자료구조를 트리라고 한다.

- 트리의 여러 가지 방법으로 정의할 수 있다. 그 중 한가지는 '루트 노드와 다른 모든 노드와의 경로가 유일할 경우 그러한 구조를 트리라고 한다'라는 것이다. 

 

[ 트리와 그래프의 차이점 ]

- 만약 루트 노드와 루트 노드가 아닌 다른 노드와의 경로가 둘 이상이거나 없는 경우가 있다면 이를 그래프(Graph)라고 한다. 

트리의 정의 및 용어

 

[ 트리의 용어 ]

(1) 노드(node) : 이름과 관계된 정보를 담을 수 있는 객체(object)를 노드라고 한다. 왼쪽의 예에서는 A, B, C, D, E, F, G 모두 7개의 노드가 있다.

(2) 간선(edge) : 두 노드를 잇는 선을 간선이라고 한다.

(3) 루트 노드(root node) : 트리의 가장 위에 있는 노드가 루트 노드가 된다. 위의 예에서 루트는 A이다.

(4) 부모 노드(parent node) : 어떤 노드 위에 연결되어 있는 노드를 그 노드의 부모 노드라고 한다. 위의 예에서 B는 D의 부모 노드이다.

(5) 자식 노드( child node) : 어떤 노드 아래에 연결되어 있는 노드를 그 노드의 자식 노드라고 한다. 위의 예에서 E는 C의 자식 노드이다.

(6) 형제 노드( sibling node) : 같은 부모 노드를 갖는 노드들을 형제 노드라고 한다. 위의 예에서 E와 F는 형제 노드이다.

(7) 단말 노드( leaf node, terminal node, external node ) : 자식 노드가 없는 노드를 단말 노드라고 한다. 위의 예에서 D, E, G는 단말 노드이다.

(8) 내부 노드( internal node, nontorminal node) : 자식 노드가 하나 이상 있는 노드를 내부노드라고 한다. 위의 예에서 A, B, C, F는 내부 노드이다.

(9) 부트리(sub node) : 임의의 노드를 루트 노드로 했을 때 그 노드와 그 아래의 노드들은 하나의 부트리를 이룬다. 위의 예에서 C, D, F, G는 루트 노드로 하나 하나의 부트리이다.

(10) 레벨(level) : 루트 노드까지의 거리. 예를 들어 B의 레벨은 1, F의 레벨은 2이다.

(11) 높이, 깊이(height, depth) :  트리에 포함되는 노드의 레벨 중 가장 큰 값을 그 트리의 높이, 또는 깊이라고 한다.

 

※ 트리라는 이름은 나무를 거꾸로 한 모양에서 나왔다.

가장 위에 있는 노드를 root(뿌리) 노드,

가장 끝에 있는 노드를 leaf(잎) 노드라고 부르는 것도 비슷한 이유에서이다.