Tree

자료구조 Tree는 이름 그대로 거꾸로 놓은 나무의 형태를 가지고 있다. 그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있다고 해서 트리 구조라고 부릅니다.

Tree 구조의 특징

가장 먼저 시작 되는 Root가 있으며 여러개의 데이터를 간선으로 연결 한다.

1은 234의 부모가 되는 노드이며, 3은 67의 부모 노드이다.
부모 밑에 있는 노드들은 자식 노드이며 , 자식에서 다시 파생되는 자식이 없으면 나뭇잎과 같다고 하여 leaf노드 라고 한다.

깊이 (depth)
트리 구조에서는 루트로부터 하위 계층의 특정 노드까지의 깊이(depth)를 표현할 수 있습니다. 루트 노드는 지면에 있는 것처럼 깊이가 0입니다. 위 그림에서 루트 1의 depth는 0이고, 2,3,4의 깊이는 1입니다. 6,7의 깊이는 2입니다.

레벨(Level)
트리 구조에서 같은 깊이를 가지고 있는 노드를 묶어서 레벨(level)로 표현할 수 있습니다. depth가 0인 루트 1의 level은 1입니다. depth가 1인 2,3,4의 level은 2입니다. 6,7의 레벨은 3입니다. 같은 레벨에 나란히 있는 노드를 형제 노드(Sibling Node) 라고 합니다.

서브 트리(Sub tree)
트리 구조의 root에서 뻗어 나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리를 서브 트리 라고 부릅니다. (3,6,7)로 이루어진 작은 트리도 서브 트리 입니다.

Graph

그래프는 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조입니다.

Graph의 구조

• 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있습니다.
• 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어집니다.
• 하나의 점을 그래프에서는 정점(vertex)이라고 표현하고, 하나의 선은 간선(edge)이라고 합니다.

위 그림에서 확인해 보면 1,2,3,4는 정점(vertex)이고 연결 되어 있는 화살표는 간선(edge)이다.
화살표가 양방향으로 연결 되어 있는 것은 무(방)향 그래프 (undirected graph)라고 한다.

인접 정점 (adjacent vertex)은 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점을 뜻합니다.