[CS 면접지식노트] 비선형 자료구조
비선형 자료구조(NonLinear Data Structure)
일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조로 일반적으로 트리나 그래프를 말한다.
그래프(Graph)
정점과 간선으로 이루어진 자료구조
정점과 간선
어떠한 곳에서 어떠한 곳으로 무언가를 통해 간다고 했을 때 '어떠한 곳'은 정점(Vertex) '무언가'는 간선(Edge)이 된다.
간선에는 단방향과 양방향이 존재한다.
V로 부터 나가는 간선을 outdegree / v로 들어오는 간선을 indegree
+ 정점은 약자로 V 또는 U라고 한다.
가중치
정점고 정점 사이에 드는 비용
트리(Tree)
그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 이루어져있고 트리구조로 배열된 일종의 계층적 데이터의 집합이다.
- 루트노드, 내부 노드, 리프 노드 등으로 구성된다.
트리 특징
- 간선의 수 = 노드 수 - 1
- 같은 경로상에서 어떤 노드보다 위에 있으면 부모 아래 있으면 자식 노드가 된다.
- 임의의 두 노드 사이의 경로는 '유일무이' 하게 존재한다.
- 트리 내의 어떤 노드까지의 경로는 반드시 존재
트리 구성
루트 노드
가장 위에 있는 노드로 보통 트리를 탐색할 때 루트 노드를 중심으로 탐색하면 문제가 쉽게 풀린다.
내부 노드
루트 노드와 내부 노드 사이에 있는 노드
리프 노드
자식 노드가 없는 노드
트리의 높이와 레벨
- 깊이
- 루트로부터 하위 계층의 특정 노드까지의 깊이(depth)
- 4번 노드의 길이는 2
- 높이
- 가장 하위에 있는 리프 노드를 기준으로 루트까지의 높이(height)
- 예제에서의 높이는 3
- 레벨
- 같은 깊이를 가지고 있는 노드를 묶어서 레벨(level)
- 루트노드를 0레벨이라 할 때 2,3 노드를 1레벨 / 루트 노드를 1레벨이라 할 때 2,3 노드를 2레벨...
- 서브 트리
- 트리 구조의 root에서 뻗어 나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리
- 5, 6, 7번 노드는 전체 트리의 하위 집합으로 서브트리라 한다.서브 트리
이진 트리(Binary Tree)
자식의 노드 수가 두 개 이하인 트리로 다양한 종류의 이진 트리가 존재한다.
- 정이진 트리(Full Binary Tree): 자식 노드가 0 또는 두 개인 이진 트리
- 완전이진트리(Complete Binary Tree): 왼쪽에서부터 채워져 있는 이진 트리로 마지막 레벨을 제외하고 모든 레벨이 완전하게 채워져 있으며 마지막 레벨의 경우 왼쪽부터 채워져 있음
- 변질이진트리(Degenerate Binary Tree): 자식 노드가 하나밖에 없는 이진트리
- 포화이진트리(Perfect Binary Tree): 모든 노드가 꽉 차 있는 이진트리
- 균형이진트리(Balanced Binary Tree): 왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진 트리로 Map, Set을 구성하는 레드블랙트리는 균형이진트리 중 하나이다.
이진탐색트리(BST, Binary Search Tree)
현재 노드의 왼쪽 하위 트리에는 현재 노드 값보다 작은 값만 있는 노드만 포함되고, 오른쪽 하위 트리에는 해당 노드의 값보다 큰 값이 있는 노드가 포함되어있는 트리
- 왼쪽 및 오른쪽 하위 트리에도 같은 위와 같은 특성이 적용된다.
- 이렇게 노드들을 구성하는 이유는 검색(search)을 하기에 용이하기 때문이다.
- 보통 요소를 찾을 때 이진 탐색 트리의 경우 O(log n) 최악의 경우 O(n)이 걸리는데 이유는 이진 탐색 트리는 삽입 순서에 따라 선형적일 수 있기 때문이다.
AVL트리(Adelson-Velsky and Landis Tree)
자가균형이진탐색트리라고도 부르며 이진탐색트리에서 최악의 경우 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진탐색트리
두 자식의 서브트리의 높이는 항상 최대 1만큼 차이가 난다는 특징이 있음.
AVL트리는 이진탐색트리는 선형적인 트리의 형태를 가질 때 최악의 경우O(n)의 시간 복잡도를 가지는데, "이러한 최악의 경우를 배제하고 항상 균형잡힌 트리로 만들자"는 개념을 가진 트리이다.
- 탐색, 삽입, 삭제 모두 시간 복잡도가 O(log n)이며 삽입, 삭제를 할 때마다 균형을 맞추기 위해 트리 일부를 왼쪽 혹은 오른쪽으로 회전하며 균형을 잡는다.
- 각 노드마다 균형도가 있으며 균형도가 절대값 2미만인 경우 "균형트리" / 절대값 2 이상인 경우 "불균형트리"이다.
- 부모 노드 균형도 = 좌측 노드 높이 - 우측 노드 높이이다.
레드 블랙 트리
균형 이진 탐색 트리로 탐색, 삽입, 삭제 모두 시간 복잡도가 O(log n)이다.
각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하며 삽입 및 삭제 중에 트리가 균형을 유지하도록 하는 데 사용된다.
모든 리프 노드와 루트 노드는 블랙이고 어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.
위와 같은 여러 규칙들을 기반으로 균형을 잡는 트리를 레드 블랙 트리라 한다.
힙(Heap)
완전 이진 트리 기반의 자료구조로 최소힙과 최대힙 두 가지가 있고 해당 힙에 따라 특정한 특징을 지킨 트리를 의미한다.
- 최대 힙
- 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야하고 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어진다.
- 최소힙
- 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 작아야 하고 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어진다.
힙에는 어떠한 값이 들어와도 특정 힙의 규칙을 지키게 만들어져 있다.
최대힙의 삽입
힙에 새로운 요소가 들어오면 새로운 노드를 힙의 마지막 노드에 이어서 삽입하며 새로운 노드를 부모 노드들과 크기를 비교하며 교환해서 힙의 성질을 만족시킨다.
8이라는 값을 가진 노드 밑에 15라는 값을 가진 노드를 삽입한다고 하면 이 노드가 점차 올라가면서 해당 노드 위에 있는 노드와 스왑하는 과정을 거쳐 최대 힙 조건을 만족하게 된다.
최소힙의 삭제
최대힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제되고 마지막 노드와 루트 노드를 스왑하여 또 다시 스왑 등의 과정을 거쳐 재구성된다.