트리
트리 자료구조는 이름 그대로 나무의 형태를 가지고 있다. 나무가 뿌리에서부터 시작되듯이 트리자료구조 또한 root라는 뿌리로 부터 시작된다.
트리구조의 정의 : 트리 구조는 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조
선형 구조와 비선형 구조
- 선형 구조는 배열과 같이 사이클이 있는 구조이다.
- 비선형 구조는 트리구조와 같이 아래로만 뻗어 나가는 계층적 구조이다. (사이클이 존재할 수 없다.)
트리 구조의 특징
트리구조는 루트라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선으로 연결한다.
각 데이터를 노드라고 칭하고, 두개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 갖게 된다.
A
/ \
B C위와 같은 구조를 트리구조라 칭하고 A는 부모 노드 / B와 C 는 A에 대하여 자식 노드라고 칭한다.
또한 B와 C는 형제 노드이다.
조금더 자세히 알아보자!
A
/ \
B C
/ \ \
D E F
/
G위와같은 구조에서 A와 B,C는 이미 설명을 했고, B는 D와 E의 부모노드가 되는것이고 D와 E는 B의 자식노드가 된다.
또한 Leaf 노드라고도 있는데 자식이 없는 노드는 나무의 잎과 같다고 하여 리프 노드(Leaf Node)라고 부른다.
정리
- 노드(Node) : 트리 구조를 이루는 모든 개별 데이터
- 루트(Root) : 트리 구조의 시작점이 되는 노드
- 부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
- 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
- 리프(Leaf) : 트리 구조의 끝 지점이고, 자식 노드가 없는 노드
트리 구조 용어
깊이(depth)
-> 트리 구조에서는 루트로부터 하위 계층의 특정 노드까지의 깊이(deppth)를 표현할수있다. 루트노드는 지면에 있는 것처럼 깊이가 0 고, 위 그림의 G는 깊이가 2이다.
레벨(Level)
-> 트리 구조에서 같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현이 가능하다. 깊이와 다르게 레벨은 루트노드부터 1부터 시작한다.
즉, 위 그림의 G는 레벨이 3이다.
높이(Height)
-> 트리 구조에서 리프 노드를 기준으로 루트까지의 높이(height)를 표현할 수 있다. 한가지 독특한점은 위 그림에서 D,E,G는 0의 높이를 가지고, B,F 는 1의 높이를, C는 2의 높이를, A는 3의 높이를 가진다. 즉 각각의 마지막 레벨에 있는 노드부터 0으로 시작해서, A는 최종 높이를 갖는다.
서브트리(Sub tree)
-> 트리 구조의 root에서 뻗어 나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리를 서브 트리 라고 부른다. 위 그림에서 A,B,C를 제외한 모든 트리가 서브트리라고 부를수 있다.
트리의 실사용 예
가장 대표적으로는 컴퓨터의 디렉토리 구조이다. 파일들은 파일 내부의 파일들이 있듯이 트리와 비슷한 구조를 갖고있다.
트리 구조와 이진 트리는 트리의 또 다른 추가적인 개념이다. 혼동 금지.
그래프
그래프는 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조이다.
자료구조의 그래프는 독특하게, 수학의 그래프와 다르게 복잡한 네트워크망처럼 서로 연결되어있는 모습을 그래프라고 한다.
위 이미지처럼 그래프를 그림으로 그리면 저런 모양이고, 실제 코드상에서는 메트릭스를 2차배열로 구현하여 문제를 푼다.
그래프의 구조
직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있습니다.
간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어집니다.
하나의 점을 그래프에서는 정점(vertex)이라고 표현하고, 하나의 선은 간선(edge)이라고 합니다.
단어
1. 정점 : vertex(버텍스)라고 하며 그래프의 하나의 점을 가리킴.
2. 간선 : 버텍스와 버텍스를 잇는 선을 edge(간선)이라고 함.
인접 행렬
두 정점을 바로 이어주는 간선이 있다면 이 두 정점은 인접하다고 이야기한다.
인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타낸다. 만약 A라는 정점과 B라는 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시한 일종의 표이다.
예시
위와 같은 이미지 그래프가 있다면 이것은 매트릭스로 이렇게 표현가능하다.
총 4개의 버텍스가 존재하고 엣지들은 일시방향이다.
int [][] graph = new int [5][5];
{0,0,0,0,0} //0 버텍스는 아무것도 이어져 있지 않아서 모든 진출로가 0이다.
{0,0,1,1,0} //1 버텍스는 2번과 3번 버텍스로 갈 수 있기 때문에 진출로가 2개이다.
{0,0,0,0,0} //2 버텍스는 아무 곳도 갈수 없기 때문에 모든 진출로가 0이다.
{0,0,1,0,1} //3 버텍스는 2번과 4번 버텍스로 갈 수 있기 때문에 진출로가 2개이다.
{0,0,0,0,0} //4 버텍스는 아무 곳도 갈수 없기 때문에 모든 진출로가 0이다.
//이렇게 그래프 그림을 2차 배열을 이용하여 메트릭스로 표현이 가능하다. 인접 행렬의 사용시기
- 한 개의 큰 표와 같은 모습을 한 인접 행렬은 두 정점 사이에 관계가 있는지 없는지 확인하기에 용이하다.
- 가장 빠른 경로(Shortest path)를 찾고자 할 때 주로 사용된다.
인접 행렬의 단점
- 전체 노드의 개수를 V개, 간선의 개수를 E개라고 했을 때, 노드 i에 연결된 모든 노드를 탐색해야 하기 때문에 O(V)이 걸린다는 단점이 존재.
- 최악의 경우, 노드가 억 단위가 된다면, 정말 오랜시간이 걸리게 될 것이다.
인접 리스트
인접 리스트는 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현한다. 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있다.
인접 리스트의 사용시기
- 메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용한다.
- 인접 행렬은 연결 가능한 모든 경우의 수를 저장하기에 상대적으로 메모리를 많이 차지함.
알아둬야 할 그래프 용어들
정점 (vertex): 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소입니다.
간선 (edge): 정점 간의 관계를 나타냅니다. (정점을 이어주는 선)
인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점을 뜻합니다.
가중치 그래프 (weighted Graph): 연결의 강도(추가적인 정보, 위의 예시에서는 서울-부산으로 가는 거리 등)가 얼마나 되는지 적혀져 있는 그래프를 뜻합니다.
비가중치 그래프 (unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프를 뜻합니다.
무(방)향 그래프 (undirected graph): 앞서 보았던 내비게이션 예제는 무(방)향 그래프입니다. 서울에서 부산으로 갈 수 있듯, 반대로 부산에서 서울로 가는 것도 가능합니다. 하지만 단방향(directed) 그래프로 구현된다면 서울에서 부산을 갈 수 있지만, 부산에서 서울로 가는 것은 불가능합니다(혹은 그 반대). 만약 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현할 수 있습니다.
진입차수 (in-degree) / 진출차수 (out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냅니다.
인접 (adjacency): 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점입니다.
자기 루프 (self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현합니다. 다른 정점을 거치지 않는다는 것이 특징입니다.
사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현합니다. 내비게이션 그래프는 서울 —> 대전 —> 부산 —> 서울 로 이동이 가능하므로, 사이클이 존재하는 그래프입니다.
추가적인 다른 블로거의 정리 링크
