11강. BS, Splay, AVL, BB

by

학습개요

삽입, 삭제 연산을 보다 효과적으로 작업하기 위해 만든 이진 탐색 트리에 대한 정의와 이진 트리와 같이 순회 방법에 대해서도 학습하게 됩니다. 이진 탐색 트리에서는 각 노드를 식별하기 위해서 별도의 이름을 붙여준 키(key)라는 용어를 사용합니다. 노드의 데이터라고 생각해도 됩니다.

정해진 노드()를 기준으로 왼쪽 서브 트리에 있는 모든 노드는 의 킷값보다 값이 작아야 하고, 오른쪽 서브 트리의 노드들은 의 킷값보다 값이 커야 한다는 조건을 만족하는 이진 트리를 이진 탐색 트리 즉 BS 트리라 합니다. 균형 잡힌 트리로 Splay, AVL, BB 트리가 있습니다.

Splay 연산을 적용한 Splay 트리가 있습니다. 최근에 사용한 노드 x를 다음에도 사용할 수 있다는 가정하에 노드 x를 루트에 위치시켜 트리를 재구성합니다. AVL 트리는 노드 의 왼쪽 서브트리 높이와 의 오른쪽 서브트리 높이가 최대 1만큼 차이가 난다는 조건을 만족하는 트리입니다.

무게가 균형 잡힌 트리란 각 노드의 양쪽 서브트리 무게가 균형을 유지하는 트리입니다. 이 트리를 BB-트리(bound-balanced)라고 부릅니다. AVL 또는 BB 트리에 대하여 각각 높이 또는 크기 제한 조건을 만족시키는데 드는 비용은 트리를 완전히 균형 잡히게 유지하는 비용이나 노력보다 훨씬 작기 때문에 사용됩니다.

학습목표

  1. 이진 탐색 트리의 정의와 순회, 탐색 방법을 이해할 수 있다.
  2. 이진 탐색 트리의 삽입 및 삭제 방법을 이해할 수 있다.
  3. Splay 트리의 개념과 연산 방법을 이해할 수 있다.
  4. AVL 트리의 개념과 조건을 이해할 수 있다.
  5. BB 트리의 개념을 이해할 수 있다.

연습문제

  1. 빠르게 탐색할 수 있도록 구성한 이진트리는 무엇인가 ?
    1. BB 트리
    2. AVL 트리
    3. 이진 선택 트리
    4. 이진 탐색 트리
      –
  2. Splay 트리에 대한 설명은 무엇인가 ?
    1. 승자 트리
    2. 패자 트리
    3. 자주 탐색하는 키를 가진 노드를 루트에 가깝게 위치하도록 구성한 이진 탐색 트리
    4. 이진 정렬
      –
  3. 트리의 무게는 무엇인가 ?
    1. 차수가 2인 노드의 갯수
    2. 루트부터 입 노드까지의 경로에 존재하는 노드의 갯수
    3. 트리에 속한 잎 노드의 개수
    4. 같은 부모에 대한 자식의 높이 차이

정리하기

  1. 트리에 특정 데이터가 있는지를 검색하고, 노드를 자주 삽입, 삭제하는 응용 문제에 가장 효과적인 이진 트리는 이진 탐색 트리(binary search tree)입니다.
  2. 키는 각 노드를 식별하기 위해서는 별도의 간단한 이름을 붙여준 것으로 노드의 데이터라고 생각할 수 있습니다.
  3. 이진 탐색 트리는 전위 순회, 중위 순회 및 후위 순회로 모든 정점을 차례로 순회할 수 있고 트리 내의 특정 정점을 탐색할 수도 있습니다.
  4. 이진 탐색 트리에서 새 노드는 항상 잎으로 삽입합니다. 즉, 루트부터 킷값을 비교하며 자기가 삽입될 위치가 왼쪽이냐 오른쪽이냐를 정하며 내려갑니다.
  5. Splay 트리는 자주 탐색하는 키를 가진 노드를 루트에 가깝게 위치하도록 구성한 이진 탐색 트리입니다.
  6. Splay 트리는 Splay 연산을 적용하여 최근에 사용하려고 접근한 노드 x를 루트에 위치시켜 트리를 재구성합니다.
  7. AVL 트리는 노드 의 왼쪽 서브트리 높이와 의 오른쪽 서브트리 높이가 최대 1만큼 차이가 난다는 조건을 만족하는 트리입니다.
  8. 트리의 높이란 노드가 가질 수 있는 가장 높은 레벨에 1을 더한 값으로 루트로부터 잎까지 가장 긴 경로 길이를 말합니다.
  9. 트리의 무게는 트리에 속한 잎 노드의 개수로 정의합니다.
  10. 무게가 균형 잡힌 트리란 각 노드의 양쪽 서브트리 무게가 균형을 유지하는 트리입니다. 이 트리를 무게가 균형 잡힌 트리(weight-balanced tree) 또는 BB-트리(bound-balanced)라고 부릅니다.
  11. AVL 또는 BB 트리에 대하여 각각 높이 또는 크기 제한 조건을 만족시키는데 드는 비용은 트리를 완전히 균형 잡히게 유지하는 비용이나 노력보다 훨씬 작습니다.
  12. 삽입이나 삭제 후에 트리를 완전히 균형 잡히게 유지하기 위해서는 Ο(n)개의 노드를 옮겨야 하는 반면에 AVL 또는 BB 트리는 Ο(log₂n)개의 노드를 옮기면 되는 것으로 알려졌습니다.

Leave a Comment