24.01.19 비선형 자료 구조 1
1. 비선형 자료 구조
- 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조
- 일반적으로 트리나 그래프를 말함
1) 그래프
- 정점과 간선으로 이루어진 자료구조
(1) 정점과 간선
- 어떠한 곳에서 어떠한 곳으로 무언가를 통해 간다고 했을 때 어떠한 곳은 정점(vertex)이 되고
무언가는 간선(edge)이 됨
- 짝사랑은 단반향 간선이고 서로 좋아하는 것은 양방향 간선과 같다
- 예) 아래 그림처럼 집으로 간다고 했을 때 나와 아파트는 하나의 정점이고 거기로 가는 길은 간선이 됨
- 정점으로 나가는 간선을 해당 정점의 outdegree 라고 하며, 들어오는 간선을 해당 정점의 indegree 라고 한다
- 위의 그림의 정점 V 는 outdegree 는 세개, indegree 는 두개인 상태
- 정점은 약자로 V 또는 U 라고 하고, 보통 어떤 정점으로부터 시작해서 어떤 정점까지 간다를
U 에서 부터 V 로 간다라고 표현
- 정점과 간선으로 이루어진 집합을 그래프라고함
A) 가중치
- 간선과 정점 사이에 드는 비용
- 1번 노드와 2번 노트까지 가는 비용이 한칸이라면 가중치는 한칸
- 예) 성남이라는 정점에서 네이버라는 정점까지 가는데 걸리는 택시비가 13,000원이라면
성남에서 네이버까지 가는 가중치는 13,000원이 됨
2) 트리
- 그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 이루어져 있고, 트리구조로 배열된 일종의
계층적 데이터의 집합
- 루프 노드, 내부 노드, 리프 노드 등으로 구성됨
- 트리로 이루어진 집합을 숲이라고 함
(1) 트리의 특징
- 그래프의 일종이며 다음 특징을 가진 다는 점이 다르다
* 부모, 자식 계층 구조를 가짐 5번 노드는 6번 노드와 7번 노드의 부모노드이고 6번 노드와 7번 노드는
5번 노드의 자식노드이다. 같은 경로상에서 어떤 노드보다 위에 있으면 부모, 아래 있으면 자식노드가 됨
* V - 1 = E 라는 특징이 있다. 간선 수는 노드수 -1 임
* 임의의 두 노드 사이의 경로는 유일무이하게 존재한다. 즉, 트리 내의 어떤 노드와 어떤 노드까지의
경로는 반드시 있다
(2) 트리의 구성
- 루트 노드, 내부 토드, 리프 노드로 이루어짐
A) 루트 노드
- 가장 위에 있는 노드
- 트리 문제가 나오고 트리를 탐색할 때 루트 노드를 중심으로 탐색하면 문제가 쉽게 풀리는 경우가 많다
B) 내부 노드
- 루트 노드와 내부 노드 사이에 있는 도드
C) 리프 노드
- 자식 노드가 없는 노드
(3) 트리의 높이와 레벨
- 깊이 : 각 노드마다 다르며, 루트 노드부터 특정 노드까지 최단 거리로 갔을 때의 거리를 말한다
예) 4번 노드의 깊이는 2 이다
- 높이 : 루트 노드부터 리프 노드까지 거리 중 가장 긴 거리를 의미하며 위 그림의 트리 높이는 3이다
- 레벨 : 주어지는 문제마다 조금씩 다르지만 보통 깊이와 같은 의미를 지닌다
1번 노드를 0레벨이라고 하고 2번 노드, 4번 노드까지의 레벨을 1레벨이라고 할 수도 있고,
1번 노드를 1레벨 이라고 한다면 2번 노드와 3번 노드는 2레벨이 됨
- 서브트리 : 트리 내의 하위 집합을 서브트리라고한다
트리 내에 있는 부분 집합이라고 보면됨
5번, 6번, 7번 노드가 이 트리의 하위 집합으로 저 노드들은 서비트리 이다 라고함
(4) 이진 트리
- 자식의 노드 수가 두개 이하인 트리를 말함
- 아래와 같이 분류
* 정이진 트리(full binary tree) : 자식 노드가 0 또는 두개인 이진 트리
* 완전 이진 트리(complete binary tree) : 왼쪽에서부터 채워져 있는 이진트리
마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며
마지막 레벨의 경우 왼쪽부터 채워짐
* 변질 이진 트리(degenerate binary tree) : 자식 노드가 하나밖에 없는 이진트리
* 포화 이진 트리(perfecte binary tree) : 모든 노드가 꽉 차 있는 이진트리
* 균형 이진 트리(balanced binary tree) : 왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진트리
map, set 을 구성하는 레드 블랙 트리는 균형 이진 트리중 하나다
(5) 이진 탐색 트리 (BST)
- 노드의 하위 트리에는 노드 값보다 큰 값이 있는 노드만 포함되고, 왼쪽 하위 트리에는 노드 값보다
작은 값이 들어있는 트리
- 왼쪽 및 오른쪽 하위 트리도 해당 특성을 가짐
- 검색하기에 용이하다
- 왼쪽에는 작은 값 오른쪽에는 큰 값이 이미 정해져 있기 때문에 10을 찾으려고 한다면 25의
왼쪽 노드들만 찾으면됨
- 보통 요소를 찾을때 이진 탐색 트리의 경우 O(logn) 이 걸린다 최악의 경우 O(n) 이걸림
- 그 이유는 아래그림처럼 삽입 순서에 따라 선형적일 수 있기 때문
(6) AVL 트리 (Adelson - Velsky and Landis tree)
- 앞서 설명한 최악의 경우 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리
- 두자식 서브트리의 높이는 항상 최대 1만큼 차이 난다는 특징이 있다
- 이진 탐색 트리는 선형적인 트리 형태를 가질 때 최악의 경우 O(n) 의 시간 복잡도를 가진다
- 이러한 최악의 경우를 배제하고 항상 균형 잡힌 트리로 만들자 라는 개념을 가진 트리가 AVL 트리
- 탐색, 삽입, 삭제 모두 시간 복잡도가 O(logn)이며 사입, 삭제를 할 때 마다 균형이 안맞는 것을
맞추기 위해 트리 일부를 왼쪽 혹은 오른쪽으로 회전시키며 균형을 잡는다
(7) 레드 블랙 트리
- 균형 이진 탐색 트리로 탐색, 삽입, 삭제 모두 시간 복잡도가 O(logn) 이다
- 각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하며, 삽입 및 삭제 중에 트리가
균형을 유지하도록 하는데 사용됨
- C++ STL 의 set, multiset, map, and multimap 이 레드 블랙 트리를 이용해 구현됨
- 모든 리프 노드와 루트 노드는 블랙이고 어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙이다 등의
규칙을 기반으로 균형을 잡는 트리
