[트리] Tree 2: 이진 검색 트리, 트립

1. 검색 트리

 

검색 트리는 링크드 리스트나 큐처럼 자료들을 담는 컨테이너지만,

자료들을 일정한 순서에 따라 정렬한 상태로 저장해둔다.

이것은 입력이 주어진 순서에 따라 자료들을 배치하는 리스트나 큐와 다른 속성이다.

이런 속성은 원소의 추가 와 삭제만이 아니라 특정 원소의 존재 여부 확인 등의 다양한 연산을 빠르게 할 수 있다.

 

 

이진 검색트리는 특히 아주 널리 사용되기 때문에, 이들의 동작 원리와 장단점은 알아야한다.

 

대부분 이진 검색트리는 라이브러리에서 제공한다.

 

2. 이진 검색 트리

 

이진 트리(binary tree) 란 각 노드가 왼쪽과 오른쪽, 최대 두 개의 자식 노드만을 가질 수 있는 트리를 의미한다.

따라서, 이진 트리는 자식 노드들의 배열 대신 두 개의 포인터 left 와 right를 담는 객체로 구현된다,

 

이진 검색 트리는 이진 탐색(binary search)에서 아이디어를 가져와서 만든 트리이다.

이진 탐색은 검색시 수행시간은 O(lgn)이다.

 

이진 검색 트리 = 이진 탐색 + 이진 트리

 

서브트리에서 

작은 원소들이 루트의 왼쪽,

큰 원소들이 루트에서 오른쪽인걸 위 트리에서 볼 수 있다.

이런 성질을 유지하기 때문에

이진 탐색의 방법으로 원하는 원소를 빠르게 찾을 수 있는 것이다.

 

 

3. 이진 검색트리 다루기

 

순회

 

이진 검색 트리를 중위 순회하면 크기 순서로 정렬된 원소의 목록을 얻을 수 있다.

 

루트 보다 작은 원소는 전부 왼쪽, 큰 원소는 전부 오른쪽에 있기 때문이다.

 

또 이러한 성질로 인해 최대 최소 원소를 쉽게 얻을 수 있다.

 

중위 순회 첫번째: 최소원소 (윈쪽을 따라 쭉 내려감)

중위 순회 마지막: 최대원소 (오른쪽을 따라 내려감)

 

 

 

자료의 검색

 

이진 검색 트리에서는 아주 간단하게 검색할 수 있다.

 

이진 검색과 마찬가지로 현 루트보다 작은 값이면 왼쪽 서브트리로 큰값이면 오른쪽 트리로

(균형잡힌 트리와 가까울 시 O(lgn) 에 가깝다)

 

 

 

 

조작- 삽입, 삭제, 합치기

 

 

정렬된 배열보다 장점인 성질

 

원소를 추가하거나 삭제하는 조작 연산도 쉽게 가능하다.

 

선형적 구조의 제약이 없기 때문이다.

 

새 원소가 들어갈 위치를 찾고 거기에 추가만 하면 된다.

(검색시 값을 찾지못하면 현 루트와의 비교에따라 왼쪽 포인터 오른쪽포인터에 할당)

 

삭제를 구현하려면 먼저 '합치기'연산을 구현해야한다.

 

노드 t를 지우고 나면

t의 두 서브 트리를 합친후 다시 연결이 필요하기 때문이다.

(원래 서브트리를 대체)

 

합치는 과정은 다음과 같다.

루트를 삭제하고 남은 왼쪽 서브트리 A와 오른쪽 서브트리 B가 있으면

A는 항상 B보다 작다,

그러므로 A를 루트삼아 A의 오른쪽과

B를 재귀적으로 다시 합치는 것을 반복하고 A와 합친다.

반대의 연산도 마찬가지다 B를 루트삼아도 상관없다.

 

 

 

 

4. 시간 복잡도 분석과 균형 잡힌 이진 검색 트리

 

 

모든 이진 검색 트리는 루트에서 시작하여 재귀 호출로 한 단계씩 내려간다.

 

최대 재귀 호출의 횟수는 트리의 높이와 같다 h

 

따라서 모든 연산은 O(h)라고도 할 수 있다.

 

하지만 이진트리가 균형잡힌 트리가 아닐때 이는 '기울어진(skewed)' 트리라고하여

이런 연산들이 링크드 리스트와 차이가 없음을 그림을 그려보면 직관적으로 알 수 있다.

 

균형 잡힌 트리를만들게 되면 단계마다 노드의 수가 2배가 되므로

트리의 최소 높이는 O(lgn)이 되어 더욱 빠르게 연산들을 수행 할 수 있다.

 

이와 같이 균형 잡힌 트리를 유지하기 위해서

트리의 구조에 추가적인 제약을 정하고, 노드들을 옮기면서

트리의 높이를 항상 lgn으로 유지하는 트리들을  balanced binary search tree라고 한다.

 

대표적인 트리는 레드-블랙 트리(red-black tree)와 AVL트리가 있다.

이는 라이브러리에서 제공하는 이진 검색트리의 구현에 자주 쓰인다.

 

 

 

5. 균형 잡힌 이진 검색 트리 직접 구현: 트립(treap)

 

표준 라이브러리의 이진 검색 트리는 대부분 x보다 작은 원소의 수, k번째 원소를 찾는 연산을 지원하지 않는다.

 

따라서 이런 연산이 필요하면 BST를 직접 구현할 수 밖에 없다.

 

Treap은 랜덤화된 이진 검색 트리이다.

 

트리의 형태가 원소들의 추가 순서에 따라 결정되지 않고, 난수에 의해 임의대로 결정된다.

 

삽입 삭제하더라도 따라서 트리 높이의 기대치는 항상 일정하다.

 

 

트립은 새 노드가 추가될 때마다 우선순위(priority)를 부여한다.

 

이 우선순위는 난수로 생성된다.

 

트립은 항상 부모의 우선순위가 자식의 우선순위보다 높은 BST를 만든다.

 

→ BST의 조건: 루트원소보다 왼쪽 서브트리의 모든 원소는 작고 오른쪽은 크다

→ Heap의 조건: 모든 노드의 우선순위는 각자의 자식 노드보다 크거나 같다.

  

또한 트립은 우선순위가 높은 것부터 순서대로 추가한 BST랑 똑같다.

 

 

트립의 높이

트립에서 원소 x를 찾으려고할때 방문하는 노드 수의 기대치가 O(lgn)임을 증명해보자.

 

O(lgn)이라는 것은 한 단계 내려갈 때마다 후보가 되는 원소의 수가 선형으로 줄어드는 것이 아니라

지수적으로 줄어든다는 것을 보이면 된다. (절반씩 줄여나가면 lgn).

 

각 원소가 현재 찾는 원소일 확률이 모두 같다고 가정하고, 루트가 r번째로 작은 원소라고 가정해보자.

 

찾는 원소가 루트일 확률: 1/N

찾는 원소가 왼쪽 서브트리에 있을 확률: (r-1)/N

찾는 원소가 오른쪽 서브트리에 있을 확률: (N-r)N

 

다음단계에서의 후보의 수에 대한 기대치는 다음과 같다.

기댓값은 각 결과를 그 확률로 곱하고 이를 모두 더해 구할 수 있다.

 

1 * 1/N  + (r-1)(r-1)/N + (N-r)(N-r)N

 

=( (r-1)^2 + 1 + (N-r)^2  ) /  N

 

우선순위를 임의로 부여하기 때문에 모든 값은 루트가 될 가능성이 있다.

r이 1~N이 될 확률은 모두 같다. 

따라서 모든 r에 대한 값의 평균을 취해야한다.

 

(∑( (r-1)^2 + 1 + (N-r)^2  ) /  N) / N

 

= 2N^2 - 3N + 4 / 3N 

≒ 2N/3

 

이는 후보의 수가 평균적으로 2/3로 줄어든다는 뜻이다

따라서 O(lgn) 단계를 거치면 답을 찾을 수 있다.

 

 

트립의 구현

 

구조:

    트립의 구조는 이진트리에 우선순위가 들어간것이다. 

 

    각 서브트리의 루트마다 서브트리의 사이즈를 기록하여 

 

    특정 함수를 구현하기 쉽게 하였다.

 

    setLeft와 setRight는 재귀할때 유용하게 사용된다.

 

 

쪼개고 삽입:

    삽입하려면 일단 한 트리를 쪼개야한다.

 

    추가하려는 노드의 우선순위와 서브트리의 루트의 우선순위를 비교하면서 우선순위가 더 큰 루트를 찾는다.

 

    찾으면 다음과 같이 쪼갤 수 있다.

 

    x가 루트보다 클경우 : (왼쪽-루트- x보다 작은 오른쪽 서브트리 , x보다 큰 오른쪽 부분)

 

    x가 루트보다 작을경우: (왼쪽의 x보다 작은 부분, 왼쪽 서브트리의 x보다 큰부분 - 루트-오른쪽) 

 

    쪼갠 두개의 서브트리를 삽입하려는 노드에 연결하고 원래 루트의 부모를 받는다.

 

합치고 제거:

    제거하고 남은 왼쪽 서브트리와 오른쪽 서브트리 두개를 합쳐야한다.

 

    합칠때는 왼쪽, 오른쪽 루트 중에서 우선순위가 높은것이 루트가 되고, 각각 작거나 큰 부분을 옮긴다.

 

    왼쪽이 높을 경우: 왼쪽의 오른쪽 서브 트리를 오른쪽과 합친다. (재귀 필요 오른쪽부분과 우선순위)

 

    오른쪽이 높을 경우: 오른쪽의 왼쪽 서브트리를 왼쪽으로 옮긴다.(재귀필요)

 

 

x보다 작은 원소의 개수 구하기:

    x보다 작은 원소는 높이에 비례한 수 lgn 만큼 함수를 수행하여 구할 수 있다.

 

    각각 루트마다 x와 같거나 크면 왼쪽으로 넘어간다.

 

    왼쪽이 만약 x보다 작을 경우 왼쪽의 크기(0일 수 있다.) 와 루트 1개 그리고 재귀를 통하여

 

    오른쪽 서브트리에서 x보다 작은 원소의 개수를 구한다.

 

k번째 원소 찾기: 

    k번째 원소또한 높이에 비례한 수 lgn만큼 한수를 수행하여 구할 수 있다.

 

    k번째 원소는 사이즈를 통해 현재 몇번째 원소인지 파악한다.

 

    왼쪽 서브트리가 만약 사이즈가 k번째 보다 작을 경우 오른쪽 서브트리로 이동하여 조사한다.

    왼쪽 서브트리 안에 k번째 원소가 있으면 재귀를 통해 왼쪽 서브트리로 이동한다.

    왼쪽 서브트리의 사이즈 + 1이 k일 경우 루트가 k 번째 원소가 된다. 

typedef int KeyType;
 
 
struct Node {
    KeyType key;
    int priority, size;
    Node *left, *right;
    Node(const KeyType& _key) : key(_key), priority(rand()), size(1), left(NULL), right(NULL) {}
    void calcsize() {
        size = 1; 
        if(left)
            size += left->size;
        if(right)
            size += right->size;
    }
    void setRight(Node* _right){
        right = _right;
        calcsize();
    }
    void setLeft(Node* _left) {
        left = _left;
        calcsize();
    }
};
 
typedef pair<Node*, Node*> NodePair;
NodePair split(Node* root, KeyType key)
{
    if(root == NULL) return NodePair(NULL, NULL);
 
    if(root->key < key) {
        NodePair rs = split(root->right, key);
        root->setRight(rs.first);
        return NodePair(root, rs.second);
    }
    NodePair ls = split(root->left, key);
    root->setLeft(ls.second);
    return NodePair(ls.first, root);
}
 
Node* insert(Node* root, Node* node) {
    if(root == NULL) return node;
    if(root->priority < node->priority) {
        NodePair splitted = split(root, node->key);
        node->setLeft(splitted.first);
        node->setRight(splitted.second);
        return node;
    }
    else if(node->key < root->key)
        root->setLeft(insert(root->left, node));
    else
        root->setRight(insert(root->right, node));
    return root;
}
// max(a) < min(b)
Node* merge(Node* a, Node* b) 
{
    if(a == NULL) return b;
    if(b == NULL) return a;
    if(a->priority < b->priority)
    {
        b->setLeft(merge(a, b->left));
        return b;
    }
    a->setRight(merge(a->right, b));
    return a;
}
 
Node* erase(Node* root, KeyType key) {
    if(root == NULL) return root;
    if(root->key == key) {
        Node* ret = merge(root->left, root->right);
        delete root;
        return ret;
    }
    if(key < root->key)
        root->setLeft(erase(root->left, key));
    else
        root->setRight(erase(root->right, key));
    return root;
}
 
Node* kth(Node* root, int k) {
    int leftSize = 0;
    if(root->left != NULL) leftSize = root->left->size;
    if(k<=leftSize) return kth(root->left, k);
    if(k==leftSize + 1) return root;
    return kth(root->right, k - leftSize - 1);
}
 
int countLessThan(Node* root, int x) {
    if(root == NULL) return 0;
    if(root->key >= x)
        return countLessThan(root->left, x);
    int ls = (root->left ? root->left->size : 0);  
    return ls + 1 + countLessThan(root->right, x); 
}
 

 

 

- 알고리즘 문제해결전략 697p