자료구조란? - 비선형 자료구조

자료구조란?

위키백과에 따르면, 자료구조는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미하며, 더 정확히 말해, 자료 구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다고 합니다.

 

비선형 자료구조란?

비선형은 말 그대로 선형이 아니다 즉 비선형 자료구조는 선형자료구조 데이터 관계가 일직선상에 있지 않고 자유분망하게 혹은 규칙적으로 놓여져 있다고 생각이 듭니다.

첫 번째 그림인 트리 구조를 보면 일직선상에 있지 아래로 나무 형식으로 뻗어나가는 모양을 보입니다.

두 번째 그림인 그래프 구조도 일직선상에 있지 않고 자유 분망하게 놓여져 있는 모양을 보입니다.

 

트리

트리 구조는 그래프의 일종으로, 한 노드에서 시작해서 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결 그래프입니다.

특징

• 노드가 N개인 트리의 Edge의 수는 N-1개

트리 종류

• 이진 트리: 각 노드는 최대 2개의 자식만을 갖는 트리

• 포화 이진 트리: 모든 레벨에서 노드들이 꽉 채워져 있는 트리

• 완전 이진 트리: 마지막 레벨을 제외하고 노드들이 모두 채워져 있는 트리

• 정 이진 트리: 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

• 편향 트리(시향 트리): 한쪽으로 기울어진 트리

• 균형 이진 트리: 모든 노드의 좌우 서브 트리 높이가 1이상 차이 나지 않는 트리

 

용어 정리

• 노드(Node): 트리 구조의 자료 값을 담고 있는 단위
  • A, B, C, D, E, F, G 를 뜻합니다.
• 에지(Edge): A-B, C-G 와 같이 노드를 연결해주는 선
• 루트 노드(Root): 부모가 없는 노드, 최상위 노드
• 잎새 노드(Leaf): 자식이 없는 노드
• 내부 노드(Internal): 잎새 노드를 제외한 모든 노드
• 부모(Parent): 연결된 두 노드 중 상위의 노드
• 자식(Child): 연결된 두 노드 중 하위의 노드
• 형제(Sibling): 같은 부모를 가지는 노드
• 깊이(Depth): 루트에서 어떤 노드까지의 간선의 수
  • B의 깊이는 1, D의 깊이는 2
• 레벨(Level): 트리의 특정 깊이를 가지는 노드 집합
  • A의 레벨 0
  • B, C의 레벨 1
  • D, E, F, G의 레벨 2
• 높이(Height): 트리에서 가장 큰 레벨 값
  • A의 높이는 2
  • B,C의 높이는 1
  • D, E, F, G의 높이는 0
• 크기(Size): 자신을 포함 자식 노드의 개수
• 차수(Degree): 각 노드가 지닌 가지의 수
• 트리의 차수: 트리의 최대 차수

이진 탐색 트리

특징

• 왼쪽 자식 노드의 키는 부모 노드의 키보다 작음
• 오른쪽 자식 노드의 키는 부모 노드의 키보다 큼
• 각각의 서브 트리도 이진 탐색 트리를 유지
• 중복된 키를 허용하지 않음

장점

• 이진 트리에 비해 탐색이 빠름

균형 이진 트리(AVL트리, Red-Black 트리)

• 모든 노드의 좌우 서브 트리 높이가 1이상 차이 나지 않는 트리
• 노드의 삽입과 삭제가 일어날 때 균형을 유지하도록 하는 트리
• 각 노드의 BF를 [-1, 0, 1]만 가지게 하여 균형을 유지
  • BF(Balance Factor) : 왼쪽 서브 트리의 높이와 오른쪽 서브 트리 높이의 차이

 

그래프

그래프는 노드와 간선으로 이루어진 자료구조로 연결된 노드간의 관계를 표현할 수 있는 자료 구조입니다.

위에 트리 또한 그래프의 한종류이며 방향 그래프, 무방향 그래프, 완전 그래프, 부분 그래프 등 여러종류의 그래프가 존재합니다.

용어정리

• 정점(Vertax): 각 노드
• 간선(Edge): 노드와 노드를 연결하는 선 (link, branch)
• 인접 정점(Adjacent vertex): 간선 하나를 두고 바로 연결된 정점
• 정점의 차수(Degree)
  • 무방향 그래프에서 하나의 정점에 인접한 정점의 수
  • 무방향 그래프 모든 정점 차수의 합 = 그래프 간선의 수 2배
• 진입 차수: 방향 그래프에서 외부에서 오는 간선의 수
• 진출 차수: 방향 그래프에서 외부로 나가는 간선의 수
• 사이클(Cycle): 단순 경로의 시작 정점과 끝 정점이 동일한 경우

힙

완전 이진 트리의 일종으로 중복값은 허용되며, 반정렬 상태를 유지합니다.

종류

• 최소 힙: 부모 노드의 키가 자식 노드의 키보다 작거나 같은 형태
• 최대 힙: 부모 노드의 키가 자식 노드의 키보다 크거나 같은 형태

우선 순위 큐

제목 그대로 큐이지만 큐는 가장 먼저 들어온 데이터를 꺼내서 삭제 하지만, 우선 순위 큐는 우선순위가 제일 높은 데이터가 먼저 나옵니다.

우선 순위 큐는 배열, 연결리스트, 힙으로 구현 할 수 있습니다.

삽입 삭제

정렬된 배열	O(N)	O(1)
정렬된 연결 리스트	O(N)	O(1)
힙	O(logN)	O(logN)

 

트라이

문자열을 저장하고 빠르게 탐색하기 위한 트리 형태의 자료구조입니다.

문자열 저장을 위한 메모리가 필요하지만 탐색이 빠르며 길이가 N인 문자열 탐색의 시간 복잡도는 O(N)입니다.