[CS] 트리(Tree)란 무엇인가?

트리란?

트리구조는 나무를 뒤집어 놓은 모습과 유사한 구조를 가지고 있어 붙여진 이름이다. 하나의 뿌리(루트 노드)로부터 가지를 뻗어 값을 이룬 형태가 나무와 닮아 있다.

트리는 그래프의 여러 구조 중 단방향 그래프의 한 구조이다.

 

트리구조는 데이터가 하나 이상의 다른 데이터에 무방향으로 연결된 계층적 자료구조이다. 데이터를 순차적으로 나열시킨 선형 구조가 아닌 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조이다. 또한, 단방향으로 연결되어 아래로만 뻗어 나가기 때문에 사이클이 존재하지 않는다.

 

트리의 구조와 특징

루트(Root)

최상위에 존재하는 데이터는 루트(Root)라고 한다. 루트부터 시작하여 여러 개의 데이터를 간선(edge)으로 연결한다.

 

노드(Node)

노드는 루트를 포함하여 트리 구조의 각 데이터를 노드라고 한다. 노드 간의 상하 계층으로 연결되면 이를 부모-자식 관계를 가진다. 또한, 최상위 데이터는 루트 노드라고도 한다.

 

부모 노드(Parent Node)

노드 A와 노드 B가 서로 연결되어 A가 상위, B가 하위에 존재한다면, A는 B의 부모 노드이다.

 

자식 노드(Child Node)

마찬가지로 위 예시를 들면, B는 A의 자식 노드이다.

 

리프 노드(Leaf Node)

리프 노드는 자식이 없는 노드이다.

 

깊이(Depth)

트리 구조에서는 루트로부터 하위 계층의 특정 노드까지의 깊이를 표현할 수 있다. 루트 노드의 depth는 0이며, 하위 노드로 1칸씩 내려갈 때마다 1씩 증가한다. 위 그림으로 나타내면 B와 C의 depth는 1, D, E, F, G의 depth는 2가 된다.

 

레벨(Level)

같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현할 수 있다. depth가 0인 루트 노드는 level 1이 된다. 또한, 같은 레벨에 나란히 존재하는 노드들은 형제 노드(Sibling Node)라고 한다.

 

높이(Height)

리프 노드를 기준으로 루트까지의 높이(height)를 표현할 수 있다. 리프 노드와 직간접적으로 연결된 노드의 높이를 표현한다. 각 리프 노드의 height는 0이 되며, 상위 노드로 올라갈 때마다 height + 1을 가진다. 즉, B는 D의 height + 1인 2, C는 G의 height +1인 2를 가지며 루트 노드 A의 높이는 3이 된다.

 

서브 트리(Sub tree)

트리 구조안에 존재하는 작은 트리 구조를 뜻한다. 위 그림 상에서 D, H, I는 루트가 A인 트리 구조안에서 작은 트리 구조를 이룬다. 이를 서브 트리라 한다.