탐색트리 연습문제

연습문제

D를 이진탐색트리로 구현된 n 항목의 순서사전이라고 가정하자. D를 위한 다음의 메쏘드를 O(n) 시간에 수행하도록 구현하라.

• elements(): 이진탐색트리로 구현된 사전 D의 모든 원소들을 반환
  그냥 선,중,후위순회로 돌아다니면 끝인거 아녀?

  Alg elements()

1. L = empty list
2. rElements(T.root(),L)
3. return L.elements()

Alg rElements(v,L)

1. if(T.isExternal(v))
   return

2. L.addLast(T.element(v))

3. rElements(T.leftChild(v),L)

4. rElements(T.rightchild(v),L)

   ### 알고리즘 treeSearch(v,k)의 비재귀 버전을 의사코드로 작성하라
   제일 왼쪽에서 시작해서 올라가면서 왼쪽 오른쪽 다 보면서 가기...?

   Alg treeSearch(v,k)

5. while(isInternal(v)){
   if(k == key(v))

    return v

   else if (k<key(v))

    v = leftChild(v)

   else {k > key(v)}

    v = rightChild(v)

   }

6. return v
   ```
   전체를 보는게 아니라 찾는 것이었다.

   비어있는 이진탐색트리에 아래 키들을 가진 항목들을 주어진 순서대로 삽입한다.

• 키 : 30, 40, 24, 58, 48, 26, 11, 13

삽입이 수행될 때마다 변화하는 트리 모습을 보여라
30 가운데로 알아서 찢어지겄지

중복 키를 가진 이진트리 응용문제에서 제시했던 탐색알고리즘 findAllElements의 다른버전을 의사코드로 작성하라.

Alg findAllElements(k)

1. L = empty list
2. w = T.root()
3. while(T.isInternal(w)){
    if(k == T.key(w)){
        L.addLast(T.element(w))
        w = T.rightChild(w)
    }
    else if (k<T.key(w))
        w = T.leftChild(w)
    else {k>T.key(w)}
        w = T.rightChild(w)
}
return L.elements()

윤하는 이진탐색트리에 특정 집단의 키들을 삽입할 때 삽입 순서는 상관이 없다고 주장한다. 즉, 동일한 키 집단에 대해서는 동일한 이진탐색트리가 생성된다는 것이다. 윤하가 옳은지 그른지 논거와 함께 설명하라

그르다. 시작 키에 따라 전혀 다른 트리가 나오기 때문이다.

그르다. 그름을 보일 수 있는 사례는 하나만이 아니다. 일례로 먼저 키 9, 5, 12, 7, 13를 주어진 순서로 삽입하여 생성된 이진탐색트리를 만들어 보인다. 다음, 앞서의 입력에서 5와 7의 순서를 뒤바꿔서, 즉 9,7,12,5,13를 삽입하여 생성된 이진탐색트리를 만들어 보인다.

윤하는 앞서 자신이 내세운 주장을 약간 수정했다. 이제 그녀는 이진탐색트리가 아니라 AVL 트리에 특정 집단의 키들을 삽입할 때 삽입 순서는 상관이 없다고 주장한다. 동일한 키 집단에 대해 동일한 AVL 트리가 생성된다는 것이다. 윤하가 옳은지 그른지 논거와 함께 설명하라.

그르다. 불균형만 안만들고 트리를 만든다면 그 트리는 모양이 전혀 다르게 여러개가 나올 것 이기 때문이다.

그르다. 그름을 보일 수 있는 사례는 하나만이 아니다. 일례로 먼저 키 9, 5, 12, 7, 13을 주어진 순서로 삽입하여 생성된 AVL트리를 만들어 보인다. 다음, 5와 7을 순서를 뒤바꿔서, 즉 키 9,7,12,5,13를 삽입하여 생성된 AVL트리를 만들어 보인다.

비어 있는 AVL트리에 아래 키들을 가진 항목들을 주어진 순서대로 삽입한다. 삽입이 수행될 때마다 변화하는 트리 모습을 보여라

• 키: 2, 1, 4, 5, 9, 3, 6, 7

배열로 표현된 n-노드 이진트리에서 회전을 수행하는데 n시간이 소요되는 이유를 설명하라

뒤에 까지 다 봐야 해서?

연결트리에서는 회전에 관여하는 부트리들의 루트만 재위치시키면 자손 노드들 까지 회전에 참여하게 된다. 하지만 배열로 표현된 n노드의 이진트리를 회전하기 위해서는 해당 노드들의 자손 노드들까지 재배치시켜야 한다. 따라서 n시간이 소요된다.

다음 AVL 트리 관련 알고리즘을 의사코드로 작성하라

• searchAndFixAfterInsertion - $\log{n}$
• searchAndFixAfterRemoval- $\log{n}$
• restructure- $\log{1}$

  Alg searchAndFixAfterInsertion(w)

1. w.left.height, w.right.height, w.height = 0,0,1
2. if(isRoot(w))
   return
3. z = w.parent
4. while(updateHeight(z)&& isBalanced(z)){
   if(isRoot(z))

    return

   z = parent(z)
   }
5. if(isBalanced(z))
   return
6. if(z.left.height > z.right.height)
   y = z.left
   else {z.left.height < z.right.height}
   y=z.right
7. if(y.left.height > y.right.height)
   x = y.left
   else {y.left.height<y.right.height}
   x = y.right
8. restructure(x,y,z)
9. return

Alg searchAndFixAfterRemovel(z)

1. while (updateHeight(z)&& izBalanced(z)){
   if(isRoot(z))

    return

   z = parent(z)
   }
2. if(isBalanced(z))
   return
3. if(z.left.height > z.right.height)
   y = z.left
   else {z.left.height < z.right.height}
   y=z.right
4. if(y.left.height > y.right.height)
   x = y.left
   else if (y.left.height<y.right.height)
   x = y.right
   else {y.left.height == y.right.height}{
   if(z.left==y)

    x = y.left

   else {z.right = y}

    x = y.right

   }
5. b = restructure(x,y,z)
6. if (isRoot(b))
   return
7. searchAndFixAfterRemoval(b.parent)

Alg restructure(x,y,z)

1. if(key(z)<key(y)<key(x)){ - 자식으로 가면서 오른쪽으로 밀리는 그래프
   a,b,c = z,y,x - 작은 순서대로 abc
   t0,t1,t2,t3 = a.left,b.left,c.left,c.right - t는 작은 순서대로
   }
   else if (key(x)<key(y)<key(z)){ - 왼쪽으로 밀리는 그래프
   a,b,c = x,y,z
   t0,t1,t2,t3 = a.left,a.right,b.right,c.right
   }
   else if (key(z)<key(x)<key(y)){
   a,b,c = z,x,y
   t0,t1,t2,t3 = a.left,b.left,b.right,c.right
   }
   else {key(y)<key(x)<key(z)} {
   a,b,c = y,x,z
   t0,t1,t2,t3 = a.left,b.left,b.right,c.right
   }
2. if (isRoot(z)){ - 가장 위에 b 만들기
   root = b
   b.parent = NULL
   }
   else if (z.parent.left = z){
   z.parent.left = b
   b.parent = z.parent
   }
   else {z.parent.left ==z} {
   z.parent.right = b
   b.parent = z.parent
   }
3. a.left, a.right = t0,t1 - a 밑에 완성시키기
4. t0.parent, t1.parent = a
5. updateHeight(a) - a완성시키기
6. c.left, c.right = t2,t3 - c밑에 완성시키기
7. t2.parent, t3.parent = c
8. updateHeight(c)
9. b.left, b.right = a,c - b 밑에 완성시키기
10. a.parent,c.parent = b
11. updateHeight(b)
12. return b

Alg updateHeight(w)

1. h = max(w.left.height, w.right.height) +1
2. if (h!= w.height){
   w.height = h
   return Treu
   }
   else
   return False

Alg isBalanced(w)

1. return |w.left.height - w.right.height|<2
   ```