Binary Search Tree - How To Save and Restore

binary search tree를 다른 곳에 저장했다가, 원할때 다시 불러와야 하는 상황을 상상해보자. 예를 들면... 노트북에 랜섬웨어가 들어와서 공장초기화를 해야 하는데 이 binary search tree는 남겨두고 싶어서 usb에 넣어놨다가 복원 후 가져와야 한다든지..

 

아무튼 그런 상황에서 binary search tree를 저장하고 불러오는 방법은 두 가지로 생각해볼 수 있다. 

 

1. binary search tree의 형태 그대로 저장한 후 원본 그대로 복원

2. binary serach tree내 키들을 정렬된 상태로 저장한 후 더 balanced된 상태로 복원

 

각각을 자세히 살펴보자.

 

1. binary search tree의 형태 그대로 저장한 후 원본 그대로 복원

 

형태 그대로 저장한다는 말이 실제로 binary seach tree를 모든 ADT(insert, delete, retrieval, ...)와 함께 usb에 넣는다는 의미는 아니다. 저장 형태는 배열이다. 여기서 형태 그대로 저장한다는 것은, 저장된 배열을 단순히 차례대로 트리에 insert했을 때 원본 그대로의 트리가 나타나도록 저장한다는 것이다. 이건 preorder로 트리를 순회하면서 배열에 기록해놓고 이 배열을 저장하면 간단히 해결된다. 예를 들어서

 

           5

         /    \

       3      7

     /   \   /   \

   1     4 6    9

 

이런 형태의 binary search tree는 preorder로 순회하면서 배열에 기록했을때 

 

[5, 3, 1, 4, 7, 6, 9]

 

로 기록될 것이고 이걸 다시 차례대로 빈 binary serach tree에 insert하면 원본과 똑같은 것이 만들어진다.

 

 

2. binary serach tree내 키들을 정렬된 상태로 저장한 후 더 balanced된 상태로 복원

 

이 경우에는 조금 더 복잡하다. 정렬된 상태로 저장하는 것은 그냥 inorder로 저장하면 되지만, 이걸 복원할 때 써먹을 알고리즘을 따로 생각해야 한다. 위의 예시로 다시 생각해보자.

 

           5

         /    \

       3      7

     /   \   /   \

   1     4 6    9

 

이걸 inorder로 저장하면 정렬된 상태로 저장된다.

 

[1, 3, 4, 5, 6, 7, 9]

 

문제는 복원할때인데, 가운데 값 5부터 root로 삼고, 1/4 가량 지점의 값 3을 left로, 3/4 가량 지점의 값 7을 right로, 1/8 가량 지점을 left의 left로... 만들어야 한다. 이는 재귀를 이용해 구현할 수 있다.

 

def restore(L): # L은 배열을 의미
    
    if not L:
        return None
        
    middle_index = len(L) // 2
    node.val = L[middle_index]
    node.left = restore(L[:middle_index])
    node.right = restore(L[middle_index + 1:])
    return node

 

그럼 왜 이 방식을 굳이 써야 할까? 지금 든 예시는 이미 balanced되어있는 binary search tree를 저장했다가 복원한 것이지만, balanced되지 않은 binary search tree, 예를 들면 

 

     1

      \

       2

         \

           3

             \

              4

                \

                 5

     

이런 트리의 경우에는

 

[1, 2, 3, 4, 5]

 

로 저장이 될 것이고, 복원되었을 때는

 

        3

      /   \

    2      4

   /          \

1              5

 

의 complete binary tree가 될 수 있다. 즉 어떤 식으로 저장된 binary search tree이든 저장했다가 복원했을 때 complete binary tree가 될 수 있는 것이다. 따라서 2.번 방식이 좀더 나을 것이다.