컴퓨터과학 개론 04 - 자료구조(2)

해당 포스트는 강의를 수강 후 개인적으로 이해한 부분을 글로 기록하고 해석하기 위한 목적으로 이해한 부분이 틀릴수도 있습니다. 잘못 이해하고 있거나 틀린 부분에 대해서는 편하게 지적해 주시면 수정하겠습니다.

1. 트리

1. 개념

   • 데이터 간 관계를 나타내는 비선형 자료구조
   • 노드(Node)와 노드를 연결하는 가지(Branch, Edge)로 구분
   • 노드 사이에는 계층적인 관계성을 갖음
     
   
   
   • 노드(Node): 정보 항목을 의미함
   • 루트(Root): 빈 트리가 아닌 경우 가장 최상위층에 있는 하나의 노드
   • 차수(Degree): 각 노드에 있는 가지의 수
     
   
   
   • 잎 노드(Leaf node) = 단말 노드(Termianl node)
     : 노드의 차수가 0인 노드
   • 내부 노드(Internal node) = 비단말 노드(Non-terminal node)
     : 루트 노드와 단말 노드를 제외한 나머지 노드
     
     루트 노드는 잎 노드도 아니고 내부 노드에도 속하지 않는다.
   
   
   • 조상(선조) 노드
     : 루트 노드로부터 어떤 노드 X까지의 경로(가지들의 모음) 상에 존재하는 모든 노드를 X의 조상 노드라고 한다.
   • 자손(후손) 노드
     : 어떤 노드 X에서 단말 노드까지의 경로 상에 존재하는 모든 노드를 자손 노드라고 한다.
     
     위 그림에서 어떤 노드 X를 노드 J라고 가정하면 루트 A부터 경로 상 존재하는 B, E의 노드가 조상 노드, 어떤 노드 X를 노드 D라고 가정하면 D부터 G, H, I, L, M을 자손 노드라고 한다.
   
   
   • 레벨(Level): 루트 노드로부터의 거리(가지의 수)
   • 깊이(Depth)/높이(Height): 루트 노드로부터 최하위 단말 노드의 레벨에 1의 값을 더한 것
     

     레벨은 노드에 부여된 개별적인 값을 의미하고 깊이는 트리 전체에 부여된 값을 의미한다. 따라서 레벨과 깊이의 의미는 차이가 있다.

   
   
   • 서브 트리(Subtree): 특정 노드를 루트 노드로 지정하고 해당 노드와 연결되어 있는 하위 노드들이 연결된 구조
   • 숲(Forest): 루트 노드를 제거하였을 때 얻을 수 있는 서브 트리의 집합
     
   
   

2. 이진 트리, Binary tree

1. 개념
   

• 모든 노드의 최대 차수가 2개인 트리
• 모든 노드의 차수는 2개를 넘지 않아야 한다.
• 모든 노드는 최대 2개의 서브트리를 가진다.
• 각 서브트리는 왼쪽 또는 오른쪽 서브트리로 구분
• 왼쪽 노드와 오른쪽 노드에 순서의 의미를 부여
• 이진 트리의 각 서브 트리는 다시 이진 트리가 된다.

데이터의 값을 순서대로 확인 또는 출력하는 경우도 있지만 노드를 방문하는 순서로도 이해할 수 있다.

2. 이진 트리의 최대 높이

• N개의 노드를 가진 이진 트리의 높이를 계산으로 구할 수 있다.
• 최대 높이: N으로 노드의 개수와 같다.
  

3. 이진 트리의 최소 높이

• 모든 내부 노드가 최대 2개의 자식 노드를 갖는 경우 $[log_2N] + 1$이 높이가 된다.
  

4. 이진 트리 순회 연산

   • 일정한 순서에 따라 트리에 있는 각 노드를 한 번씩 방문하는 연산
     
   
   
   1. 전위 순회(Preorder), DLR(Data-Left-Right)
      • 루트 노드 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리 순서로 순회
        
        위 그림 순서대로 값을 나열하면 ABDHIEJK, B부터 K까지 순서대로 A 노드의 왼쪽 서브트리
        
   
   
   2. 중위 순회(Inorder), LDR(Left-Data-Right)
      • 왼쪽 서브 트리 -> 루트 노드 -> 오른쪽 서브 트리 순서로 순회
        
        왼쪽 서브 트리의 가장 마지막 왼쪽 서브 트리부터 시작한다. 왼쪽 서브 트리 HDIBJEK의 순서대로 데이터를 확인한 후 루트 노드 A를 확인, 오른쪽 서브 트리의 가장 마지막 왼쪽 노드부터 LFMCNGO 순서대로 확인
   
   
   3. 후위 순회(Postorder), LRD(Left-Right-Data)
      • 왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 루트 노드 순서로 순회
        
        왼쪽 서브트리 HIDJKEB, 오른쪽 LMFNOGC, 루트 노드 A의 값을 가장 마지막에 확인

5. 포화 이진 트리, Full binary tree
   

   1. 개념
      • 깊이가 k인 이진 트리 중에서 노드의 개수가 $2^k-1$개인 이진트리
      • 깊이가 k인 이진 트리가 가질 수 있는 노드의 최대 개수는 $2^k-1$개
      • 단말 노드의 개수가 $2^k-1$개
      • 각 레벨에 빈자리 없이 노드를 모두 가지고 있다.
      • 모든 내부 노드들은 2개의 자식 노드를 가진다.

6. 완전 이진 트리, Complete binary tree
   

   1. 개념

      • 트리의 최대 레벨이 k일 때, 레벨 $k-1$까지는 포화 이진 트리를 형성하고, 레벨 k에서는 왼쪽부터 오른쪽으로 채워진 트리
      • 총 노드의 개수가 $2^{k-1}-1$을 초과하지 않고, 포화 이진 트리의 노드 번호에 해당하는 연속적인 번호를 갖는 트리

      최대 k레벨의 노드에서도 왼쪽 서브 트리가 완전히 채워지지 않고 오른쪽 트리에 노드가 채워졌다면 완전 이진 트리가 아니다.

   

7. 경사 이진 트리, Skewed binary tree
   

   • 왼쪽 또는 오른쪽, 한 방향으로만 뻗어 나간 경사 이진 트리
   
   

2. 그래프

1. 그래프, G

   • 정점(Vertex)들의 유한 집합 V와 두 개의 정점을 연결하는 간선(Edge)들의 유한 집합 E로 정의
   • $G = (V, E)$로 표시
     
     
     

   1. 무방향 그래프, Undirected graph

      • 방향성이 없는 간선으로 연결된 그래프
      • 간선끼리 서로 확인할 수 있다.
        
      
      

   2. 방향 그래프

      • 방향성을 가지는 간선으로 연결된 그래프
      • 정해진 방향의 간선만 확인할 수 있다.
        

   3. 그래프의 집합 표현 방법

      1. 무방향 그래프

         $V(G1) =$ {$1, 2, 3, 4$}
         $E(G1) =$ {$(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)$}

      2. 방향 그래프

         $V(G1) =$ {$1, 2, 3, 4$}
         $E(G1) =$ {$<1, 2>, <1, 3>, <1, 4>, <2, 3>, <2, 4>, <3, 4>$}

   4. 용어

      두 정점이 간선으로 직접 연결되어 있으면 두 정점은 인접(Adjacent)해있다고 하며, 두 정점에 인접한 간선은 두 정점에 부수(Incident)되었다고 한다.

      • 인접한다: 정점 간의 관계

      • 부수되었다: 정점과 간선 간의 관계

      • 경로(path): 간선으로 연결된 정점들의 순차적 나열을 의미

      • 경로의 길이: 경로에 포함된 간선의 개수

      • 단순 경로(Simple path): 경로 상에 존재하는 정점들이 모두 다른 경로

      • 사이클(Cycle): 세 개 이상의 정점을 가진 경로 중에서 시작 정점과 끝 정점이 같은 경로, ex) {1, 3, 4, 2, 1}

      • 단순 사이클(Simple Cycle): 시작 정점과 끝 정점을 제외하고 모든 정점이 다른 사이클,
        ex) {1, 2, 3, 3, 2, 1}

      • 두 정점은 서로 연결되었다
        : 두 정점 사이에 경로가 존재한다.

      • 그래프가 서로 연결되었다
        : 무방향 그래프에서 서로 다른 모든 정점들 사이에 경로가 존재함

      무방향 그래프에서 한 정점의 차수(Degree)는 정점에 부수된 간선의 개수이지만 방향 그래프에서 정점의 차수는 진입 차수와 진출 차수로 나뉜다.

      방향 그래프에서 차수

      • 진입 차수(Indegree): 다른 정점에서 해당 정점으로 향하는 간선의 개수
      • 진출 차수(Outdegree): 해당 정점에서 다른 정점으로 향하는 간선의 개수

   5. 그래프의 표현

      1. 개념
         • 그래프의 형태를 인접 행렬(Adjacency matrix) 또는 인접 리스트(Adjacency list)를 이용하여 컴퓨터가 이해할 수 있도록 표현
         • 인접 행렬을 이용하여 n개의 정점을 가진 그래프를 표현하기 위해서는 $n \times n$ 크기의 2차원 배열을 이용함
           
           
      2. 인접 행렬
         • A[i][j]에 값이 존재하면 그래프의 "정점 $v_i$에서 정점 $v_j$ 사이에 간선이 존재함을 의미"하고, A[i][j]의 값은 1로 정한다.

      

      3. 인접 리스트

         • n개의 정점을 가진 그래프를 표현하기 위해 임의 정점 $v_i$를 중심으로 하여 정점 $v_i$에 인접한 정점들을 1개의 연결 리스트로 표현

         

         위 그림에서 그래프는 2와 3을 제외하고 서로 간선을 가지고 있다. 먼저 모든 정점을 가지고 있는 연결리스트가 만들어 지고 각 정점의 노드는 정점 번호와 포인터라는 2개의 필드로 구성된다.

   6. 그래프의 탐색

      • 그래프의 모든 정점을 체계적으로 방문하는 것
      • 깊이 우선 탐색(Depth first search)과 너비 우선 탐색(Breadth first search)가 있다.
      
      
      1. 깊이 우선 탐색(Depth first search)
         • 최근의 방문하지 않은 인접한 하나의 정점을 우선적으로 방문한다.
         • 최종 방문 순서는 구현 방법에 따라 달라질 수 있다.
           
           
      2. 너비 우선 탐색(Breadth first search)
         • 최근의 방문하지 않은 인접한 모든 정점을 모두 방문한다.