[자료구조] 트리(Tree)

 

이번에는 트리 자료 구조이다.

 

트리(Tree)는 말그대로 …

나무이다.

 

트리구조는 나무를 보고 나뭇가지가 쭉쭉 뻗어있는 모습이 연상되서

이름이 그렇게 지어진 것 같다.

이렇게 나뭇가지처럼 뻗은 모습이 연상 된다.

 

트리는 계층적 관계(Hierarchical Relationship)를 표현 한 자료 구조이다.

 

단순히 무엇인가 저장하고 꺼내는 것이 전부가 아닌 무엇인가 표현하는 것이다

단지 표현을 위해서 저장과 삭제라는 기능이 제공되어 있을 뿐 이다.

 

트리가 아래로 뻗으나 옆으로 뻗으나 중요치는 않다.

중요한 것은 가지가지를 늘려가며 뻗어간다는 사실이다.

이러한 구조도 트리 구조이다.

방향만 다르고 가지가 뻗어가는 모습은 같지 않은가?

 

일단 트리에 관해서 용어를 설명하자면 …

노드	node
트리의 구성요소에 해당하는 A,B,C,D,E,F와 같은 요소
간선	edge
노드와 노드를 연결하는 연결선
루트노드	root node
트리 구조에서 최상위에 존재하는 A와 같은 노드
단말노드	terminal node
아래로 또 다른 노드가 연결되어 있지 않은 E,F,C,D
내부노드	internal node
단말 노드를 제외한 모든 노드로 A,B와 같은 노드

 

단말 노드는 나무의 구조상에 잎에 해당한다고 해서 '잎사귀 노드(leaf node)'라고도 불린다.

내부 노드는 단말노드가 아니여서 '비단말 노드(noninternal node)'라고도 불린다.

 

노드간에는 부모(parent),자식(child) , 형제(sibling)성립되어 이렇게 표현 가능하다.

노드 A는 노드 B,C,D의 부모 노드(parent node) 이다.

노드 B,C,D는 노드 A의 자식 노드(child node)이다.

노드 B,C,D는 부모 노드가 같으므로 서로서로 형제노드(sibling node)이다.

이 관계들은 상대적으로 B가 A의 자식노드지만 E,F의 부모 노드도 된다.

 

그리고 특정 노드의 위에 위치한 모든 노드를 조상노드(Ancester node)라고 하고

특정 노드의 아래에 위치한 모든 노드를 후손노드(Descendant node)라고 부른다.

 

 

위 그림을 보면 큰 트리는 작은 트리로 구성이 된다.

이렇게 큰 트리에 속하는 작은 트리를 서브 트리(sub tree)라고 한다.

빨간 박스는 A를 루트노드로 하는 서브트리이고

검정 박스는 B를 루트노드로 하는 서브트리이다.