UnderCode

2013 1차 필기 11 ~ 15 본문

2013 1차 필기

2013 1차 필기 11 ~ 15

MS.S 2016. 4. 30. 21:24





AVL Tree

AVL 트리(AVL tree)는 가장 초기에 나온 균형 잡힌(balanced) 이진탐색트리이다. 1962년 G.M. Adelson-Velskii와 E.M. Landis 가 그들의 논문 "An algorithm for the organization of information" 을 통해 발표했고 그들의 이름을 따서 지어졌다. 

AVL 트리는 각각의 노드(node, 분기점)마다 왼쪽과 오른쪽 부분 트리(sub-tree)의 높이 차이에 대한 정보를 가지며 부분 트리의 높이 차이가 1보다 크지 않은 성질을 가진다. 

균형 잡힌 AVL 트리는 n개의 원소가 있을 때 O(log n) 의 시간복잡도로 검색, 삽입, 삭제를 할 수 있다. 그러나 삽입과 삭제를 할 때에는 원하는 노드를 찾기 위해 2개의 경로가 필요하기 때문에 레드-블랙 트리 만큼 효율이 좋지 않아 자주 쓰이지는 않는다.


AVL 트리에서 노드를 일반적인 이진 탐색 트리처럼 삽입, 삭제 시키면 높이 균형 성질을 만족하지 않게 된다. 노드가 삽입, 삭제될 때 회전(rotation)을 통해 트리를 재구성하여 높이 균형 성질을 유지시킨다.


일반적으로 AVL 트리에서는 4가지 형태의 삽입으로 AVL 트리가 조건이 깨져버린다.

LL 형식 : A의 왼쪽(L)     자식의  왼쪽(L)에넣는 경우

LR 형식 : A의 왼쪽(L)     자식의  오른쪽(R)에 넣는 경우

RR 형식 : A의 오른쪽(R) 자식의  오른쪽(R)에 넣는 경우

RL 형식 : A의 오른쪽(R) 자식의  왼쪽(L)에 넣는 경우



[LL형식]



B의 왼쪽 자식노드에 새로운 노드가 추가되어 트리에 불균형이 발생하였다.



이때, B의 오른쪽 노드를 A의 왼쪽노드로 하고 B의 오른쪽 노드를 A로 한다.


[코드]

Node* rotateLL(Node *node)

{

        Node *child=node->left;

        node->left=child->right;

        child->right=node;

        return child;

}


[RR형식]



B의 오른쪽 자식노드에 새로운 노드가 추가되어 트리에 불균형이 발생하였다.




이때, B의 왼쪽 노드를 A의 오른쪽노드로 하고 B의 왼쪽 노드를 A로 한다.


[코드]

Node* rotateRR(Node *node)

{

        Node *child=node->right;

        node->right=child->left;

        child->left=node;

        return child;

}



[LR형식]




C의 왼쪽 자식 노드에 새로운 노드가 추가되어 트리에 불균형이 발생하였다.

B와 C에 대해서 RR 회전을 해줍니다.




A와 C에 대해서 LL회전을 해줍니다.




[코드]

Node* rotateLR(Node *node)

{

        Node *child=node->left;

        node->left=rotateRR(child);

        return rotateLL(node);

}



[RL형식]




C의 왼쪽 자식 노드에 새로운 노드가 추가되어 트리에 불균형이 발생하였다.

B와 C에 대해서 LL 회전을 해줍니다.




A와 C에 대해서 RR회전을 해줍니다.




[코드]

Node* rotateRL(Node *node)

{

        Node *child=node->right;

        node->right=rotateLL(child);

        return rotateRR(node);

}



문제를 풀어보면


문제에서 제시된 트리는 LR형식을 이용하여 해결 가능해보인다.

7노드와 10노드를 RR회전한다.



위와 같은 형태로 재배치 되고 20노드와 10노드를 LL회전한다.




위와 같은 순서로 적용되어 답은 ③번이다.


http://blog.naver.com/ellay06/120171022413






너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용한다. OPEN List 는 큐를 사용해야만 레벨 순서대로 접근이 가능하다.


직관적인 이해를 돕기 위해 리를 대상으로 설명을 시작하자. 루트를 시작으로 탐색을 한다면 너비우선탐색(BFS)은 먼저 루트의 자식을 차례로 방문한다. 다음으로 루트자식의 자식, 즉 루트에서 두 개의 간선을 거쳐서 도달할 수 있는 정점을 방문한다. 다음으로 루트로부터 세 개의 간선을 거쳐서 도달하는 정점들... 순(레벨 순)으로 루트에서의 거리 순으로 방문한다.


그래프로 설명해보자.

1단계 : 하나의 노드를 택한다.

2단계 : 노드를 방문하여 필요한 작업을 한 다음 연결된 다음 노드를 찾는다. 노드들을 큐에 저장한다. 

더 이상 방문할 곳이 없으면 3단계로 간다.

3단계 : 큐의 맨 앞의 노드를 빼내 2단계를 반복한다.


장점

1. 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다.

단점

1. 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.

2. 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.

3. 무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.






답 ②


[참고 블로그http://blog.naver.com/lhm0812/220618145325








완전이진트리 : 노드가 왼쪽부터 차곡차곡 재워지는 이진 트리


가 : 편향 이진 트리

나 : 완전 이진 트리

다 : 이진 트리 

라: 포화 이진 트리

마 : 이진 트리




[참고 블로그] http://blog.naver.com/yitmdtn/220094816350






레드-블랙 트리 : 균형을 바로잡기 위해 5가지 규칙을 가지는 트리.

AVL 트리 : 4가지 형식의 뷸균형을 바로잡아 균형을 이루게 하는 트리.

2-3-4 트리 : 자식을 2~4개 까지 가질수 있는 균형 트리

Threaded Quad Tree : 효율적으로 이웃 노드를 검색할 수 있는 트리


답 ④

[레드-블랙 트리 참고] http://blog.naver.com/noblea1117/220454721219 

[2-3-4 트리 잠고] http://thesoul214.tistory.com/103

[Threaded Quad Tree 참고] http://www.dbpia.co.kr/Journal/ArticleDetail/NODE00624469






해당 문제에서 공간을 2분할하여 트리에 저장하고 있다.

따라서 이진 공간 분할 트리라고 할 수 있다.


BSP는 임의로 공간을 분할하여 렌더링 속도 향상을 이끌어 냅니다.

하지만 공간 분할 자제가 이점이 아니라 공간 분할을 이용하여 각 공간에서

가시성 판단을 했을 때 다른 공간이 보이느냐 안보이느냐에 따라

보이지 않는 공간을 렌더링 하지 않음으로 렌더링 속도의 향상을 이끌어낼 수 있습니다.


[참고 블로그] http://blog.naver.com/dombi77/110037336975


'2013 1차 필기' 카테고리의 다른 글

2013 1차 필기 11 ~ 15  (0) 2016.04.30
0 Comments
댓글쓰기 폼