탐색 트리

탐색트리

• 이진탐색트리(binary search tree): 내부노드에 (키, 원소) 쌍을 저장하며 다음의 성질을 만족하는 이진트리
  • u, v, w는 모두 트리노드며 u와 w가 각각 v의 왼쪽과 오른쪽 부트리에 존재할 때 다음이 성립 key(u) < key(y) <= key(w)
• 그림의 단순화를 위해 각 노드에 저장된 키만 표시
• 외부 노드에는 데이터 항목을 저장하지 않는다.
• 이진탐색트리를 중위순회(inorder traversal)하면 키가 증가하는 순서로 방문
• 적정 이진트리로 전제

 

탐색

• 키 k를 찾기 위해, 루트에서 출발하는 하향 경로를 추적
• 다음에 방문할 노드는 k와 현재 노드의 키의 크기를 비교한 결과에 따라 결정
• 잎(외부노드)에 다다르면, 키 k가 발견되지 않은 것이므로 NoSuchKey를 반환

Alg findElement(k)
	input binary search tree T, key k
    output element with key k
    
1. w <- treeSearch(root(), k)
2. if (isExternal(w))
	   return NoSuchKey
   else
   	   return element(w)

Alg treeSearch(v, k)
	input node v of a binary search tree, key k
    output node w, s.t either w is an internal node storing key k or 
    w is the external node where key k would belong if it existed
    
1. if (isExternal(v))
	   return v
2. if (k = key(v))
	   return v
   elseif (k < key(v))
   	   return treeSearch(leftChild(v), k)
   else {k > key(v)}
   	   return treeSearch(rightChild(v), k)

 

삽입

• insertItem(k, e) 작업을 수행하기 위해, 우선 키 k를 탐색
• k가 트리에 존재하지 않을 경우, 탐색은 외부노드(w)에 도착
• 외부노드 w에 k를 삽입한 후 expandExternal(w) 작업을 사용하여 w를 내부노드로 확장

Alg insertItem(k, e)
	input binary search tree T, key k, element e
    output none

1. w <- treeSearch(root(), k)
2. if (isInternal(w))
	  return
   else
   	  Set node w to (k, e)
      expandExternal(w)
      return

 

삭제: Case 1

• removeElement(k) 작업을 수행하기 위해 우선 키 k를 탐색
• k가 트리에 존재할 경우, 탐색은 k를 저장하고 있는 노드(w)에 도착
• 노드 w의 자식 중 하나가 외부노드(z)라면, reduceExternal(z) 작업을 사용하여 w와 z를 트리로부터 삭제

 

삭제: Case 2

• 삭제되어야 할 키 k가 내부노드만을 자식들로 가지는 노드(w)에 저장되어 있다면 다음과 같이 처리
  1. 트리 T에 대해 w의 중위순회후계자 y와 그 자식노드 z를 찾아낸다.
     • 노드 y는 우선 w의 오른쪽 자식으로 이동한 후, 거기서부터 왼쪽 자식들만을 끝까지 따라 내려가면 도달하게 되는 마지막 내부노드며, 노드 z는 y의 왼쪽 자식인 외부노드
     • y는 T를 중위순회할 경우 노드 w 바로 다음에 방문하게 되는 내부노드이므로 w의 중위순회 계승자(inorder successor)라 불린다.
     • 따라서 y는 w의 오른쪽 부트리 내 노드 중 가장 왼쪽으로 돌출된 내부노드
  2. y의 내용을 w에 복사
  3. reduceExternal(z) 작업을 사용하여 노드 y와 z를 삭제

Alg removeElement(k)
	input binary search tree T, key k
    output element with key k
    
1. w <- treeSearch(root(), k)
2. if (isExternal(w))
	  return NoSuchKey
3. e <- element(w)
4. z <- leftChild(w)
5. if (!isExternal(z))
	  z <- rightChild(w)
6. if (isExternal(z))	{case 1}
	  reduceExternal(z)
   else					{case 2}
   	  y <- inOrderSucc(w)
      z <- leftChild(y)
      Set node w tho (key(y), element(y))
      reduceExternal(z)
7. return e

 

이진탐색트리의 성능

• 높이 h의 이진탐색트리를 사용하여 구현된 n항목의 사전을 가정하면
  • O(n) 공간 사용
  • findElement, insertItem, removeElement 작업 모두 O(h) 시간에 수행
• 높이 h는
  • 최악의 경우 O(n)
  • 최선의 경우 O(log n)

 

AVL 트리

• 트리 T의 모든 내부노드 v에 대해 v의 자식들의 좌우 높이 차이가 1을 넘지 않는 이진탐색트리 (즉, 높이균형 속성, height-balance property)
  • AVL 트리의 부트리 역시 AVL 트리
  • 높이 (또는 균형) 정보는 각 내부노드에 저장
  • n개의 항목을 저장하는 AVL 트리의 높이: O(log n)
  • findElement 작업: O(log n) 시간 소요

 

갱신 작업

• AVL 트리에 대한 삽입 및 삭제 작업은 이진탐색트리에서의 삽입 및 삭제 작업과 유사
• 삽입이나 삭제 작업의 결과 AVL 트리의 높이균형속성이 파괴될 수도 있음
• 그러므로 삽입이나 삭제 작업 후에는 혹시 생겼을지도 모를 불균형을 찾아서 수리해야 함
• 불균형을 찾는 것은 각 노드의 균형검사(balance check)를 통해, 그리고 불균형을 수리하는 것은 개조(restructure)라 불리는 작업을 통해 트리의 높이균형 속성을 회복하기 위한 계산 작업을 수행함을 의미

 

AVL 트리에서 삽입

• 삽입은 이진탐색트리에서와 동일하게 수행
• expandExternal 작업에 의해 확장된 노드 w(그리고 조상노드들)가 균형을 잃을 수 있음

Alg inserItem(k, e)
	input AVL tree T, key k, elemet e
    output none

1. w <- treeSearch(root(), k)
2. if (isInternal(w))
	  return
   else
   	  Set node w to (k, e)
      expandExternal(w)
      searchAndFixAfterInsertion(w)
      return

Alg searchAndFixAfterInsertion(w)
	input internal node w
    output none

1. w에서 T의 루트로 향해 올라가다가 처음 만나는 불균형 노드를 z라 하자
   (그러한 z가 없다면 exit)
2. z의 높은 자식을 y라 하자.
   {수행 후, y는 w의 조상이 되는 것에 유의}
3. y의 높은 자식을 x라 하자.
   {수행 후, 노드 x가 w와 일치할 수도 있으며
   x가 z의 손자임에 유의. y의 높이는 그의 형제의 높이보다 2가 더 많다}
4. restructure(x, y, z)
   {수행 후, 이제 b를 루트로 하는 부트리의 모든 노드는 균형을 유지한다. 
   높이균형 속성은 노드 x, y, z에서 지역적으로나 전역적으로나 모두 복구된다}
5. return

 

개조 (restructure)

• 종종 회전(rotation)이라고도 불림
• 3-노드 개조(trinode restructure)
  • 3대의 직계 노드 x, y(x의 부모), z(y의 부모)의 중위순회 순서 a < b < c를 회전축으로 하여 수행
• 단일 회전 (single rotation)
  • 만약 b = y면, y를 중심으로 z를 회전
• 이중 회전 (double rotation)
  • 만약 b = x면, x를 중심으로 y를 회전한 후, 다시 x를 중심으로 z를 회전
• 좌우대칭 포함하여 모두 4종류의 회전 유형 존재

 

개조를 위한 통합 알고리즘

• 4가지 유형의 회전(대칭 모양에 대한 단일 및 이중회전)이 restructure 작업에 모두 반영되어 있음
• T의 모든 노드의 중위순회 순서는 보존
• T의 O(1)개 노드의 부모-자식 관계만 수정

Alg restructure(x, y, z)
	input a node x of a binary search tree T
    	that has both a parent y and a grandparent z
    output tree T after restructuring involving
    	nodes x, y and z

1. x, y, z의 중위순회 방문 순서의 나열을 (a, b, c)라 하자.
2. x, y, z의 부트리들 가운데 x, y, z를 루트로 하는 부트리를
   제외한 4개의 부트리들의 중위순회 방문순서의 나열을
   (T0, T1, T2, T3)라 하자.
3. z를 루트로 하는 부트리를 b를 루트로 하는 부트리로 대체.
4. T0과 T1을 각각 a의 왼쪽 및 오른쪽 부트리로 만든다.
5. T2와 T3를 각각 c의 왼쪽 및 오른쪽 부트리로 만든다.
6. a와 c를 각각 b의 왼쪽 및 오른쪽 자식으로 만든다.
7. return b

 

AVL 트리에서 삭제

• 삭제는 이진탐색트리에서와 동일하게 수행
• reduceExternal 작업에 의해 삭제된 노드의 부모노드 w(그리고 조상노드들)가 불균형을 초래할 수 있음

Alg removeElement(k)
	input AVL tree T, key k
    output element with key k
    
1. w <- treeSearch(root(), k)
2. if (isExternal(w))
	  return NoSuchKey
3. e <- element(w)
4. z <- leftChild(w)
5. if (!isExternal(z))
	  z <- rightChild(w)
6. if (isExternal(z))	{case 1}
	  zs <- reduceExternal(z)
   else					{case 2}
   	  y <- inOrderSucc(w)
      z <- leftChild(y)
      Set node w tho (key(y), element(y))
      zs <- reduceExternal(z)
7. searchAndFixAfterRemoval(parent(zs))
8. return e

Alg searchAndFixAfterRemoval(w)
	input internal node w
    output none

1. w에서 T의 루트로 향해 올라가다가 처음 만나는
   불균형 노드를 z라 하자. (그러한 z가 없다면 exit)
2. z의 높은 자식을 y라 하자.
   {수행 후, y는 w의 조상이 아닌 z의 자식의 되는 것 유의}
3. 다음과 같이 하여 y의 자식 중 하나를 x라 하자. y의 두 자식 중
   어느 한쪽이 높으면 높은 자식을 x라 하고, 두 자식의 높이가
   같으면 둘 중 y와 같은 쪽의 자식을 x로 선택
4. b <- restructure(x, y, z)
   {수행 후, 높이균형 속성은, 방금전 z를 루트로 했으나
   이젠 변수 b를 루트로 하는 부트리에서 지역적으로 복구된다.
   하지만 방금의 개조에 의해 b를 루트로 하는 부트리의 높이가
   1 줄어들 수 있으며 이 때문에 b의 조상이 균형을 잃을 수 있다.
   즉, 삭제 후 1회의 개조만으로는 높이균형 속성을 전역적으로
   복구하지 못할 수도 있다}
5. T를 b의 부모부터 루트까지 올라가면서 균형을 잃은 노드를 찾아
   수리하는 것을 계속

 

AVL 트리의 성능

• AVL 트리를 사용하여 구현된 n개의 항목으로 이루어진 사전을 전제하면
  • 공간사용량: O(n)
  • 높이: O(log n)
  • 3-노드 개조, 즉 한 번의 restructure: O(1)
    • 연결 이진트리 사용을 전제
  • findElement: O(log n)
    • 개조 불필요
  • insertItem, removeElement: O(log n)
    • 초기의 treeSearch: O(log n)
    • 트리를 올라가면서 개조를 수행하여 높이균형을 회복: O(log n)