면접 대비 자료구조 공부 (호로비츠 5장 트리)

5.3 이진 트리 순회 pg220

트리 순회(tree traversal)은 트리의 모든 노드를 한 번씩만 방문하는 것이다. 한 노드가 방문될때 어떤 연산이 그 노드에 대해 수행된다고 한다. 일반적으로 L,V,R 왼쪽 가운데,오른쪽 이렇게 세개 노드를 방문하는 순서를 나열 하면 6개가 되겠지만, 항상 R보다 L을 먼저 방문한다 하면 LVR,LRV,VLR이 가능하다. V의 상대적인 위치에 따라 중위 순회, 후위순회, 전위 순회라 한다함...

이름에 대한 유래도 전혀 몰랐고, 왜 굳이 3개 방법으로 하나 했는데 이해가 잘되는 내용이다

중위 순회 (in order)

중위 순회는 LVR 답게 왼쪽으로 쭉 들어가서 왼쪽에 자식이 없으면 해당 노드를 V로 보고 연산한뒤 R 오른쪽 노드로 방문한다. 그리고 V 이전 노드로 돌아간다.

재귀적으로 구현한다.

void LVR (int Node* ptr){
    if(ptr->left != NULL)
        LVR(ptr->left);

    //do calculation for V

    if(ptr->right != NULL)
        LVR(ptr->right);
}

전위 순회 (pre order)

VLR 전위 순회는 V 가운데를 먼저 방문하고 L왼쪽 R 오른쪽을 방문

먼저 방문하는 노드가 V이므로 연산을 먼저하고 L 왼쪽 자식으로 들어간다(L을 새로운 V로 삼는셈)
그리고 L이 없으면 R을 순회한다. 그러다 R이 없으면 V의 이전 V로 가서 R만 수행하는셈인데

->내가 봐도 내가 생각하는 프로세스가 왜 이렇게 개떡같이 설명하는지 모르겠다. 뭐가 문젤까 ....

void pre_order(Node* ptr){
    //V에 대한 연산.
    if(ptr->left != NULL)
        pre_order(ptr->left);
    if(ptr->right != NULL)
        pre_order(ptr->right);
}

후위 순회는 귀찬..

5.6 히프 237

우선 내 설명 ㅋㅋ

우선순위 큐

우선 순위 큐는 큐의 front에 큐에서 가장 크거나 작은 값이 항상 오도록 하는 자료구조입니다.
가장 크거나 작은 값을 찾는 시간 복잡도는 O(1)로 매우 성능이 좋습니다.
우선 순위 큐의 구성은 트리 형태로 힙의 구조를 갖습니다. 그래서 값의 삽입의 시간 복잡도가 O(logN)입니다.

최대 힙, 최소 힙

최대 힙은 트리 루트 원소가 항상 가장 큰 값이 오도록 하는 자료구조 입니다. 모든 노드의 왼쪽의 노드들은 자신 보다 작은 값이 오른쪽의 노드들은 자신보다 큰 값이 오도록 합니다.(최소 힙은 반대로)

-> 틀림

최대 힙은 최대 트리이면서 완전 이진 트리이고 최소 힙은 최소 트리이면서 완전 이진 트리이다.

(최대,최소 트리에 대해서 찾아볼것)

최대 힙, 최소 힙의 삽입

~삽입은 원소를 새로 리프 노드를 추가하고, 그 리프 노드와 루트 노드를 교환합니다. 그리고 최대 힙의 경우 자식 노드와 크기를 비교 하면서 자식이 더 큰 경우 부모와 바꿉니다. ~

-> 이게 아님
bubbling up 방식을 사용합니다. 말단 노드에서 시작해서 부모 보다 크면 부모와 교환하는 방식으로 갱신하면 됩니다.

코드는 맥스힙 기준이다.

void push(elemet item, int* n){
//c언어는 보통 다 element를 아이템으로 갖더라... 
//n을 변경 하기 위해서 포인터로 넘겨준다.

    int i = (*n)++;
    while(1){
        if( heap[i/2].key <  item.key){
            heap[i] = heap[i/2];
             i = i/2;   
        }
        else{
            break;
        }
    }
    heap[i] = item;
}

최대 힙, 최소 힙의 삭제

~ 모르겠다 ~

루트 노드를 삭제하고 마지막 노드를 루트 노드 위치로 옮긴다.
그리고 힙을 bubble down으로 정리 하면 된다.
시간 복잡도는 트리의 높이인 log(n)이 될 것이다.

trickle down 전략 이란다.
맥스힙 기준이다.

이건 내가 안보고 생각해서 작성해본건데
책을 보니 틀린 부분이 많다.

1. 힙이 비어있을 경우에 대해서 처리가 없다.

2. 변수 사용을 cur이라고 해서 parent 와 child이 햇갈릴 수 있다.

3. 제일 중요한데 두 자식중 더 큰놈을 찾아야 하는데 나는 그냥 크기만 하면 왼쪽으로 먼저 내려가도록 했다.

   void delete(element item,int* n){
    int root = 0;
    int cur =0;
    //move last to root
    heap[root] = heap[*n];
   
    while(1){
        if(heap[cur*2] != NULL && heap[cur] < heap[cur*2]){
            swap(*heap[cur],*heap[cur*2]);
            cur = cur*2;
        }
        else if(heap[cur*2+1] != NULL &&  heap[cur] < heap[cur*2+1]){
            swap(*heap[cur],*heap[cur*2+1]);        
        }
        else{
            break;
        }
    }
   

}

다시 해보자.

``` C
void delete(int *n){
    int parent= 1;
    int child=2;
    int greater;

    if(*n ==0){
        printf("heap is empty\n");
    }
    heap[parent] = heap[*n];

    while( *n >= child){
        greater = heap[child] < head[child+1] : child+1 ? child;

        if( heap[parent].key < heap[greater].key)
        {
            heap[parent].key = heap[greater].key;
        }

        parent = greater;
        child = greater*2;

    }
}

음 이렇게 구현하면 자식들이 원소가 없는 경우에 대한 경우가 문제일듯...아....모르겠다. pg234

5.7 이원 탐색 트리 (binary search tree)

binary search는 기억나는데 binary search tree는 기억이 안난다....

이원 탐색 트리 조건이다.

1. 모든 원소는 키를 갖고, 어떤 두 원소도 동일한 키를 갖지 않는다.
2. 왼쪽 서브트리의 키들은 그 루트의 키보다 작다.
3. 오른쪽 서브트리의 키들은 그 루트의 키보다 크다.
4. 왼쪽과 오른쪽 서브트리도 모두 이원 탐색 트리이다.

내가 아까 힙에서 사용된 트리가 이원탐색 트리인줄 알았다. 그게 아니라 힙에서 사용된 트리는 최대 트리, 완전 이진 트리이다.
이진 탐색 트리는 탐색,삽입,삭제,연산에 있어서 그 어떤 자료구조 보다도 성능이 좋다 한다.(즉 탐색,삽입,삭제,연산시 사용하면 좋을듯 하다)

키가 k인 원소를 찾기, k번째로 작은 원소를 찾아라, 삭제하라, 삽입하라 등에 유리한듯 하다.

이원 탐색 트리의 탐색

binary search tree 자체 정의가 순환적이므로 탐색 또한 순환적으로 하는것이라 한다.

element* search(TreePointer\* root,int k){  
if(root == NULL)  
return NULL;  
else if(root->key == k)  
return root;


if(root->key < k)
    return search(root->right);
else if(root->key > k)
    return search(root->left);       


}

이원 탐색 트리에서의 삽입

탐색 결과로 반환 받는 위치에 새로 노드를 할당한다.

이원 탐색 트리에서의 삭제

리프 노드일 경우는 리프 노드의 부모 포인터를 NULL로 하고 free하면 된다.

비리프 노드일 경우 왼쪽에서 가장 큰 값 또는 오른쪽에서 가장 큰 키 값의 노드를 제거하고자 하는 노드로 값을 가져온다. 그리고 복사 대상 이였던 노드의 자식들이 제거하려는 노드를 부모로 가리키게 하면 된다.즉 중간을 뛰어 넘는 샘이다.

5.7.5 이원 탐색 트리의 조인과 분할

이 부분은 음 too much가 아닌가...

5.8 선택 트리

5.10 Disjoint union Set

이 내용은 알고리즘 문제 풀다가 집합별로 뭉치고 어떤 원소가 어느 집합에 속하는지 찾을때 자주 사용한 내용인데 가중 규칙과 붕괴 규칙을 어설프게 사용해서 구현에 너무 오래걸렸었기에 정리해본다.

Union, Find 연산

내가 알고있는 Union,Find 방법(simple인듯)
Find는 원소가 부모가 -1일때 까지 재귀적으로 부모의 부모를 찾으면 된다.
Union은 합치려는 두 원소의 부모를 각각 찾고 한쪽 부모가 다른쪽 부모를 가리키도록 하면 된다.
(사실 여기서 굳이 둘다 부모를 찾을 필요는 없는듯 하다. 한쪽만 찾아도 될듯)

여기서 degenerate tree가 생성되는 것이 문제라 한다.

weighted union(가중 규칙)

이 부분 구현을 find 연산에 대한 호출 횟수를 세서 큰쪽이 작은쪽의 부모가 되도록 구현했다.....

그래서 union을 위한 가중 규칙은 루트 i,j의 트리의 노드수가 많은 쪽을 부모로 하고 적은 쪽을 자식으로 한다.

void weighted_sum(int a,int b){
    int parent_a = find(a);
    int parent_b = find(b);
    int temp = parent_a + parent_b;
    //b가 a를 부모로 갖게 한다.
    if( parent_a < parent_b){
        parent[b] = a;
        parent[a] = temp;
     }
    else{
        parent[a] = b;
        parent[b] = temp;
    }
    return ;    
}

collapsingFind (붕괴 규칙)

어떤 노드의 부모를 찾는데 경로상에서 지나가는 노드들의 parent가 루트가 아니면 그 노드의 parent를 마지막에 발견하는 root로 정해주자는 내용이다.

나는 이걸 find연산에 추가해 줬는데 호로비츠는 따로 함수 구현하신듯

1. find에 붕괴 규칙 적용시

    int find(int a){
        if(parent[a] == -1){
            return a;
        }
        return (parent[a] = find(a));
    }

이렇게 해서 재귀로 들어갔다 나올때 부모를 지정해 줬었다.

2. 호로비츠님

    int collapsingFind(int i)
    {
        int root,trail,lead;
        for(root = i;parent[root] >=0; root = parent[root]);
        for(trail=i; trail != root; trail = lead){
            lead = parent[trail];
            parent[trail] = root;
        }
        return root;
    }

6 그래프