2013 1차 필기 11 ~ 15

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)은 먼저 루트의 자식을 차례로 방문한다. 다음으로 루트자식의 자식, 즉 루트에서 두 개의 간선을 거쳐서 도달할 수 있는 정점을 방문한다. 다음으로 루트로부터 세 개의 간선을 거쳐서 도달하는 정점들... 순(레벨 순)으로 루트에서의 거리 순으로 방문한다.