비선형 자료구조

비선형 자료구조란?

일렬로 나열하지 않고 복잡한 구조를 말한다. 일반적으로 트리나 그래프를 말한다.

그래프

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

이 간선의 구조로는 단방향 간선과 양방향 간선이 있다.
나라는 주체의 정점과 아파트라는 정점을 두고 나라는 사람이
아파트로 가는 길을 간선이라고 생각하면 되고 이 간선은
단방향 간선이라고 볼 수 있다.

양방향 간선으로는 서로 사랑하는 연인 사이일 경우
사랑이라는 감정이 남성과 여성 두개의 정점에서
두명다 사랑을 하기 때문에 양방향 간선이라고 볼 수 있다.

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

정점은 약자로 V 또는 U라고 한다.
그리고 지금까지 설명한 정점과 간선으로 이루어진 집합을
그래프라고 한다.

가중치
가중치는 간선과 정점사이에 드는 비용이다.

예를들어 내가 택시를 타고 부산에서 서울로 가는데 드는
택시비가 30만원이라고 한다면 부산에서 서울로가는 가중치는
30만원이 된다.

트리

트리는 그래프 중 하나이고 트리 구조로 배열된 일종의 계층적 데이터의
집합이다. 트리로 이루어진 집합을 숲이라고 한다.

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

트리의 구조
트리는 루트, 내부, 리프로 이루어져 있습니다.

각각의 의미를 알아보겠습니다.

루트노드

가장 위에 있는 노드, 보통 트리 문제를 풀 때에 트리를 탐색하는 경우 루트노드를
기준으로 탐색하면 문제 해결이 쉽습니다.

내부노드

루트노드와 내부 노드 사이에 있는 노드이다.

리프노드

리프노드는 자식 노드가 없는 노드를 뜻한다.

트리의 높이와 레벨

• 깊이 : 루트 노드로부터 특정 노드 까지 최단 거리로 갔을 때의 거리
• 높이 : 루트 노드로부터 리프 노드까지 거리 중 가장 긴 거리
• 레벨 : 주어지는 문제마다 조금씩 다르지만 보통 깊이와 같은 의미

이진트리

의미 : 자식의 노드 수가 두 개 이하인 트리

종류

• 정이진 트리: 자식 노드가 0 또는 두 개인 이진트리
• 완전 이진 트리: 왼쪽에서 부터 채워져 있는 이진트리
• 변질 이진 트리: 자식노드가 하나밖에 없는 이진트리
• 포화 이진 트리: 모든 노드가 꽉 차 있는 이진트리
• 균형 이진 트리: 왼쪽의 노드와 오른쪽 노드의 높이 차이가 1이하인 이진트리

이진 탐색 트리

이진 탐색 트리(BST)는 노드의 오른쪽 하위 트리에는
노드 값보다 큰 값이 있는 노드만 포함, 왼쪽 하위트리에는
노드 값보다 작은 값이 들어있는 트리이다.

특징

검색하기에 용이하다 그 이유로는 오른쪽에는 큰 값만,
왼쪽에는 작은 값만 있기 때문에 찾기 용이하다.
하지만 이진 탐색 트리는 삽입 순서에 따라 선형적일 수 있기 때문에
엄청 오래걸릴 수 도 있다.