비선형 자료 구조

비선형 자료 구조

비선형 자료 구조는 데이터 요소들이 선형적으로 나열되어 있지 않고 계층적인 구조를 의미한다.

그래프

정점(Vertex)과 간선(Edge)으로 이루어진 자료 구조를 의미한다.

 

그래프 저장 방법

1. 인접 행렬 : 정점과 간선의 관계를 2차원 행렬로 표현, 공간 복잡도 : O(V^2)

2. 인접 리스트 : 정점과 간선이 주어졌을 때 2차원 ArrayList로 표현, 공간 복잡도 : O(E)

트리

정점들이 계층적인 구조를 가지고 있는 비선형 자료 구조이다.

하나의 루트 노드 에서 시작하여, 부모-자식 관계를 가지는 노드들로 구성되어 있다.

반드시 노드가 N인 트리는 항상 N-1개의 간선을 가진다.

노드의 종류

• 루트 노드 : 최상단에 있는 노드
• 내부 노드 : 루트 노드와 리프 노드 사이에 있는 노드
• 리프 노드 : 자식 노드가 없는 노드

트리의 깊이와 높이

• 깊이 : 루트 노드부터 특정 노드까지 최단 거리로 갔을 때의 거리
• 높이 : 루트 노드부터 리프 노드까지 거리 중 가장 긴 거리

이진 트리의 분류

• 정이진 트리 : 자식 노드가 0 또는 2개인 이진 트리
• 완전 이진 트리 : 왼쪽에서부터 채워져 있는 이진 트리, 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 경우에도 왼쪽부터 채워져 있다.
• 변질 이진 트리 : 자식 노드가 하나밖에 없는 이진 트리
• 포화 이진 트리 : 모든 노드가 꽉 차 있는 이진 트리
• 균형 이진 트리 : 왼쪽과 오른쪽 노드의 높이 차이가 1이하인 이진 트리

이진 탐색 트리(BST)

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

데이터 요소를 찾을 때 이진 탐색 트리의 경우 O(logn)이 걸리지만, 삽입 순서에 따라 선형적으로 트리 한쪽에만 노드가 몰릴 수 있기 때문에 최악의 경우 O(n)이 걸린다.