탐색

사전

method

일반

• integer size(): 사전의 항목 수를 반환
• boolean isEmpty(): 사전이 비어있는지 여부를 반환

  접근

• element findElement(k): (키, 원소) 항목들의 모음인 사전에 키 k를 가진 항목이 존재하면 해당 원소를 반환, 그렇지 않으면 특별 원소 NoSuchKey를 반환

갱신

• insertItem(k,e): 사전에 (k,e) 항목을 삽입
• element removeElement(k) : 사전에 키 k를 가진 항목이 존재하면 해당 항목을 삭제하고 원소를 반환, 그렇지 않으면 특별 원소 NoSuchKey를 반환

사전 ADT 구현

구현 형태	구현 종류	예	주요 탐색 기법
리스트	무순사전ADT	기록 파일	선형 탐색
	순서사전	일람표	이진 탐색
트리	탐색트리	이진탐색트리, AVL트리, 스플레이 트리	트리 탐색
해시 테이블			해싱

무순사전

Alg findElement(k)

1. l.initialize(i)
2. while(l.isValid(i)){
    if(l.key(i)==k)
        return l.element(i)
    else
        l.advance(i)
}
3. return NoSuchKey

순서 사전

선형 탐색

조기 실패가 보장, O(n)최악 실행 시간

Alg findElement(k)

1. l.initialize(i)
2. while(l.isvalid(i)){
    if(l.key == k)
        return l.element(i)
    else if(l.ket(i)> k)
        return NoSuchKey
    else
        l.advance(i)
}
3. return NoSuchKey

이진 탐색

배열로 구현되었다면 $O(\log{n})$ 시간에 수행
연결리스트로 구현되었다면 이진 탐색으로 얻는 이득은 없다.

Alg findElement(k)

1. return rFindElement(k,0,n-1)


Alg rFindElement(k,l,r)

1. if(l>r)
    return NoSuchKey
2. mid = (l+r)/2
3. if(k == key(a[mid]))
    return element(a[mid])
   else if( k< key(a[mid]))
    return rFindElement(k,l,mid-1)
   else {k > key(a[mid])}
    return rFindElement(k,mid+1,r)

요약

• 사전 ADT는 (키,원소) 쌍으로 구성된 데이터 항목의 집단을 모델링한다.
• 사전 ADT에 대한 주요 작업은 탐색, 삽입 그리고 삭제가 있다.
• 사전 관련 작업에 영향을 미치는 두 가지의 상이한 전제로는 유일 키와 중복 키 두 가지가 있다.
• 기록 파일로 대표되는 무순사전 ADT는 삽입이 빠른 대신 탐색과 삭제가 트린 특성을 가진다. 무순 사전에 대해서는 선형 탐색을 수행한다.
• 일람표로 대표되는 순서사전 ADT는 탐색이 빠른 대신 삽입과 삭제가 느린 특성을 가진다. 순서사전에 대해서는 이진탐색을 수행할 수 있다.
• 배열로 구현된 순서리스트에 대한 이진탐색은 최악의 경우$O(\log{n})$시간에 수행한다.

탐색 트리

이진 탐색 트리

Alg findElement(k)

1. w = treeSerch(root(),k)
2. if (isExternal(w))
    return NoSuchKey
   else 
    return element(w)


Alg treeSearch(v,k)

1. if(isExternal(v))
    return v
2. if(k == key(v))
    return v
   else if(k < key(v))
    return treeSerch(leftChild(v),k)
   else {k > key(v)}
    return treeSearch(rightChild(v),k)


Alg insertItem(k,e)

1. w = treeSearch(root(),k)
2. if(isInternal(w)) - 이건 이미 똑같은게 있다는 것
    return
   else
    Set node w to(k,e)
    expandExternal(w)
    return

삭제

1. 트리 T에 대해 w의 중위순회 계승자 y와 그 자식노드 z을 찾아낸다.

• 노드 y는 우선 w의 오른쪽 자식으로 이동한 후, 거기서부터 왼쪽 자식들만을 따라 끝까지 내려가면 도달하게 되는 마지막 내부노드며, 노드 z은 y의 왼쪽 자식인 외부노드다.
• y는 T를 중위순회할 경우 노드 w 바로 다음에 방문하게 되는 내부노드이므로 w의 중위순회 계승자라 불린다.
• 따라서 y는 w의 오른쪽 부트리 내 노드 중 가장 왼쪽으로 돌출된 내부노드다.

2. y의 내용을 w에 복사한다.
3. reduceExternal(z) 작업을 사용하여 노드 y와 z를 삭제한다.

Alg remoceElement(k)

1. w = treeSerch(root(),k)
2. if (isExternal(w))
    return NoSuchKey
3. e = element(w)
4. z = leftchild(w) - 오른쪽으로 가야 되는거 아닌가?
5. if (!isExternal(z))
    z=rightChild(W) - 이건 왼쪽 아닌가???
6. if (isExternal(z))
    reduceExternal(z)
   else 
    y = inOrderSucc(w)
    z = leftChild(y)
    Setnode w to (key(y),element(y))
    reduceExternal(z)
7. return e

AVL트리

자식들의 좌우 높이 차이가 1을 넘지 않는 이진탐색트리
삽입이나 삭제 작업 후에 불균형이 생길 수 있다.

삽입

Alg insertItem(k,e)

1. w = treeSearch(root(),k)
2. if (isInternal(w))
    return
   else
    Set node w to(k,e)
    expandExternal(w)
    searchAndFixAfterInsertion(w)
    return

Alg searchAndFixAfterInsertion(w)

1. w에서 t의 루트로 향해 올라가다가 처음 만나는 불균형 노드를 z라 하자.
(없으면 return)
2. z의 높은 자식을 y라 하자.
    {수행 후 y는 w의 조상이 되는 것에 유의}
3. y의 높은 자식을 x라 하자
    {수해 후 노드 x가 w와 일치할 수도 있으며 x가 z의 손자임을 유의. y의 높이는 자신의 형제노드의 높이보다 2가 더 많다.}
4. restructure(x,y,z)
    {수행 후, 이제 b를 루트로 하는 부트리의 모든 노드는 균형을 유지한다. 높이균형 속성은 노드x,y,z에서 지역적으로나 전역적으로나 모두 복구된다.}
5. return


Alg restructure (x,y,z)

1. x,y,z의 중위순회 방문순서의 나열을 (a,b,c)라 하자
2. x,y,z의 부트리들 가운데 x,y,z을 루트로하는 부트리를 제외한 4개의 부트리들의 중위순회 방문순서의 나열을 (t0,t1,t2,t3)라 하자.
3. z을 루트로 하는 부트리를 b를 루트로 하는 부트리로 대체한다.
4. t0와 t1을 각각 a의 왼쪽 및 오른쪽 부트리로 만든다.
5. t2와 t3를 각각 c의 왼쪽 및 오른쪽 부트리로 만든다.
6. a와 c를 각각 b의 왼쪽 및 오른쪽 자식으로 만든다.
7. return b

삭제

Alg removeElement(k)

1. w = treeSearch(root(),k)
2. if (isExternal(w))
    return NoSuchKey
3. e = element(w)
4. z = leftChild(w)
5. if (!isExternal(z))
    z = rightChild
6. if (isExternal)
    zs = reduceExternal(z)
   else{
    y = inOrdersucc(w)
    z = leftChild(y)
    Set node w to (key(y),element(y))
    zs = reduceExternal(z)
   }
7. searchAndFixAfterRemoval(parent(zs))
8. return e


Alg searchAndFixAfterRemoval(w)

1. w에서 t의 루트로 향해 올라가다가 처음 만나는 불균형 노드를 z이라 하자 (그러한 z이 없다면 return).
2. z의 높은 자식을 y라 하자.
    {수행 후 y는 w의 조상이 아닌 z의 자식이 되는 것에 유의}
3. y의 두 자식 중 어느 한쪽이 높으면 높은 자식을 x라 하고, 두 자식의 높이가 같으면 둘 중 y와 같은 쪽의 자식을 x로 선택한다.
4. b = restructure(x,y,z)
    {수행 후 높이 균형 속성은 방금 전 z을 루트로 했으나 지금은 변수 b를 루트로 하는 부트리에서 지역적으로 복구된다. 하지만 방금의 개조에 의해 b를 루트로 하는 부트리의 높이가 하나 줄어들 수 있으며 바로 이 때문에 b의 조상도 균형을 잃을 수 있다. 즉, 삭제 후 한번의 개조만으로는 높이균형속성을 전역적으로 복구하지 못할 수도 있다.}
5. t를 b의 부모부터 루트까지 올라가면서 균형을 잃은 노드를 찾아 수리하는 작업을 계속한다.

요약

• 탐색트리를 이용하여 사전 ADT를 구현할 수 있으며 여기에는 이진탐색트리, AVL트리, 스플레이 트리 등의 방식이 있다.
• u, v, w가 이진탐색트리의 노드며 u와 w가 각각 v의 왼쪽과 오른쪽 부트리에 존재할 때 key(u)< key(v) <= key(w) 가 성립한다.
• AVL트리는 트리 T의 모든 내부노드 v에 대해 v의 자식들의 좌우 높이 차이가 1을 넘지 않는 이진탐색트리를 말한다. 이를 높이균형 속성이라고 한다.
• AVL 트리에 대한 갱신은 높이 균형 속성을 파괴할 수 있다. 트리에 대한 개조 작업을 통해 높이균형 속성을 회복할 수 있으며 삽입 후의 개조 작업은 O(1) 시간에, 삭제 후의 개조 작업은 $O(\log{n})$시간에 수행한다.
• AVL 트리로 구현된 사전의 주요 메쏘드들은 모두 $O(\log{n})$ 시간에 수행한다.

해시테이블

해시함수

ex)

h(x) = x%m

정수 h(x)를 키 x의 해시값이라 부른다.

해시테이블 구성

• 해시 함수 h
• 크기 m의 배열(해시 테이블이라고 불린다.)

  압축 맵

  나머지셈

  $h_2(k) = |k| % m$
  m은 일반적으로 소수이다.

  승합제

  $h_2(k) = |ak+ b| % m$
  a,b는 음이 아닌 정수로서 a % m이 0이 아니어야 한다. 그렇지 않으면 모든 정수가 동일한 수 b로 매핑되기 때문이다.

충돌 해결

분리 연쇄법

해쉬에 하나만 저장하는 것이 아닌 여러개를 저장하여 리스트로 연결한다.

Alg findElement(k)

1. v = h(k)
2. return a[v].findElement(k)


Alg insertItem(k,e)

1. v = h(k)
2. a[v].insertItem(k,e)
3. return


Alg removeElement(k)

1. v = h(k)
2. return a[v].removeElement(k)


Alg initBucketArray()

1. for (i = 0 to M-1)
    a[i] = empty list
2. return

개방 주소법

개방주소법은 분리연쇄법에 비해 공간사용을 절약하지만 삭제가 어렵다는것과 사전 항목들이 연이어 군집화하는 결점이 있다.

선형조사법

a[(h(k)+f(i))%m], f(i) = i , i = 0,1,2,3,4,5,,,,,
1차 군집화가 발생할 수 있고, 군집을 순회하는데 많은 시간이 소요된다.

2차 조사법

a[(h(k)+f(i))%m], f(i) = $i^2$ , i = 0,1,2,3,4,5,,,,,
여기에서도 2차 군집화가 발생할 수 있다. 또한 m이 소수가 아니거나 혹은 버켓 배열이 반 이상이 차면 비어있는 버켓이 남아있더라도 찾지 못할 수도 있다는 단점이 있다.

이중 해싱

a[(h(k)+f(i))%m], f(i) = $i^2*h'(k)$ , i = 0,1,2,3,4,5,,,,,
$h'(k) = q - (k % q)$ 또는 $h'(k) = q + (k % q)$를 사용한다. p<m이며 p는 소수이다.
h'(k)와 m은 서로소이다.

개방주소법 알고리즘

Alg findElement(k)

1. v= h(k)
2. i = 0
3. while(i < m){
    b = getNextBucket(v,i)
    if (isEmpty(A[b]))
        return NoSuchKey
    else if (k == key(A[b]))
        return element(A[b])
    else
        i = i +1
}
4. return NoSuchKey


Alg insertItem(k,e)

1. v = h(k)
2. i = 0
3. while(i<m ){
    b = getNextBucket(v,i)
    if (isEmpty(A[b]))
        Set bucket A[b] to (k,e)
        return
    else
        i = i +1
}
4. overflowException()
5. return


Alg getNextBucket(v,i)

1. return(v+i)%m


Alg getNextBucket(v,i)

1. return (v + i*i) %m


Alg getNextBucket(v,i)

1. return(v + i * h'(k)) % m


Alg initBucketArray()

1. for i = 0 to m-1
    A[i].empty = 1
return


Alg isEmpty(b)

1. return b.empty

해시테이블 성능

적재율

해시테이블의 적재율 $\alpha$ 는 n/m으로 정의된다.
주요 작업의 효율을 높이려면 적재율을 낮게 유지해야 한다.
주요 작업의 기대 실행시간은 O($\alpha$)이다.

분리 연쇄법

$\alpha$ > 1 이어도 작동하지만 다소 비효율적이다.
$\alpha$ <= 1이면 O($\alpha$) = O(1) 기대실행시간이 성취 가능하다.

개방 주소법

항상 $\alpha$ <= 1 이다.
$\alpha$ > 0.5면, 선형 및 2차 조사법인 경우 군집화 가능성이 높으며 이에 따른 성능 저하가 있게 된다.
$\alpha$<= 0.5로 유지하면 O($\alpha$)= O(1) 기대실행시간에 수행한다.

재해싱

• 적재율의 최적치를 초과했을 때
• 삽입이 실패한 때
• 너무 많은 비활성 셀들로 포화되어 성능이 저하되었을 때

  재해싱 단계

1. 버캣 배열의 크기를 증가시킨다.(원래 배열의 두강 두배 크기로 - 이때 새 배열의 크기를 소수로 설정하는 것을 잊지 말아야 한다).
2. 새 크기에 대응하도록 압축뱁을 수정.
3. 새 압축맵을 사용하여 기존 해시테이블의 원소들을 새 테이블에 삽입.

요약

• 해시테이블은 키-주소 매핑에 의해 구현된 사전 ADT를 말한다.
• 해시테이블은 버켓 배열과 해시함수가 결합되어 정의된다. 버켓 배열은 해시 테이블을 구현한 1차원 배열을 의미하며, 해시함수는 키-주소 매핑을 위한 연산을 수행하는 함수다.
• 해시 함수는 보통 해시 코드 맵과 압축맵 두 함수의 복합체로 명세된다.
• 상이한 두 개의 키가 동일한 해시 테이블 주소로 매핑되면 충돌이 일어났다고 말한다. 충돌 해결을 위한 전략으로는 크게 분리연쇄법과 개방주소법 두 가지가 있다.
• 해시테이블의 적재율 $\alpha$는 n/m으로 정의된다. 다시 말해 적재율은 좋은 해시함수를 사용할 경우 각 버켓의 기대 크기를 말한다. 주요 작업의 효율을 위해 적재율은 낮게 유지되어야 한다.