비선형 자료 구조(1)

일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말한다.

일반적으로 트리나 그래프를 말한다.

 

그래프

정점과 간선으로 이루어진 자료 구조를 말한다.

 

정점과 간선

어떠한 곳에서 어떠한 곳으로 무언가를 통해 간다고 했을 때 '어떠한 곳'은 정점이고 '무언가'는 간선이 된다.

간선은 단방향, 양방향이 있다.

정점으로 나가는 간선을 해당 정점의 outdegree라고 하며 들어오는 간선을 정점의 indegree라고 한다.

이렇게 정점과 간선으로 이루어진 집합을 그래프라고 한다.

 

가중치

간선과 정점 사이에 드는 비용을 말한다. 예를 들어 1번 노드에서 2번 노드까지 가는 비용이 한 칸이라면 1번 노드에서 2번 노드까지의 가중치는 한 칸이다.

 

트리

그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 이루어져 있고, 트리 구조로 배열된 일종의 계층적 데이터의 집합이다.

루트 노드, 내부 노드, 리프 노드로 구성된다.

 

트리의 특징

1. 부모, 자식 계층 구조를 가진다.
2. V - 1 = E 라는 특징이 있다. 간선 수는 노드 수 - 1이다.
3. 임의의 두 노드 사이의 경로는 유일무이하게 존재한다. 즉, 트리 내의 어떤 노드와 어떤 노드까지의 경로는 반드시 있다.

 

루트 노드

가장 위에 있는 노드

 

내부 노드

루트 노드와 리프 노드 사이에 있는 노드

 

리프 노드

자식 노드가 없는 노드

 

트리의 높이와 레벨

• 깊이 : 각 노드마다 다르며, 루트 노드부터 특정 노드까지 최단 거리로 갔을 때의 거리를 말한다.
• 높이 : 루트 노드부터 리프 노드까지 거리 중 가장 긴 거리를 의미한다.
• 레벨 : 보통 깊이와 같은 의미를 지닌다. 루트 노드는 0레벨, 밑으로 갈 수록 1씩 늘어난다.
• 서브트리 : 트리 내의 하위 집합을 서브트리라고 한다. 트리 내의 부분집합으로도 볼 수 있다.

 

이진 트리

자식의 노드 수가 두 개 이하인 트리를 의미한다.

• 정이진 트리 (full binary tree) : 자식 노드가 0 또는 두 개인 이진 트리를 의미한다.
• 완전 이진 트리 (complete binary tree) : 왼쪽에서부터 채워져 있는 이진 트리를 의미한다. 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며 마지막 레벨의 경우 왼쪽부터 채워져 있다.
• 변질 이진 트리 (degenerate binary tree) : 자식 노드가 하나 밖에 없는 이진 트리를 의미한다.
• 포화 이진 트리 (perfect binary tree) : 모든 노드가 꽉 차 있는 이진 트리를 의미한다.
• 균형 이진 트리 (balanced binary tree) : 왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진 트리를 의미한다. map, set을 구성하는 레드 블랙 트리는 균형 이진 트리 중 하나이다.

 

이진 탐색 트리

노드의 오른쪽 하위 트리에는 '노드 값보다 큰 값'이 있는 노드만 포함되고, 왼쪽 하위 트리에는 '노드 값보다 작은 값'이 들어있는 트리를 말한다.

 

AVL 트리 (Adelson-Velsky and Landis tree)

선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리이다.

두 자식 서브트리의 높이는 항상 최대 1만큼 차이 난다는 특징이 있다.

 

레드 블랙 트리

균형 이진 탐색 트리로 탐색, 삽입, 삭제 모두 시간 복잡도가 O(logn)이다. 각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하며, 삽입 및 삭제 중에 트리가 균형을 유지하도록 하는 데 사용된다.

 

 

Reference

• http://www.yes24.com/Product/Goods/108887922