[자료구조] 비선형구조

자료구조(2) - 비선형구조

자료구조에는 선형구조와 비선형구조가 있다. 자료구조(1)에서 선형구조에 대해 설명했었는데, 데이터를 순차적으로 나열하는 선형구조와 달리 비선형구조는 비선형적인 계층 구조를 나타낸다.

 

트리

• Tree

  • 그래프의 일종으로, 하나 이상의 노드(node)를 가진다. 각 노드는 엣지(edge, branch)로 연결된다.
  • degree(차수) : 부속 트리의 개수 level(레벨, 깊이) : 루트노드로부터의 깊이 (루트노드의 level = 1)
  • Parent node(부모 노드) : 노드 A가 B를 가리킬 때 A를 B의 부모 노드라고 한다. Child node(자식 노드) : 노드 A가 B를 가리킬 때 B를 A의 자식 노드라고 한다. Sibling node(형제 노드) : 부모가 같은 노드
  • Root node(뿌리 노드) : 최상위 노드로 부모 노드가 없는 노드 Leaf node(잎 노드), Terminal node(단말 노드) : 자식 노드가 없는 노드로 차수가 0이다. Internal node(내부 노드) : 잎 노드가 아닌 차수가 1 이상인 노드
  • Sub tree : 트리 안에 존재하는 부속트리
  • 한 노드는 여러 노드를 가리킬 수 있지만, 여러 노드가 한 노드를 가리킬 수는 없는 구조이다. 따라서 루트노드를 제외한 모든 노드는 단 하나의 부모노드만을 가질 수 있다.
  • 하나의 노드에서 또다른 하나의 노드로 가는 경로는 하나 뿐이어야 한다.
  • 다른 노드와 연결되지 않는 노드는 없다.

 

• 이진트리(Binary tree)

  • 자식 노드의 수가 최대 2개인 트리이다.

• 포화 이진트리(정이진트리, Full binary tree)

  • 모든 레벨에서 노드가 꽉 차있는 이진트리이다.
  • Leaf node를 제외한 모든 노드가 자식 노드를 2개 씩 가진다.
  • 노드수가 n개일 때, Leaf 노드의 수는 n/2를 올림한 수가 된다.
    

• 완전 이진트리(Complete binary tree)

  • 모든 레벨이 꽉 찬 상태는 아니지만, 마지막 레벨을 제외한 모든 레벨의 노드가 꽉 채워진 이진트리이다.

• 균형 이진트리(Balanced binary tree)

  • 모든 Leaf node의 깊이 차이가 1 이하인 이진트리이다.
  • 예측 가능한 깊이(predictable depth)를 가지며, 노드가 n개일 때 깊이는 log ⁡n을 내림한 값이 된다.

• 트리 순회(Tree traversal)

  • 트리의 모든 노드를 중복없이 한 번 씩만 방문해서 순회하는 과정

  • 전위 순회(pre-order)

    • 루트 - 왼쪽 서브트리 - 오른쪽 서브트리 순으로 방문하는 방법

  • 중위 순회(in-order)

    • 왼쪽 서브트리 - 루트 - 오른쪽 서브트리 순으로 방문하는 방법

  • 후위 순회(post-order)

    • 왼쪽 서브트리 - 오른쪽 서브트리 - 루트 순으로 방문하는 방법

  • 각 순회방법의 이름은 루트노드 위치를 생각하면 편하다.

    • 루트를 '먼저' : '전'위 순회(pre-order traversal)
    • 루트를 '중간'에 : '중'위 순회(in-order traversal)
    • 루트를 '마지막'에 : '후'위 순회(post-order traversal)

 

그래프

• Graph

  • 서로 연결된 개체들 간의 관계를 표현하는 자료구조이다. (전기회로, 도로망을 생각해보자.)

  • 트리도 그래프의 일종이기 때문에 트리에서와 같이 그래프도 node와 edge로 구성되는데, 그래프에서 node는 정점(vertex), 간선인 edge는 arc라고도 부른다.

  • G(V,E)로 표시한다.

    • G : graph
    • V : vertex
    • E : edge

  • 자기 자신을 가리키는 간선은 없다.

  • 정점 a, b를 연결하는 간선 (a,b)가 있으면, 정점 a는 정점 b에 인접(adjacent)하며, 간선 (a, b)는 a와 b에 부속(incident)된다.

• 경로(path) : 정점 a 에서 b로 가는 경로

  • 단순 경로(simple path) : 처음과 마지막을 제외하고 정점이 모두 다른 경로로, 경로상의 정점이 중복되지 않는 경로이다.
  • 사이클(cycle) : 단순경로 중 처음과 마지막 정점이 같아 경로가 다시 원점에 도달하는 경우의 경로이다.
  • 정점 a에서 정점 b로 가는 경로가 있는 경우 a와 b는 연결되어있다(connected).

• 차수(degree) : 간선에 의해 연결된 정점 개수

  • 진입 차수 : 외부에서 들어오는 간선의 수
  • 진출 차수 : 외부로 나가는 간선의 수

• 무방향 그래프(undirected graph)

  • 두 버텍스를 연결하는 아크의 방향이 없는 그래프이다.
  • 양방향으로 이동이 가능하다.

• 방향 그래프(directed graph, di-graph)

  • 방향이 있는 그래프이다.
  • 아크를 통해 한 쪽 방향으로만 이동할 수 있다.

• 완전 그래프(complete graph)

  • 모든 버텍스가 연결된 최대 간선 수를 가지는 그래프이다.
  • 무방향그래프 : 버텍스가 n개일 때 아크 수는 n(n-1)/2
  • 방향그래프 : 버텍스가 n개일 때 아크의 수는 n(n-1)

• 가중 그래프(weight graph) = network

  • 아크에 가중치(cost, weight)를 할당한 그래프이다.
  • 가중그래프에서 최단 경로는 모든 경로 중 가중치 합이 최소가 되는 경로이다.

• 다중 그래프

  • 두 버텍스 사이에 두 개 이상의 아크가 존재하는 그래프이다.

• 부분 그래프

  • 버텍스의 집합 V(G)와 엣지의 집합 E(G)의 부분집합으로 이루어진 그래프이다.

• 그래프 탐색(Graph traversal)

  • 깊이우선탐색 DFS(Depth First Search)

    • 트리의 전위순회
    • 내려갈 수 있는 데까지 내려가다가 더 내려갈 곳이 없으면 다시 이전 위치로 나와서 다른 길로 다시 내려가는 방식이다.

  • 너비우선탐색 BFS(Breath First Search)

    • 트리의 레벨순회
    • 깊이가 1인 모든 정점을 방문하고, 그 다음으로 깊이가 2인 모든 정점을 방문하고, 그 다음으로 깊이가 3인 모든 정점을 방문하는 식으로 계속 내려가다가 마지막 레벨의 모든 정점을 방문한 후 탐색이 종료된다.