13강. 멀티웨이 탐색 트리 (II)

by

학습개요

13장은 트리를 다루는 마지막 장입니다. 지금까지 배운 내용을 간략하게 정리해 봅시다. 7장에서 일반적인 트리를 정의하고 이어서 차수가 2인 즉, 자식을 두 개만 갖는 이진 트리를 다루었습니다. 그리고 여러 가지 확장된 이진 트리에 대해 11장까지 소개했습니다.

특히 11장에서는 이진 탐색 트리와 그것을 개선한 트리들에 대해 배웠습니다. 이때까지 우리는 자식을 2개 까지만 허용하는 이진 트리를 줄 곧 다뤘지요. 그리고 12장에서 마침내 m 차수가 허용되는 멀티웨이 탐색 트리를 정의했습니다. 그리고는 곧바로 균형에 대한 제약을 갖는 B 트리 계열을 설명했지요. 그런 모든 변형 들은 결국 탐색을 효율적으로 하는 것을 위한 것들이었습니다. 이 장에서도 앞 장과 마찬가지로 균형을 유지하는 다른 탐색 트리에 대해 배워보도록 하겠습니다.

학습목표

  1. 2-3 트리를 설명하고 탐색, 삽입, 삭제 연산을 수행할 수 있다.
  2. 2-3-4 트리를 설명하고 탐색, 삽입, 삭제 연산을 수행할 수 있다.
  3. 레드 블랙 트리를 설명하고 탐색, 삽입, 삭제 연산을 수행할 수 있다.

연습문제

  1. 2-노드와 3-노드만으로 구성한 트리로 B 트리 계열과 거의 같은 성능을 유지하면서 상대적으로 삽입 삭제가 용이한 트리는 무엇인가 ?
    1. BS 트리
    2. 레드블랙 트리
    3. 2-3-4 트리
    4. 2-3 트리
      –
  2. 2-3-4 트리를 이진 트리로 나타낸 것으로 기억장소를 효율적으로 사용할 수 있도록 만든 트리는 무엇인가 ?
    1. m-웨이 멀티 트리
    2. 레드블랙 트리
    3. 2-3-4 트리
    4. 2-3 트리
      –
  3. 2-3-4 트리에서 lchild, mchild 및 rchild를 각각 3-노드의 왼쪽, 좌중간 및 우중간 자식이라 하고 lkey, rkey를 이 노드의 키값이라 하면, 틀린 설명은 무엇인가 ?
    1. ‘mkey < lkey’ 를 만족한다.
    2. 루트가 lchild인 모든 2-3-4 서브트리 키값은 lkey 보다 작다.
    3. 루트가 lmchild인 모든 2-3-4 서브트리 키값은 lkey 보다 크고 mkey 보다 작다.
    4. 루트가 rmchild인 모든 2-3-4 서브트리 키값은 mkey보다 크다.

정리하기

  1. 차수가 2인 노드를 2-노드, 3인 노드를 3-노드라 합니다.
  2. 2-노드와 3-노드만으로 구성한 트리를 2-3 트리라 합니다. 이 트리는 균형이 잡힌 B 트리 계열과 거의 같은 성능을 유지하면서도 상대적으로 삽입과 삭제가 용이합니다.
  3. 2-노드, 3-노드, 및 4-노드만으로 구성한 트리를 2-3-4 트리라 합니다. 이 트리는 2-3트리와 같은 특성을 갖습니다. 대신 같은 수의 노드를 더 낮은 레벨로 구축할 수 있습니다.
  4. 2-3-4 트리는 4노드를 갖기 때문에 경우에 따라서는 기억 장소를 낭비할 수 있습니다. 기억장소를 효율적으로 사용하기 위해 2-3-4 트리를 이진 트리로 나타낸 것이 레드 블랙 트리입니다.

Leave a Comment