20. van Emde Boas Trees

반 엠데 보아스 트리는 우선 순위 큐 연산들을 O(\lg \lg n) 최악 시간에 제공하나, 키가 0부터 n – 1까지의 정수여야 하고 중복이 허용되지 않는다는 조건이 있다. 키의 가능한 값의 집합 \{0, \cdots, u - 1\}전체집합이라 하고 u를 전체집합 크기라 하자. 여기선 u = 2^{k}라 가정한다.

20.1. Preliminary approaches

기본적 접근법을 알아보자.

Direct addressing

전체집합 \{0, \cdots, u - 1\}의 값을 갖는 동적 집합을 저장하려면 u개의 비트를 가진 배열이 필요하다. 하지만 MAXIMUM, MINIMUM, SUCCESSOR, PREDECESSOR는 \Theta(u)가 걸릴 수 있다.

Superimposing a binary tree structure

각 원소를 이진 트리의 리프로 두고 이진 트리의 부모를 자식들의 비트 OR로 하면 최악 시간을 O(\lg u)로 줄일 수 있다. 저장된 원소 수가 적다면 레드 블랙 트리가 더 좋다.

Superimposing a tree of constant height

u = 2^{2k}라 하고 차수 \sqrt{u} (높이 2)의 트리로 자료구조를 증강하자. 부모는 역시 자식들 (클러스터)의 비트 OR로 정의한다. 이 때 MINIMUM, MAXIMUM, SUCCESSOR, PREDECESSOR, DELETE는 O(\sqrt{u})로 줄일 수 있다.

20.2. A recursive structure

위의 구조를 재귀적으로 만들어 보자. 원본 배열은 u^{\frac{1}{2}} 크기의 증강된 자료구조를, 이는 u^{\frac{1}{4}} 크기의 증강된 자료구조를, … 이를 반복하는 것이다. 여기서 u=2^{2^{k}}로 가정한다 (나중에 이 제한은 u=2^{k}로 풀린다). 이 때 T(u) = T(\sqrt{u}) + O(1)이므로 T(u) = O(\lg \lg u)이 된다.

20.2.1. Proto van Emde Boas structures

프로토 반 엠데 보아스 구조(프로토-vEB 구조)를 다음과 같이 정의한다.

  • u = 2이면 A[0, 1]의 2비트 배열을 갖는다.
  • u=2^{2^{k}}이고 k \geq 1이면 proto-vEB(u)는 proto-vEB(\sqrt{u}) 구조 (요약)에 대한 포인터를 갖고 각각이 proto-vEB($\latex \sqrt{u}$)가 되는 클러스터 [0, \cdots, \sqrt{u} - 1]\sqrt{u}개 갖는다.

20.2.2. Operations on a proto van Emde Boas structure

이제 각 연산들을 알아보자.

Determining whether a value is in the set

MEMBER(x)의 구현은 다음과 같다. O(\lg \lg u)이다.

PROTO-VEB-MEMBER(V, x)
if V.u == 2
    return V.A[x]
else
    return PROTO-VEB-MEMBER(V.cluster[high(x)], low(x))

Finding the minimum element

최소 원소 찾기의 구현은 다음과 같다. \Theta(\lg u)이다.

PROTO-VEB-MINIMUM(V)
if V.u == 2
    if V.A[0] == 1
        return 0
    else if V.A[1] == 1
        return 1
    else
        return NIL
else
    min-cluster = PROTO-VEB-MINIMUM(V.summary)
    if min-cluster == NIL
        return NIL
    else
        offset = PROTO-VEB-MINIMUM(V.cluster[min-cluster])
        return index(min-cluster, offset)

Finding the successor

다음 원소 찾기는 다음과 같다. \Theta(\lg u \lg \lg u)이다.

PROTO-VEB-SUCCESSOR(V, x)
if V.u == 2
    if x == 0 and V.A[1] == 1
        return 1
    else
        return NIL
else
    offset = PROTO-vEB-SUCCESSOR(V.cluster[high(x)], low(x))
    if offset ≠ NIL
        return index(high(x), offset)
    else
        succ-cluster = PROTO-VEB-SUCCESSOR(V.summary, high(x))
        if succ-cluster == NIL
            return NIL
        else
            offset = PROTO-VEB-MINIMUM(V.cluster[succ-cluster])
            return index(succ-cluster, offset)

Inserting an element

삽입은 다음과 같다. \Theta(\lg u)이다.

PROTO-VEB-INSERT(V, x)
if V.u == 2
    V.A[x] = 1
else
    PROTO-VEB-INSERT(V.cluster[high(x)], low(x))
    PROTO-VEB-INSERT(V.summary, high(x))

Deleting an element

삭제는 클러스터 내 모든 \sqrt{u}개의 비트를 조사해야 해서 더 복잡하다.

20.3. The van Emde Boas tree

반 엠데 보아스 트리는 추가적인 정보를 보강해 O(\lg \lg u)의 수행 시간을 갖게 한다. 또한, u = 2^{k} 제한을 둔다.

20.3.1. van Emde Boas trees

반 엠데 보아스 트리(vEB 트리)는 프로토 반 엠데 보아스 구조와 비슷하나, 최소 원소와 최대 원소를 저장한다.

20.3.2. Operations on a van Emde Boas tree

이제 연산들을 알아보자.

Finding the minimum and maximum elements

최소 원소와 최대 원소는 O(1)이다.

VEB-TREE-MINIMUM(V)
return V.min
VEB-TREE-MAXIMUM(V)
return V.max

Determining whether a value is in the set

원소 검색은 다음과 같다. O(\lg \lg u)이다.

VEB-TREE-MEMBER(V, x)
if x == V.min or x == V.max
    return TRUE
else if V.u == 2
    return FALSE
else
    return VEB-TREE-MEMBER(V.cluster[high(x)], low(x))

Finding the successor and predecessor

다음 원소 찾기는 다음과 같다. O(\lg \lg u)이다.

VEB-TREE-SUCCESSOR(V, x)
if V.u == 2
    if x == 0 and V.max == 1
        return 1
    else
        return NIL
else if V.min ≠ NIL and x < V.min
    return V.min
else
    max-low = VEB-TREE-MAXIMUM(V.cluster[high(x)])
    if max-low ≠ NIL and low(x) < max-low
        offset = VEB-TREE-SUCCESSOR(V.cluster[high(x)], low(x))
        return index(high(x), offset)
    else
        succ-cluster = VEB-TREE-SUCCESSOR(V.summary, high(x))
        if succ-cluster == NIL
            return NIL
        else
            offset = VEB-TREE-MINIMUM(V.cluster[succ-cluster])
            return index(succ-cluster, offset)

앞의 원소 찾기도 비슷하다. O(\lg \lg u)이다.

VEB-TREE-PREDECESSOR(V, x)
if V.u == 2
    if x == 1 and V.min == 0
        return 0
    else
        return NIL
else if V.max ≠ NIL and x > V.max
    return V.max
else
    min-low = VEB-TREE-MINIMUM(V.cluster[high(x)])
    if min-low ≠ NIL and low(x) > min-low
        offset = VEB-TREE-PREDECESSOR(V.cluster[high(x)], low(x))
        return index(high(x), offset)
    else
        pred-cluster = VEB-TREE-PREDECESSOR(V.summary, high(x))
        if pred-cluster == NIL
            if V.min ≠ NIL and x > V.min
                return V.min
            else
                return NIL
        else
            offset = VEB-TREE-MAXIMUM(V.cluster[pred-cluster])
            return index(pred-cluster, offset)

Inserting an element

삽입은 다음과 같다. O(\lg \lg u)이다.

VEB-EMPTY-TREE-INSERT(V, x)
V.min = x
V.max = x
VEB-TREE-INSERT(V, x)
if V.min == NIL
    VEB-EMPTY-TREE-INSERT(V, x)
else if x < V.min
        exchange x with V.min
    if V.u > 2
        if VEB-TREE-MINIMUM(V.cluster[high(x)]) == NIL
            VEB-TREE-INSERT(V.summary, high(x))
            VEB-EMPTY-TREE-INSERT(V.cluster[high(x)], low(x))
        else
            VEB-TREE-INSERT(V.cluster[high(x)], low(x))
    if x > V.max
        V.max = x

Deleting an element

삭제는 다음과 같다. O(\lg \lg u)이다.

VEB-TREE-DELETE(V, x)
if V.min == V.max
    V.min = NIL
    V.max = NIL
else if V.u == 2
    if x == 0
        V.min = 1
    else
        V.min = 0
    V.max = V.min
else if x == V.min
        first-cluster = VEB-TREE-MINIMUM(V.summary)
        x = index(first-cluster, VEB-TREE-MINIMUM(V.cluster[first-cluster]))
        V.min = x
    VEB-TREE-DELETE(V.cluster[high(x)], low(x))
    if VEB-TREE-MINIMUM(V.cluster[high(x)]) == NIL
        VEB-TREE-DELETE(V.summary, high(x))
        if x == V.max
            summary-max = VEB-TREE-MAXIMUM(V.summary)
            if summary-max == NIL
                V.max = V.min
            else
                V.max = index(summary-max, VEB-TREE-MAXIMUM(V.cluster[summary-max]))
    else if x == V.max
        V.max = index(high(x), VEB-TREE-MAXIMUM(V.cluster[high(x)]))

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중