[Red Black Tree] 2. 파이썬으로 RB Tree 구현

1. 리눅스 C 개발 환경 구성 / RB Tree 이해

2. 파이썬으로 RB Tree 구현

3. C언어 기초 문법 공부

4. 파이썬으로 작성된 RB Tree를 C 코드로 번역

5. C에서 추가적으로 구현해야 할 부분(포인터 사용, 메모리 할당 및 삭제 등) 공부 후 구현

6. testcase 검사 후 에러 부분 보수

 

 

정글 week05의 docs에 와닿는 글이 있었다.

 

좋은 성능만큼 개발 및 유지 보수에 비용이 들기 때문에 대부분의 첫 개발은 성능을 포기하고 고급언어로 대충 개발합니다. 그러나, 서비스가 커짐에 따라 대체로 다음과 같은 최적화 과정을 거칩니다.

1. 일단 기계 대수를 늘려서 현재 서비스 수요를 감당
2. 성능에 영향을 주는 주요 부분들, 즉 매우 많이 실행되거나 고성능이 요구되는 부분을 분리
3. 해당 부분의 계산 복잡도가 충분히 낮지 않으면 알고리즘적 최적화 수행 혹은 문제 단순화
4. 그래도 문제가 해결되지 않으면 C/C++ 언어로 개발해서 해당 부분의 성능 향상 및 경쟁력 강화

이런 과정을 거치면 전체적인 성능향상을 이루면서도 개발 비용이 많이 드는 C/C++로 개발하는 부분은 최소화 할 수 있습니다.

 

6주차, 7주차에야 바로 C로 구현한다 치더라도, 당장은 C에 대해 아무것도 아는게 없다.

그리고 처음인걸 감안해서인지, RB트리는 6, 7주차의 목표에 비해 '컴퓨터의 구조적 부분'과는 멀다(고 생각한다).

그래서 일단 파이썬으로 구현한 뒤 C로 전환해서 필요한 부분을 고치는게 효율적이라 생각했다.

모르는 구조를 모르는 언어로 구현하면 이게 알고리즘을 잘못 이해한건지 문법적으로 구멍이 생긴건지도 모르지만, 일단 파이썬으로 완벽히 돌아가는 알고리즘을 구현하면, C코드에서 나오는 모든 오류는 알고리즘과는 무관하게 된다.

 

결국 C 공부는 일단 미루고 RB트리의 구현부터 시작

 

class NODE() :
    def __init__(self, data) : 
        self.data = data
        self.red = True
        self.parent = None
        self.left = None
        self.right = None
 
class RBT() : 
    def __init__(self) : 
        self.root = None
        self.input = None
    
    def searchdown(self, N, v) : 
        if N == None or N.data == v : 
            return N
        if N.data < v : 
            return self.searchdown(N.right, v)
        else : 
            return self.searchdown(N.left, v)
 
    def falldown(self, N, P, v) : 
        if N == None : 
            N = NODE(v)
            N.parent = P
            self.input = N
        else : 
            if v <= N.data : 
                N.left = self.falldown(N.left, N, v)
            else : 
                N.right = self.falldown(N.right, N, v)
        return N
 
    def grandparent(self, N) : 
        if N == None or N.parent == None : 
            return None
        return N.parent.parent
 
    def uncle(self, N) : 
        G = self.grandparent(N)
        if G == None : 
            return None
        if G.right == N.parent : 
            return G.left
        return G.right
    
    def bro(self, N) : 
        if N == None or N.parent == None : 
            return None
        if N == N.parent.left : 
            return N.parent.right
        return N.parent.left
    
    def child(self, N) : 
        if N.left != None : 
            C = N.left
        elif N.right != None : 
            C = N.right
        else : 
            C = NODE(None)
            C.red = False
            C.parent = N
        return C
        
    def insert(self, P, data) : 
        self.root = self.falldown(self.root, P, data)
        self.resort(self.input)
 
    def resort(self, N) : 
        if N.parent == None : 
            N.red = False
            return
        elif not N.parent.red : 
            return
        else : 
            self.recolor(N)
    
    def recolor(self, N) : 
        U = self.uncle(N)
        if U != None and U.red : 
            G = self.grandparent(N)
            G.red = True
            U.red = False
            N.parent.red = False
            self.resort(G)
        else : 
            self.rotation(N)
    
    def rotation(self, N) : 
        G = self.grandparent(N)
        if G.right == N.parent and N == N.parent.left : 
            self.cw(N)
            N = N.right
        elif G.left == N.parent and N == N.parent.right : 
            self.ccw(N)
            N = N.left       
        G = self.grandparent(N)
        G.red = True
        N.parent.red = False
        if N == N.parent.left : 
            self.cw(N.parent)
        else : 
            self.ccw(N.parent)
 
    def cw(self, N) : 
        G = self.grandparent(N)
        if G != None : 
            if G.left == N.parent : 
                G.left = N
            else : 
                G.right = N
        N.parent.parent = N
        N.parent.left = N.right
        if N.right != None : 
            N.right.parent = N.parent
        N.right = N.parent
        N.parent = G
        if G == None : 
            self.root = N
    
    def ccw(self, N) : 
        G = self.grandparent(N)
        if G != None : 
            if G.left == N.parent : 
                G.left = N
            else : 
                G.right = N
        N.parent.parent = N
        N.parent.right = N.left
        if N.left != None : 
            N.left.parent = N.parent
        N.left = N.parent
        N.parent = G
        if G == None : 
            self.root = N
 
    def leftest(self, N) : 
        if N.left == None : 
            return N
        return self.leftest(N.left)
    
    def rightest(self, N) : 
        if N.right == None : 
            return N
        return self.rightest(N.right)
 
    def delete(self, N) : 
        C = self.child(N)
        if N.parent == None : 
            if C.data == None : 
                self.root = None
            else : 
                self.root = C
                C.red = False
                C.parent = None
            return
        if N.red : 
            if N == N.parent.left : 
                N.parent.left = None
            else : 
                N.parent.right = None
            return
        if not N.red and C.red : 
            C.parent = N.parent
            C.red = False
            if N == N.parent.left : 
                N.parent.left = C
            else : 
                N.parent.right = C
            return
        else : 
            C.parent = N.parent
            if N == N.parent.left : 
                N.parent.left = C
            else : 
                N.parent.right = C
            self.rotationD(C)
            if C == C.parent.left : 
                C.parent.left = None
            else : 
                C.parent.right = None
    
    def rotationD(self, N) : 
        if N.parent == None : 
            return
        B = self.bro(N)
        if B.red : 
            B.red = False
            B.parent.red = True
            if B == B.parent.left : 
                self.cw(B)
            else : 
                self.ccw(B)
        self.rebalance(N)
    
    def rebalance(self, N) : 
        B = self.bro(N)
        if not N.parent.red and not B.red and B.left == None and B.right == None : 
                B.red = True
                self.rotationD(N.parent)
                return
        self.replace(N)
 
    def replace(self, N) : 
        B = self.bro(N)
        if N.parent.red and not B.red and B.left == None and B.right == None : 
            B.red = True
            N.parent.red = False
            return
        if not B.red : 
            if N == N.parent.left and B.left != None and B.left.red : 
                B.red = True
                B.left.red = False
                self.cw(B.left)
            elif N == N.parent.right and B.right != None and B.right.red : 
                B.red = True
                B.right.red = False
                self.ccw(B.right)
        B = self.bro(N)
        B.red = N.parent.red
        N.parent.red = False
        if N == N.parent.left : 
            if B.right != None : 
                B.right.red = False
            self.ccw(B)
        else : 
            if B.left != None : 
                B.left.red = False
            self.cw(B)
            
    def inorder(self, N, array, n) : 
        if N.left != None : 
            self.inorder(N.left, array, n)
        if len(array) == n : 
            return
        array.append(N.data)
        if N.right != None : 
            self.inorder(N.right, array, n)
 
    def tree_insert(self, key) : 
        self.insert(None, key)
 
    def tree_find(self, key) : 
        return self.searchdown(self.root, key)
    
    def tree_erase(self, v) : 
        N = self.searchdown(self.root, v)
        if N == None : 
            return
        if N.left != None and N.right != None : 
            D = self.rightest(N.left)
            N.data, D.data = D.data, N.data
        else : 
            D = N
        self.delete(D)
    
    def tree_min(self) : 
        return self.leftest(self.root)
 
    def tree_max(self) : 
        return self.rightest(self.root)
 
    def tree_to_array(self, array, n) : 
        self.inorder(self.root, array, n)
 
 
# 파이썬은 알아서 할당해주므로 new_tree(), delete_tree()는 C에서 따로 구현 필요

 

C언어로의 번역을 고려해서 필요하지 않는 변수 선언은 최대한 줄이고 클래스의 형태로 구현했다.

(클래스를 쓰면 C의 스트럭쳐에 포인터를 쓰는 것과 구조가 비슷해진다 카더라)

line 239까지는 요구받은 기능들을 수행하기 위해 클래스 내부에서 돌아가는 함수이고

line240부터는 위의 내부함수들을 이용해 요구받은 포맷대로 인풋과 아웃풋을 지켜 구현한 함수이다.

 

 

line 243 ~ 244, 14 ~ 20

tree_find(v)

내부함수 searchdown(N, v)을 루트에서 실행시킨다.

searchdown은 현재 노드 N의 값(N.data)이 찾는 값 v와 같은지 재귀적으로 탐색하는 함수이다. (line 14 ~20)

탐색은 트리의 구조를 바꾸지 않으므로 일반적인 이진 탐색 트리와 구조가 같다.

 

line 240 ~ 241, 22 ~ 45, 65 ~ 135

tree_insert(v)

내부함수 insert(P, v)를 실행시킨다. insert는 searchdown과 유사한 구조의 함수 falldown을 루트에서 실행시킨다.  falldown이 재귀적으로 노드를 생성할 위치에 도달하면, 그곳의 null leaf를 값이 v이고 부모가 P인 노드로 바꾼다. 여기까지는 일반적인 이진 탐색 트리와 구조가 같다.

이후 RB트리의 규칙대로 노드를 재정렬하는 함수 resort를 self.input(방금 삽입한 노드)에 대해 실행한다. (line 67)

resort는 self.input과 그 주변 노드가 어떤 상태이냐에 따라 분기하여 색을 바꾸는 함수 recolor, 노드의 위치를 바꾸는 함수 rotation 등을 실행시킨다.

 

line 257 ~ 271, 137 ~ 145

tree_min(), tree_max()

RB트리는 이진 탐색 트리의 일종이므로 가장 왼쪽, 가장 오른쪽 노드가 최소, 최댓값이다.

재귀적으로 left, right를 호출하는 내부함수 leftest, rightest를 root에서 실행시켜 min, max를 return한다.

 

line 246 ~ 255, 47 ~ 63, 147 ~ 229

tree_erase(v)

searchdown으로 삭제하려는 노드를 찾는다.

만약 삭제하려는 노드가 자식이 둘이라면 삭제시 노드의 위 아래 모두 재정렬이 필요해 굉장히 까다로울 것이다. 그러므로 .left에서 rightest를 실행(혹은 .right에서 leftest를 실행)하여, 삭제하려는 노드의 위치에 넣어도 무관한 (= 삭제하려는 값과 가장 가까운 값을 가진) 트리 맨 밑의 노드 하나를 찾아 그것과 값을 서로 바꾼다. 그 후 노드를 삭제하는 내부함수 delete를 실행한다. (line 255)

delete는 insert 때와 마찬가지로, D와 그 주변 노드가 어떤 상태이냐에 따라 분기하여 삭제 후의 트리가 RB트리 조건을 만족시키도록 재정렬한다.

 

insert와 delete는 결국 기능보다도 그 기능을 하기 위한 case의 분기가 더 중요한데, 이건 교재를 보거나 그림과 함께 설명된 위키를 보는게 이해가 빠른 것 같다.

 

line 263 ~ 265, 231 ~ 238

tree_to_array(array, n)

이진 탐색 트리는 오른쪽으로 갈수록 값이 크므로 중위 순회를 하면 오름차순으로 값을 뽑을 수 있다.

중위 탐색으로 array에 값을 넣는 재귀함수 inorder를 실행시켜 arrray에 값을 담는다.