Software blog

Selection algorithms

• Definition
  • 주어진 도메인 안에서 i번째 작은 수(또는 큰 수)를 찾는 것.
• Quick sorting시 pivot 선정에서 worst case avoidance로 쓰임 (n시간 안에 정확히 중간 값을 찾기 때문에)
• types
  • Average linear time
    • 알고리즘 복잡도, 평균 O(n), worst case O(n²)
  • Guarantee average linear time in worst case.
    • O(n)

     

     

Average linear time selection

• How to
  • endIdx를 pivot으로 하여 파티션을 나눔
  • 파티션 때 pivot의 랭킹(몇 번 째 순위의 숫자인가)이 정해짐.
  • 랭킹이 적절하지 않으면 해당 값의 좌 우로 recursion
• Pseudo

  //

  //        array, 입력배열

  //        startIdx, 배열의 시작 index

  //        endIdx, 배열의 끝

  //        i, i번째 작은 인덱스를 찾음.

  //

  Select(array, startIdx, endIdx, i)

  if startIdx = endIdx

  return array[p]

     

  //

  //        quick sorting과 마찬가지로 partition을 나눔.

  //

  partIdx := partition(array, startIdx, endIdx)

  rankNum := partIdx - startIdx + 1

  if i = rankNum

  return array[partIdx]

  else if i < rankNum

  return Select(array, startIdx, partIdx - 1)

  else

  return Select(array, partIdx + 1, endIdx)

     

     

• Example
  • 2번째 작은 값을 찾을 때.
  • 

Median finding algorithms

• Deterministic Selection algorithms
• K번째 작은 값을 O(n)안에 찾아냄.
• Divide and Conquer 전략을 사용하며 작은 단위로 구분하여 런 타임 시간을 현저하게 줄임
• How to
  • 주어진 배열의 사이즈가 특정 숫자 크기(주로 5를 사용)보다 작은 경우면 단순히 sorting 하고 K번째 값을 return.
  • 주어진 숫자만큼의 element를 가지는 배열로 그룹화.
  • 각 그룹을 sorting하고 각 그룹의 median 값을 찾음.
  • 그 중에서 median 값을 구함.
  • 전체 element를 뒤지면서 찾은 median값 보다 작은 set을 L로 큰 set은 R로 구분하여 정리.
  • 정리된 set의 사이즈를 k와 비교하여 k원소가 있을 set에서 다시 recursion
• Pseudo

  FindingMedian(array, k)

          if array.size < k

                  sort(array)

                  return array[k]

            

          group(array, subsets)

            

          loop i := [0, array.size / 5)

                  medianSets[i] := FindingMedian(subsets[i], 3)

            

          //

          //        group.size = array.size / 5

          //        median of median group.size / 2

          //

          medianVal = FindingMedain(medianSets, array.size / 10)

            

          partition(array, LSet, Rset, medianVal)

          if k < LSet.size

                  return FindingMedian(LSet, k)

          else if k LSet.size + 1

                  return FindingMedean(RSet, k - LSet.size - 1)

          else

                  retrun medianVal

   

• Example
  • Element를 5이하로 가지는 그룹을 생성하는 step
     
  • 
  • Sorting후 median들을 정리 하는 단계
     
  • 
  • Median중에서 median을 선택한 단계.
     
  • 
  • Median of median으로 구분된 배열을 형성하는 단계
     
  • 

       

AVL Tree

• 정의
  • 오른쪽과 왼쪽의 서브트리 중 어떤 노드이던 간에 그 차이가 항상 1을 넘어 가지 않는 B 트리
  • 그런 이유에서 height balanced tree라고도 불림.
• Adelson-Velskii and Landis에 의해 고안
• R-B Tree랑 비교가 많이 되는 편임
  • 같은 일고리즘 복잡도 O(lnN)에 동작을 하기 때문에 비교가 많이 되는 편임
  • R-B 트리 보다 Look-up 수행이 좋음.
    • Red-Black tree는 back의 depth가 같은 것만을 보장 하기 때문에 depth 차이가 2가 날 수 있음.
• Balanced factor
  • Right sub-tree의 height에서 Left-height을 뺀것.
  • 음수 값일 경우 Right rotation
  • 양수 값일 경우 Left rotation (물론 pivot에 따라 다름.)

       

Insertion operation

• Unbalanced tree와 동일하게 삽입함, 물론 order는 지켜져야 함
• balanced factor의 절대치가 1일때는 괜찮지만 2가 되면 rotation 해야 함.
• Rotation
  • Single rotation
    • Left-Left 또는 Right-Right case
    • balanced factor가 negative이면 left로 Rotation, positive이면 right로 rotation.
  • Double rotation
    • Left-right, Single Left rotation하여 Left-left로 만든 다음 single right rotation
• 

     

Red-Block Tree

Overview

• R-B Tree는 기본적으로 2-3-4 Tree와 동일하다.
• 단지 binary tree로 2-3-4의 multi-way 노드에 해당하는 operation을 시뮬레이션 한다.
• 시뮬레이션을 하기 위해 알아두면 편리한 R-B Tree 제약사항
  • Node는 Red 또는 black이어야 한다
  • Root는 black이어야 한다
  • 모든 leaf는 black이어야 한다.
  • Red의 child는 black이어야 한다.
  • leaf의 descendant 노드까지 path에 black 노드의 개수는 모두 동일하다.

Equivalents

• black 은 2-3-4에서 실제 parent와 child관계
• red로 엮인 것들은 모두 한 노드에 있는 key들을 시뮬레이션 하는 것
• back은 실제 edge를 시뮬레이션 하는 것.
• 

     

• 

Red black representation

• 4 node
  • Middle을 중심으로 Red로 연결
  • Red의 부모가 black이어야 하는 이유는 최소한 노드 시뮬레이션상 하나의 중심축이 되는 노드는 존재 해야 하므로

    

• 3 node
  • 

Splitting

• 4 node
  • Color change를 통해서 splitting
  • Color가 바뀌는 것은 Middle key가 상위로 Migration되고 서로 red edge로 연결 되어 있던 하나의 n-ary 노드가 분리 되는 것을 시뮬레이션.
  • 
• 부모가 2node인 4node splitting
  • 해당 black node(edge)를 기준으로 아래 위 다 변경
  • 이유는 해당 black node가 middle key였는데 이를 상위로 Migration하면서 색상이 변경되고 splitting되어 새로운 edge가 생기는 것을 시뮬레이션 하기 위해 연결 되어 있던 red를 black으로 변경.
  • 
• 부모가 3노드인 4노드 splitting
  • 부모가 3노드 라는 것은 시뮬레이션을 통해서 2개의 key를 최소한 2개의 노드로 구성 했기 때문에 Color change이외에 부모 중에 red로 묶여 있는 노드의 rotation이 생길 수 있음
  • 

       

  • 

Observation

• 2-3-4Tree에서는 모든 leaf가 동일한 레벨에 있기 때문에 어떤 리프 노드까지의 path라도 동일한 edge수를 가짐
• R-B Tree에서는
  • 어떤 leaf 노드라도 모든 black edge(black node)의 수가 동일함.
    • back edge는 실제 edge를 시뮬레이션 한 것이기 때문에 같을 수 밖에 없음
    • 다만, binary tree로 표현된 R-B트리 에서 봤을 때 height이 2가 날 수 있음
  • Red edge(node)는 black edge의 개수보다 많을 수가 없음
    • Red edge는 n-ary 구조의 Key를 에뮬레이션 한 것이기 때문에 edge인 back 보다 많을 수가 없음.

       

Overview

• Disk와 같은 block device에 Search tree가 저장 되어 있을 경우 가장 유용함
• B-Tree는 Multi-way tree의 balance를 최대한 유지하도록 하고 height를 최소화 하여 블록 디바이스에 접근을 최소화 하도록 한다.
• Multi-Way Search Trees, N-ary 라고도 함.
• 

B-Trees

• Balanced 멀티웨이 서치 트리는 아래와 같은 사항을 만족 해야 함
  • 필드에 key가 K개 까지 지원 할때 루트를 제외한 모든 노드는 Ceiling(k/2) 개 부터 K개 까지 만 가질 수 있다.
    • Ceiling(k/2) 보다 작은 경우를 under flow하고
    • K개보다 많은 경우를 Overflow라고 한다.
  • 모든 leaf 노드는 같은 depth를 가진다.
• Insertion operation
  • Order 위치에 맞는 노드를 찾아서 삽입함
  • 만약 오버플로우가 발생하면 오버플루우를 클리어한다.
    • Sibling Node에 key가 오버플로우 되지 않을 여유가 있으면 Redistributing
    • Sibling들도 모두 오버플로우가 될 경우면 splitting
      • splitting, 노드를 둘로 분할 하고 Middle Key를 부모로 Migration 하는 것임.
    • splitting시에 부모도 오버 플로우가 생기면 propagation

    

       

    

       

    

       

    

       

    

• Deletion Operation
  • 삭제 할 대상을 찾는다
  • 삭제 할 대상의 노드가 leaf가 아닐 경우는 successor와 swap하여 해당 key가 leaf에 위치 하도록 임시 변경한다.
  • leaf에서 해당 key를 삭제 하고 이 노드에서 언더플로우가 발생할 경우 아래와 같은 절차를 따른다.
    • Sibling node가 여분의 키를 가지고 있다면 Redistributing
    • Sibling node도 모두 언더플로 바로 전 노드라면 여기서는 sibling node와 merge

      

         

      

         

      

         

Complexities

Hash Table

• Element가 저장될 장소가 elem의 값에 의해서 결정되는 자료 구조임
• collision이 없다고 가정하면 상수 시간 안에 Insertion, Deletion, Searching이 가능함
• Hash table은 order에 의한 search(예를 들면 최소 원소, K번째 원소)를 지원 하지 않음.
• 

Hash function

• Collision을 최대한 피하도록 입력 elem이 hash table에 최대한 골고루 흩어져야 한다.
• 매 삽입과 삭제 시 이용 되므로 계산이 간단해야 한다.
  • 가장 많이 사용되는 hash function
    • Division method
      • h(x) = x mod m
      • m은 대부분 테이블 사이즈 이면서 소수임.
    • Multiplication method
      • h(x) = (x * A mod 1) * m, 단 A는 0 < A < 1인 상수
      • m은 굳이 소수 일 필요가 없으므로 보통 2의 승수로 잡는다.
      • 

Collision

• Hash table을 한 주소에 넣고 두 개 이상의 주소가 race를 하게 되는 경우

  

• Collision solution
  • Channing
    • 같은 주소로 해싱 되는 경우 collision이 나는 원소들을 모두 하나의 linked list로 관리함
    • 추가적인 링크드 리스트가 필요해짐
    • 
  • Open Addressing
    • Collision이 일어 나더라도 어떻게든 현재 주어진 테이블 공간 안에서 해결 하도록 한다.
    • 추가적인 공간이 필요 없다.
• Open Addressing
  • 빈자리가 생길 때 까지 해시값을 계속 만들어 내는 구조
    • 반복 될 때 마다 i값을 변경해서 hash function에 적용
    • h0(x), h1(x), h2(x)….
  • 해시 값을 계속 만들어 내는 방법
    • Linear probing
      • 반복 될 때 마다 해시 값에 반복 횟수를 더해서 적용함.
      • 다음 collision이 날 때마다 다음 엔트리로 try하는 기법(선형)
      • h_i(x) = (h(x) + i) mod m
      • 
      • 문제점은 Primary clustering(특정 영역에 원소가 몰리는 현상)이 생긴다는 것.
        • 
    • Quadratic probing
      • collision이 생길 때 마다 더 멀리 있는 entry를 참조하도록 함
      • h_i(x) = (h(x) + c₁i² + c₂i) mod m
      • 
      • Quadratic Probing은 해시의 초기 값들이 겹치는 세컨더리 클러스터링에 약하다.
        • 
    • Double hashing
      • 해시 함수 두 개를 사용하여 해시 값들을 collision시 분산 시키는 것
      • h_i(x) = (h(x) + i f (x)) mod m
      • 
      • 삭제 시 collision되어 들어갔던 다른 원소가 dangling 되는 경우가 생기므로 항상 삭제 표시를 하도록 한다.
      • 

           

Kruskal Algorithm

• Greedy Algorithms
• complexity
  • worst case, O(n²*log₂n)
  • average O(n²)
  • O(|E|log|V|)
• 가중치가 낮은 순서대로 edge를 sorting하여 낮은 edge부터 선택함.
• 서로소인 부분집합의 두 vertex가 연결 되는 경우는 이를 합치고 promising Set에 추가 하는 방식
• F = {공집합}

  Edge들은 가중치로 sorting.

  V의 서로 소 부분 집합 구축

  E에 속한 이음선을 가중치가 작은 것부터 차례로 정렬

  loop 모든 부분집합이 하나로 합쳐질 때 까지

  if 서로 소 부분집합의 두 접점 연결 // feasibility check

  두 부분집합을 합침.

  Edge를 F에 추가.

  

     

  

Shortest Paths

• Dijkstra Algorithms
  • Promising Group의 Starting vertex로 부터 unvisited vertex로 가는 distance가 가장 작은 것을 선택하여 Promising group에 넣음
  • Promising group외부에 unvisited vertex가 없을 때 까지 반복
  • Prim과 다른 것은 distance를 선택하며 각 단계에서 distance를 relaxation 하는 단계가 있다는 것임.
  • 

       

  • 
  • Edge의 합이 Negative cycle이 있으면 문제를 해결 할 수 없음.
  • Complexity
    • O(|E|log|V|)

         

• Single start-vertex
  • 단일 시작점으로 부터 각 vertex의 최단 경로를 구함.
  • 다익스트라
    • Negative cycle을 허용 하지 않는 특징
  • 벨만 포드
    • Negative cycle을 허용
• 모든 쌍 최단 경로
  • 플로이드- 워샬 알고리즘.

Bellman-Ford algorithms

• Θ(|E||V|)
• 동작 방식
  • 모든 vertex의 Distance를 모두 infinite를 세팅
  • Starting Vertex의 distance를 0으로 세팅
  • Edge를 1개만 사용하는 Path의 각 vertex의 distance를 계산, 새로운 distance가 기존 distance값보다 작으면 relaxation.
  • Edge를 n-1개 까지 사용하는 path의 각 vertex의 distance를 계산.
• void negativelyWeightedSSSP(int s, int[] dist)
  {
          for (v = 0; v < n; v++)
                dist[v] = INFINITY;
          Queue q = new Queue(n);
          dist[s] = 0;
          q.enqueue(s);
          while (q.notEmpty())
         {
                v = q.dequeue();
                for (each neighbor w of v)
                if (dist[w] > dist[v] + weight[v, w]) // shorter path
               {
                     dist[w] = dist[v] + weight[v, w];
                     if (! q.isInQueue(w))
                     q.enqueue(w);
                }
          }
  }

• 

Floyd-Warshall Algorithms

• Θ(|V|³)
• Principle of optimal을 이용하여 모든 vertex 사이에 상호 최단 경로를 구한다.
  • Principle of optimal은 어떤 문제에 대한 case가 그 case를 분할한 case에 대한 optimal solution을 항상 포함하고 있으면 그 해는 optimal이다.
  • 
• 네비게이션이나 네트워크 커뮤니케이션에서 응용된다.
• FloydWarshall()

  loop k := [0, v.count)

  loop i:= [0, v.count)

  loop j:= [0, v.count)

  distance[i,j] := min ( distance[i,j], distance[i,k] + distance[k,j])