Software blog

Topological Sorting

• Condition
  • 사이클이 없는 Directed Graph
• Topological order
  • x로 부터 y로 가는 edge가 있다면 vertex x가 y보다 선행하는 vertices의 오더를 가짐
  • 일반적으로 directed 그래프는 많은 토폴로지컬 오더를 가진다.
  • Θ(|V|+|E|)

       

  • 
  • Order를 순서를 정하는 방법
    • Successor가 없는 vertex를 선택하여 sorting container에 넣음
    • 해당 vertex와 edge를 삭제하고 다시 Successor가 없는 vertex를 선택하는 과정을 반복
    • Graph의 원소가 없어질 때 까지 반복함.
    • 결과적으로 sorting container는 topological order를 가지게 됨.
    • 
  • Pseudo code.
    • TopologicalSort(v)

      loop v := [0, v.size)

      v.visit := False        // init

      loop v := [0, v.size)

      if v.visit = False

      DFS-TS(v)

         

      //

      //        successor가 없는 노드 까지 내려 가서 list header부터

      // 차곡차곡 채워 올라오는 알고리즘.

      //

      DFS-TS(v)

      v.visit := True

      loop x := v.adjacent

      if x.visit = False

      DFS-TS(x)

      list.insertheader(v)                // 연결 리스트 맨앞에 넣음

  • 

       

  • 

       

  • 

Spanning Trees

• 그래프 G의 모든 vertex를 다 담고 있는 subgraph로서의 트리
  • Tree
    • 사이클이 없는 Connected graph
    • n개의 vertices를 가지고 있다면 edge는 항상 n - 1임.
  • 단, 그래프 G는 Undirected connected graph
  • 

MST, Minimum Spanning Tree

• 모든 edge의 weight의 합이 최소인 Spanning Tree
  • 단, 그래프 G는 Weighted connected graph임
• Create Algorithms
  • Prim
    • Minimum spanning tree를 찾는 Greedy algol.
    • G = (V,E)

      T = (V,F)

      F = {x | F is subset of E}

      Y = {y | Y is subset of V}, Minimum spanning tree를 구성하는 edge로 promising 하다고 이야기 함.

         

      loop Y=V

      V-Y로 가는 edge중 가장 cost가 작은 edge를 선택.

      선택된 egde의 vertex는 Y에 삽입.

      edge는 F로 삽입.

      - complexity

      • O(E*V)
      • O(E*lnV), 힙을 사용할 경우.
  • 다시 말해서 MST가 되는 Promising set에 포함되지 않은 unvisited vertex중에서 가장 작은 weight를 가지는 edge랑 vertex를 선택하여 promising group에 넣는 과정을 반복.
  • 

       

  • 

       

  • 

       

  • 

Shortest Paths

• Condition
  • Weighted Graph
  • Undirected 그래프의 경우 양방향성을 가진 것으로 생각 하여 생각 할 수 있음.
• edge의 weight 합이 최소가 되는 path
• Dijkstra Algorithms
  • Promising Group의 Starting vertex로 부터 unvisited vertex로 가는 distance가 가장 작은 것을 선택하여 Promising group에 넣음
  • Promising group외부에 unvisited vertex가 없을 때 까지 반복
  • Prim과 다른 것은 distance를 relaxation 하는 단계가 있다는 것임.
  • 

       

  • 

Euler Circuit

• 오일러 경로
  • 그래프의 모든 edge를 한번씩만 통과하는 path를 이야기 함.
  • 필요 충분 조건
    • 두 개의 vertex만이 홀수개의 degree를 가진 Connected 그래프이어야 함.
• 오일러 회로
  • 오일러 경로 중에서 시작 vertex와 끝이 나는 vertex가 동일한 path
• 오일러 그래프
  • 오일러 회로를 가지고 있는 그래프.

Graph traversals

• DFS
• BFS

Application of Graph

• Topological Sorting
• Spanning Tree
• Shortest paths

Definition

• Graph G = (V,E)
  • Vertex와 Edge들의 집합.
• Sub-graph
  • 그래프의 Vertex, Edge들의 subset
  • 
• Adjacent
  • 두 개의 Vertex가 edge로 연결 되어 있으면 Adjacent하다고 이야기함.
• Path
  • 연결된 Edge들의 sequence.
• Cycle
  • Starting vertex와 Ending vertex가 동일한 path
• Simple path
  • 사이클이 없는 path
• Simple cycle
  • 사이클 내에 사이클이 없는 것.
• Connected graph
  • 서로 다른 어떤 vertex 사이라도 path가 존재하는 graph
  • 
• Complete graph
  • 서로 다른 어떤 vertex 사이라도 edge가 존재하는 graph
• Directed graph (digraph)
  • 방향성을 가진 그래프
  • 
• Weighted graph
  • edge가 가중치를 가진 그래프.
  • 

DFS, Depth First Search

• 특징
  • 깊이를 우선적으로 하기 때문에 backtracking 할 수 있는 stack 자료 구조가 필수임.
  • stack에 넣으면서 계속 adjacent node를 방문하며 따라감.
• 검색 방법
  • DFS(v)

    v->visit := true

    stack.push(v)

       

    loop stack.isEmpty() = false

    if top.adjacent->visit = false

    top.adjacent->visit := true

    stack.push(top.adjacent)

    else

    top := stack.pop()        // backtraking

• 

BFS, Bread First Search

• 특징
  • 너비를 우선적으로 탐색 하기 때문에 queue의 자료 구조가 필수임
  • Adjacent가 있으면 무조건 queue에 넣으면서 방문함.
  • Adjacent가 없으면 queue에서 하나를 꺼내어 위의 과정을 반복.
• 검색 방법
  • BFS(v)

    v->visit        := true

    queue.enqueue(v)

    loop qeuue.isEmpty = false

    head = qeuue.dequeue()

    loop head.adjacent != nuill        // each vertex

    head.adjacent->visit := true

    queue.enqueue(head.adjacent)

• 

     

• 

     

2-3-4 Tree

• form
  • 
  • T1,T2,T3,T4 모두 2-4 Tree이며 r의 필드가 3보다 작은 경우에 T3과 T4는 없을 수도 있음.
• 조건
  • 각 인터널 노드는 2,3,4 개의 Children을 가짐
  • 모든 leaves는 같은 레벨에 있어야 함
  • 각 노드의 필드는 1,2,3 개 안에 있어야 함.
• Order 특성
  • 
• Insertion operation
  • 4 번째 필드를 가지는 노드를 만나자 마자 무조건 split함.
    • 이 부분이 2-3 tree와 가장 다른 점임.
    • 2-3 tree는 3개 필드를 가지는 노드를 만들고 split을 하지만 2-4는 아님.
  • 2-4에서는 이러한 특성 때문에 항상 부모 노드가 하나의 key를 더 받아 들일 수 있음
  • Splitting
    • 각 노드에서 splitting은 Middle 노드를 parent로 migration하고 order순에 맞게 children을 재분배 하는 과정을 거침.
    • Splitting 4-node root
      • 
    • 4 node splitting에 의해 부모가 2 node 가 되는 경우
      • 
    • 4 node splitting에 의해 부모가 3 node 가 되는 경우
      • 
• Delete operation
  • Description
    • 2-3 Tree와 유사
      • 삭제할 대상이 되는 노드를 찾음
      • leaf가 아니라면 successor와 swap 한 후에 삭제
    • leaf가 3,4노드이면 간단히 아이템을 삭제 가능
    • Delete operation을 간단히 하기 위해서 2 노드를 3이나 4노드로 트랜스폼하는 과정이 필요.
  • Transformation
    • Middle fields를 하위 노드로 이동시키고 하위 노드에 붙어 있는 노드들은 order를 깨지 않도록 분배함.
    • 

         

    • 

         

    • 

         

2-3 Tree

• 2-3 Tree의 모든 노드는 2개의 child를 가지는 하나의 element의 노드이거나 3개의 child를 가지는 두 개의 데이터 element를 가지는 노드임.
• Property
  • 모든 Non-leaf 노드는 2개 또는 3개의 child 노드를 가진다.
  • 모든 Non-leaf 노드는 1개 또는 2개의 필드를 가지고 있다.
  • 모든 leaves는 같은 레벨에 있다.
  • 모든 데이터는 sorted order에 유지된다.
  • 
• After insert operation
  • Splitting a leaf
    • 3개의 필드를 가지고 있는 노드에서 Middle값을 상위 노드의 필드로 Migration하여 2개의 leaf로 분리.
    • 
  • Splitting an internal node
    • 3 개의 필드를 가지는 경우, 이를 분리하여 정의에 맞추어 주어야 하므로 Middle을 상위 노드로 이전하고 Middle의 child들을 남은 Small, Large 필드의 child로 재구성
    • 
  • Splitting the root node
    • Middle을 통해서 New root 노드를 생성하고 나머지 child는 Internal node의 splitting 과정과 동일하게 진행함.
    • 
• After delete operation
  • leaf-node가 아닌 경우에는 In-order successor와 swap한 뒤에 leaf로 만들고서 delete.
  • leaf 노드를 삭제하고 나서 Internal node가 2-3의 조건을 만족하지 못하게 되는 경우 재분배 또는 합병과정을 거치게 됨.
    • Redistributing values
      • 삭제된 node의 sibling을 재분배하여 삭제 되고 나서 비게 된 leaf 노드를 채운다.
      • 만약 삭제된 노드가 Internal 노드라면 Distributing을 통해서 child 또한 2-3 조건에 만족 되도록 재구성 되어야 함.
    • Merging
      • Distributing이 불가능 한 경우 하나의 노드를 merge를 통해서 만들어냄.
      • Merging에서도 마찬가지로 Internal node의 merge가 있었다면 child 또한 Merge가 되어야 함.
    • 

         

    • 
    • Root 가 삭제 된 것이라면 단순히 Height 하나만 줄어 듬.
      • 

           

Traversal of Binary Tree

• Traversal 알고리즘은 트리내에 있는 모든 노드를 방문 함
• Binary Tree의 traversal 알고리즘은 아래 3가지
  • Preorder traversal
    • Root 부터 mark하고 subtree를 탐색 하는 방식
  • Inorder traversal
    • Visit 할 leftchild가 없을 때의 노드를 mark하는 방법으로 모든 노드를 left -> right 순으로 탐색
  • Postorder
    • Visit 할 Right-child 가 없을 때의 노드를 mark하는 방법.
• 

     

  BST의 효율성

  • 

     

Full Tree Properties

• Node 수
  • height h를 가질 때 노드는 2^h - 1을 가짐.
  • 세로가 2이고 가로가 lead 노드 수인 사각형 면적 - 1 과 Full binary tree의 노드 수는 같음.
  • Binary Tree가 차면 Full tree가 되므로 Binary Tree의 최대 노드 수도 2^h - 1
  • node수를 induction으로 증명

    base condtion                : 2^0 = 1 <= root임으로 증명

    inductive hypothesis        : 2^h - 1

    inductive step

    if h = k

    1+2+ .... + 2^(k-1) = 2^k - 1

    if h = k + 1

    1+2+ .... + 2^(k-1) + 2^k        = 2^k - 1 + 2^k        // 2^k 좌항, 우항에 k+1 번째 leave수를 더함.

    = 2^k + 2^k - 1

    = 2*2^k - 1

    = 2^(k+1)-1

       

• Leaf node 수
  • 2^{(h - 1)} 임.
• Non-lead node 수
  • non-leaf node의 수는 전체 node수에서 leaf 노드 수를 제외 한것.
  • height를 h라고 할때

    total nodes - leave nodes        = 2h - 1 - 2(h-1)

    = 2 * 2(h-1) - 2(h-1) - 1

    = (2-1) * 2(h-1) - 1

    = 2(h-1) - 1

    * 노드 수 계산 하는 식에 h 대신 h-1 넣는것과 일치.

• Edge 수
  • Node가 n일 때 edge는 n-1개를 가짐.
    • 모든 노드는 root를 제외하고 부모로 가는 edge를 하나씩 가지므로
    • 그래서 10개 중에 최소값을 가지는 것을 비교 하려면 n-1번 진행 해야 함.
• Null pointer의 수
  • N + 1개
    • 모든 노드는 2개의 포인터를 가짐.
    • N개의 노드를 가진 트리의 edge수가 n-1개 이므로 총 포인터에서 edge 수를 빼면 null pointer수가 산출 됨
    • 2n - (n -1) = n + 1
• 최소 Height 수
  • Ceiling [Log₂ (n+1) ]
    • h <= n <= 2^h - 1
    • h <= n에 의해 h의 max는 n임.
    • n <= 2^h - 1 // h 관하여 정리
    • n + 1 <= 2^h
    • log2 (n + 1) <= h

Huffman code

• 간단한 data 비교 기법
• 파일에서 각각의 digit의 빈도 수를 비교 하는 것임.

     

Definition of tree

• Acyclic 이면서 Connected Graph임.
• General tree T는 disjoint subset으로 분리가 가능함.
  • Single node R은 Root
  • General tree의 집합은 r의 서브트리임.

Binary Tree

• Tree T는 empty 이거나,
• 3개의 disjoint 서브셋들로 분리 된 것.
  • Single node R은 Root
  • R의 left, right subtree로 불리는 두 개의 바이너리 트리가 있음.

Binary Search Tree

• 바이너리 트리는 각 노드의 값에 따라 소팅 되어 있는 tree임.
• 각 노드 n은 아래와 같은 조건을 만족함.
  • N은 Left subtree의 모든 값들보다 큼.
  • N은 right subtree의 모든 값들 보다 작음
  • Left tree, right tree모두 바이너리 서치 트리임.

Height of a tree

• Root부터 leaf 노드에 이르는 가장 긴 길이의 path에 노드 구성 수.
• 

Full binary tree

• Tree T가 empty이면, T이는 height가 0인 full binary tree임.
• Tree T가 empty가 아니고 height h를 가지고 있다면
  • Root의 양쪽 서브트리는 height h -1을 가지는 full binary tree임.
• => every node has no child or 2 child and all leaves is same level.

Complete Binary Tree

• Height h를 가진 Complete Binary Tree는 바이너리 트리이면서 아래의 사항을 만족함.
  • Complete Binary tree는 h -1 까지는 full이면서
  • level h는 left부터 right순으로 노드가 채워진(Leftmost) tree
• => leaf는 left most(left to right)를 가지면서 leaves간의 level 차이가 1 이하임.
• 

Array based representation

• General tree
  • 
• Complete binary tree
  • 컴플릿 바이너리 트리가 배열로 표현하기 가장 좋음.
  • 힙이 일종의 Complete binary tree로 heap sort시 자주 쓰이는 배열 구조
    • Left child = node index * 2 + 1
    • Right child = node index * 2 + 2
    • Parent = node index - / 2, 소수점 이하 버림.
  • 

BST의 Operation ADT

• Insert
  • Root부터 값을 비교 해가며 탐색, leaf node가 비어 있는 제자리 위치를 찾으면 삽입
  • 중간 Node로 삽입 되는 케이스는 없음.
  • 
• Delete
  • 유일하게 tree의 중간 노드에서 변화가 생기는 경우
  • 삭제 되는 대상 노드가 leaf일 때는 단순 삭제
  • Child가 하나만 있을 때는 삭제 하고 빈 노드 공간을 Child노드로 repalce
  • 중간 노드일 때는 아래와 같이 동작.
    • 삭제되는 값과 가장 가까운 큰 값을 선택하여 삭제되는 곳으로 replace.
      • 삭제되는 값과 가장 가까운 큰 값은 오른쪽 Subtree중에서 제일 left에 있는 노드
      • 제일 left에 있는 노드라는 것은 tree 탐색 시 leftchild를 가지지 않은 노드임
    • Replace 전에 우측에 있는 subtree는 교체 되는 노드의 위치에 삽입
      • 이 subtree의 노드들은 Replace 되는 노드보다 값은 크지만 그 노드의 부모보다는 값이 작은 것이므로 부모의 left(즉, replace 되는 노드의 자리)에 위치 하는 것이 맞음.
    •