자료구조2

자료구조 2

트리, 그래프

트리

특징

• 계층적인 구조를 가진 자료구조
• 원소들 간에 1:N 관계를 가지는 비선형 자료구조

• 구성요소를 노드(node)라고 부르며, 노드 간의 관계를 부모, 자식 관계라고 표현한다

  • 루트(root): 부모가 없는 최상단의 노드
  • 서브트리(subtree): 트리 속 트리
  • 단말노드(Terminal node)또는 리프노드(Leaf Node): 자식 노드가 존재하지 않는 노드

• 전체적인 형상에 있어서는 레벨(level), 높이(height), 차수(degree)를 사용한다

  • 레벨(level): 트리의 각 층의 번호
    • 레벨의 시작을 0으로 시작하기도, 1로 시작하기도 한다
  • 높이(height): 트리의 최대 레벨(깊이)
    • 양 쪽 서브트리의 높이가 다를 경우 가장 레벨이 큰 쪽을 따른다
  • 차수(degree): 노드가 가지고 있는 자식 노드의 개수

• 배열 또는 다중 연결 리스트로 구현

종류

• 일반 트리: 노드의 차수가 K인 트리(K는 자연수)
  • 차수가 커질수록 메모리의 낭비가 발생
• 이진 트리: 모든 노드가 2개의 서브트리를 가지고 있는 트리
  • 구성에 따라 포화 이진 트리, 완전 이진 트리, 편향 이진 트리라고 추가적으로 부름
    • 포화 이진 트리: 트리의 각 레벨에 노드가 꽉 차있는 이진 트리
    • 완전 이진 트리: 마지막 레벨을 제외한 모든 레벨이 다 차있고, 마지막 레벨은 왼쪽부터 순차적으로 채워져있는 이진 트리
    • 편향 이진 트리: 모든 노드가 한 쪽으로만 서브트리를 가지고 있는 트리

순회(Traversal)

• 트리의 노드들을 빠뜨리거나 중복하지 않고 방문하는 것
• 이진 트리에서 왼쪽에서 오른쪽으로 이동하는 경우 *전위 순회, 중위 순회, 후위 순회 *가 존재
  • 전위 순회(preorder traversal): 루트 노드 방문 후 왼쪽 노드, 오른쪽 노드를 방문
  • 중위 순회(inorder traversal): 왼쪽 노드, 루트, 오른쪽 노드 순으로 방문
  • 후위 순회(postorder traversal): 오른쪽 노드, 루트, 왼쪽 노드 순으로 방문
• 각 노드를 레벨 순으로 순회 하는 방법을 레벨 순회라고 부른다

그래프

특징

• 요소간의 연결되어 있는 관계를 표현하는 비선형 자료구조
  • 트리도 그래프의 특수한 경우

• 요소를 다른 단어로는 정점(vertex)또는 노드(node)라고도 부르고, 요소 간의 이어진 관계를 간선(edge)또는 링크(link)라고 한다.
• 특정 정점에서 다른 정점까지 가는데 거쳐가는 간선들의 집합을 경로(path)라고 부르고, 사용된 간선들의 수를 길이(length)라고 한다.
  • 단순 경로(simple path): 경로 중에서 반복되는 간선이 없는 경로
  • 사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경로
• 인접 행렬(adjacent matrix)와 인접 리스트(adjacency list)로 구현
  • 인접 행렬(adjacent matrix): 각 행과 열은 정점을 나타냄, 무방향 그래프에선 대칭을 이룬다.
  • 인접 리스트(adjacency list): 각 정점에 연결된 정점들을 연결리스트로 표현

종류

• 무방향 그래프 & 방향 그래프
  • 무방향 그래프(undirected graph): 그래프의 간선에 있어 방향성이 존재하지 않아 양방향으로 이동이 가능하다.
    • 두 정점 A와 B 사이의 간선을 (A,B) 또는 (B,A)로 표시
    • 하나의 정점에 연결된 다른 정점들의 수를 차수(degree)라고 한다.
  • 방향 그래프(directed graph): 그래프의 간선에 있어 방향성이 존재해 지정된 방향으로만 이동할 수 있다.
    • 정점 A에서 정점 B로 향하는 간선의 경우 <A,B>로 표시
    • 간선에 방향성이 존재하기에, 외부에서 오는 간선의 수를 진입 차수(in-degree), 외부로 향하는 간선의 수를 진출 차수(out-degree)라고 한다.
• 가중치 그래프
  • 간선에 비용(cost)나 가중치(weight)가 할당된 그래프
• 부분 그래프
  • 그래프 속 일부 정점들과 간선들로 이루어진 그래프
• 연결 그래프 & 비연결 그래프
  • 연결 그래프(connected graph): 무방향 그래프에서 모든 정점 간의 경로가 존재하는 그래프
    • 이중 사이클을 가지지 않는 연결 그래프를 트리(tree)라고 한다.
  • 비연결 그래프(disconnected graph): 무방향 그래프에서 특정 정점 간의 경로가 없는 그래프
• 완전 그래프
  • 모든 정점이 연결되어 있는 그래프
  • n개의 정점을 가진 무방향 완전 그래프의 간선의 수: nx(n-1)/2

탐색(순회)

• 하나의 정점으로부터 차례대로 모든 정점들을 한 번씩 방문하는 것

• 그래프의 탐색에는 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)을 사용

• 최소 경로 탐색을 위해 신장 트리를 만들어 탐색

  • 신장 트리(spanning tree): 그래프 내의 모든 정점을 포함하는 트리이며, 사이클을 포함하면 안된다.

    n개의 정점에 대한 신장 트리는 n-1개의 간선을 가진다.

힙

특징

• 우선순위 큐를 위해 만들어진 자료구조

• 완전 이진 트리 형태를 띄고 있으며, 반정렬 상태(느슨한 정렬 상태)를 유지하고 있다.

• 반정렬 상태를 통해 최대값이나 최소값을 찾아내는데 매우 빠르다.

• 배열을 이용해 구현

• 반정렬 상태를 유지하기 위해 삽입, 삭제에 특정 알고리즘이 사용된다.

  • 삽입
    1. 새로운 요소를 삽입하기 위해선 먼저 힙의 마지막 노드에 이어서 삽입
    2. 힙의 성질이 만족되지 못하면 부모 노드와 비교, 교환
    3. 이후 힙의 성질을 만족하거나 루트 노드에 다다를 때까지 반복
  • 삭제
    1. 루트 노드를 삭제
    2. 마지막 노드를 루트 노드로 이동
    3. 루트에서부터 단말 노드까지의 경로에 있는 노드들을 교환하여 성질을 만족할 때까지 내려감

종류

• 최대 히프 & 최소 히프
  • 최대 히프(max heap): 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
  • 최소 히프(min heap): 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

구조체

특징

• 타입이 다른 여러 데이터들을 하나로 묶은 자료구조
• 타입이 같은 데이터들을 하나로 묶는 배열과는 다름
• 구조체 속 여러 데이터들을 필드(field)라고 한다.
• 대부분의 언어에서는 .(comma)를 통해 구조체 속 필드에 접근

종류

• 자체 참조 구조체
  • 필드 중에 자기 자신을 가리키는 포인터가 한 개 이상 존재하는 구조체
  • 연결 리스트나 트리에서 사용