4.11 임의의 노드

문제 

이진 트리 클래스를 바닥부터 구현하려고 한다. 노드의 삽입, 검색, 삭제 뿐만 아니라 임의의 노드를 반환하는 getRandomNode() 매서드도 구현한다. 모든 노드를 같은 확률로 선택해주는 getRandomNode메서드를 설계하고 구현하라. 또한 나머지 메서드는 어떻게 구현할지 설명하라. 

 

접근방법

우선 문제를 보면 "이진트리에서 임의의 노드를 반환하는 알고리즘을 설계해라"와 동시에 "클래스를 바닥부터 구현하려고한다."라는 문구가 있다. 그 말은 아마도 문제 해결을 위해서는 자료구조의 내부를 접근해야한다는 것을 의미 할 것 같다.

 

이 문제의 해결법은 매우 다양하다. 느린해결법부터 빠르지만 해결되지 않는 해결법 최적의 해결법까지 차례로 생각해보자.

1. [느리지만 동작하는] 모든 노드를 배열에 복사한 뒤 임의의 원소를 반환하기 

  - TimeComplexity = O(N) , SpaceComplexity = O(N)

 

2. [느리지만 동작하는] 배열을 복사하는 대신 배열을 항상 유지하고 있다가 임의의 원소를 반환하기 

 - 이방식은 노드가 삭제 되는 경우에 배열안의 원소도 삭제해야하기 때문에 삭제연산이 O(N)이 소요된다.

 

3. [느리지만 동작하는 ] 각 노드에 중위순회에 따라 index labal을 붙여두고  getRandomNode를 호출되면 임의의 index 를 받아 해당되는 노드를 반환한다. 

 - 노드 삽입 삭제시 labal을 수정해주어야 하기 떄문에 삽입, 삭제 연산이 O(N) 소요된다.

 

4. [빠르지만 동작하지 않는] 트리를 임의의 방향으로 순회한다. 

 - 1/3의 확률로 현재 노드를 반환한다. 

 - 1/3의 확률로 왼쪽 노드를 순회한다. 

 - 1/3의 확률로 오른쪽 노드를 순회한다. 

하지만 이방식은 모든 노드를 같은 가능성으로 선택하지 않는다. root 노드가 선택될 확률은 항상 1/3이다.

 

5. [빠르게 동작하는] 트리를 임의의 방향으로 순회하지만 하위 노드의 갯수에 따라서 선택될 확률을 변경해준다.

 - 전체 노드의 갯수가 N개라고 했을때 root node가 선택될 확률은 [ 1/N ]

 - 왼쪽 노드를 순회할 확률은 [왼쪽 노드에 포함된 원소의 갯수/N ]

 - 오른쪽 노드를 순회할 확률은 [오른쪽 노드에 포함된 원소의 갯수/N ]

 이것을 구현하기 위해서는 각 노드에 size 변수를 두고 크기 정보를 확인할 수 있도록 해야한다. 

 

6. [빠르게 동작하는] 위의 방식에서 반복해서 랜덤한 수를 선택하는 비용을 줄이기 위해 한번의 임의의 수를 선택한 후 그 수를 통해 반환하는 방식을 채택해보자.

 - 위의 트리에서 getRandomNode를 호출한 뒤 왼쪽으로 순회한다고 생각해보자 

 처음에 0-5의 수가 선택되었기 때문에 왼쪽으로 순회하는 것이다. 그 이후에 5번 방식에서는 0-5수 중에 한번 더 random수를 뽑지만 기존의 수를 사용할 수 있는 방식이 없을까? 오른쪽을 선택했다고 가정해보자. 7과 8사이의 숫자를 뽑았지만 그다음에는 0-1의 수를 뽑아야한다.  이때 간단하게 뽑은 수에서 LeftSize+1 만큼 빼주면 된다. 이런식으로 하면 반복적으로 임의의 수를 뽑아낼 필요가 없어진다.

from random import randrange

class Tree:
    def __init__(self):
        self.root = None
    
    def getRandomNode():
        if root is None : return None
        rand = randrange(root.size())
        return root.getIthNode(rand)

    def insertInOrder(d):
        if root is None : root = TreeNode(d)
        else :
            root.insertInOrder(d)


class TreeNode:
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None
        self.size = 1

    def getIthNode(rand):
        left_size = left.size if left else 0
        if rand < left_size :
            return left.getIthNode(rand)
        elif rand > left_size :
            return right.getIthNode(i - (left_size+1))
        else
            return self

    def insertInOrder(self, d):
        if self.data => d :
            if self.left is None :
                self.left = TreeNode(d)
            else :
                self.left.insertInOrder(d)
        else :
            if self.right is None :
                self.right = TreeNode(d)
            else :
                self.right.insertInOrder(d)
        self.size +=1

    def size(self): return self.size
    def data(self): return self.data

    def find(self,d):
        if self.data == d :
            return self
        elif self.data > d :
            return find(self.left, d)
        else :
            return find(self.right,d)