AVL 트리(Andelson-Velsky and Landis Tree)

2021. 6. 29. 23:54

읽기 전

불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
개인적으로 배운 점을 정리한 글입니다.

AVL 트리란?

최초의 자가 균형 이진 탐색 트리이다. 기존의 이진 탐색 트리는 사향이진트리를 형성할 가능성이 있어 최악의 경우 시간복잡도가 $O(n)$이었다. 이 문제점을 해결하기 위해 스스로 균형을 잡게끔 노드들을 조정한다.

AVL 트리의 성질

높이 균형 성질(height-balance property): 트리 T의 모든 내부 노드에 대해 자식 노드들의 높이 차가 1 이하이다.
임의의 이진 탐색 트리 T가 높이 균형 성질을 만족할 때 AVL 트리라고 한다.
AVL 트리의 높이 h는 $log\ n$이다.
BST에서의 검색 시간복잡도는 $O(h)$이므로 $O(log\ n)$이다.
모든 노드에 대해 높이 균형 성질을 만족하므로 최선 / 최악 모두 $O(log\ n)$의 시간복잡도를 갖는다.

삽입 / 삭제 시 트리의 높이 균형이 맞지 않을 수 있어 이를 해결하기 위해 자체적으로 트리의 일부를 왼쪽 혹은 오른쪽으로 회전(rotation)시킨다.

다만, 로테이션 과정에 속도 지연이 발생하여 탐색은 신속하나 삽입 / 제거 시 Red-Black Tree보다 느리다. 트리의 균형을 맞추기 위한 Rotation 여부를 결정하는 중요한 개념 중 하나가 Balance Factor(BF)이다.

균형 인수(Balance Facotr, BF)

특정 노드의 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값이다. 표현은 BF = hL- hR이라 한다. 각 노드의 BF 값이 -1 or 0 or 1인 경우에만 균형이 잡힌 트리로 간주한다. (AVL 트리의 조건이 높이 균형 성질을 만족이므로)

노드의 양쪽 서브트리의 높이가 같으면 hL=hR이 되어 BF는 0이다. 리프 노드 또한 양 옆의 상태가 같으므로 BF는 0이다.

Data Structure_AVL_Tree_001

위 그림처럼 각 노드의 BF 절대값이 $|BF| \le 1$을 만족하므로 AVL Tree라 할 수 있다.

Rotation

Left, Right Rotation

Data Structure_AVL_Tree_002

format A에서 format B로 변환 시 좌측 서브트리가 끌려 올라간다. 이는 시계 방향으로 회전하는 것과 유사하여 우측으로 회전하는 의미의 Right Rotation이라 한다.

format B에서 format A로 변환시 우측 서브트리가 끌려 올라간다. 이는 시계 방향으로 회전하는 것과 유사하여 우측으로 회전하는 의미의 Left Rotation이라 한다.

python code

    def _left_rotate(self, cur):
        v = cur
        w = cur.right
        t = w.left
        cur = w
        w.left = v
        v.right = t
        v.height = 1 + max(self._get_height(v.left), self._get_height(v.right))
        w.height = 1 + max(self._get_height(w.left), self._get_height(w.right))
        return cur

    def _right_rotate(self, cur):
        v = cur
        w = cur.left
        t = w.right
        cur = w
        w.right = v
        v.left = t
        v.height = 1 + max(self._get_height(v.left), self._get_height(v.right))
        w.height = 1 + max(self._get_height(w.left), self._get_height(w.right))
        return cur

    def _get_height(self, cur):
        if not cur:
            return 0
        return cur.height

Single Roatation

균형을 맞추기 위해 노드들을 rotate할 때 1번의 rotation만으로 트리의 균형을 맞출 수 있으면 single rotation을 수행한다.

Data Structure_AVL_Tree_003

위 그림에서 V는 이진 탐색 트리의 루트 노드, W는 V의 좌측 자식 노드, $t_3$는 V의 우측 서브트리라 하자. $t_1,\ t_2$는 W 노드의 각각 좌측, 우측 서브트리이다. $t_1,\ t_2,\ t_3$의 높이가 모드 $h$라 할 때, $t_1$에 $x$노드를 삽입해야 하는 상황이다.

$t_1$에 $x$노드 삽입 시 높이는 $h + 1$이 되고 W의 BF 값은 $h + 1 - h = 1$이 된다. 그리고 V의 좌측 서브트리의 높이는 $h + 2$가 되어 V 노드의 BF 값은 $h + 2 - h = 2$가 된다. 즉, AVL Tree의 성질에 위배된다.

좌측 서브트리를 끌어올려서 우측을 끌어내리는 Right Rotation을 수행해야 한다.

Data Structure_AVL_Tree_004

rotation을 수행하면 위 그림처럼 회전한다. BF 값을 산출하면 정상 범위로 내려왔음을 확인할 수 있다. 이제 실제 예제를 보자.

Data Structure_AVL_Tree_005

위 그림에서 8을 삽입하면 우측 서브 트리의 높이가 좌측보다 2가 더 크다. 좌측의 높이가 더 커서 끌어올렸던 것과 반대로 좌측을 끌어내려야 하므로 Left Rotation을 수행해야 한다.

Single Rotation을 수행하여 트리의 균형을 맞출 수 있는 시나리오는 다음과 같다.

V를 BF의 절대값이 2 이상이면서 새로운 노드와 가장 가까운 조상 노드라 하고, W는 V의 자식 노드이며 BF의 절대값이 1 이하인 노드라고 할 때,

W가 V의 좌측 자식 노드이고 W의 좌측 서브트리에 새로운 노드를 삽입한 경우 - Right Rotation

V의 좌측 서브트리의 좌측 서브트리에 새로운 노드가 삽입되어 BF의 절대값이 2 이상이 되었으므로 좌측 서브트리를 끌어올려야 한다. 즉, 시계 방향의 회전이 필요하므로 Right Rotation을 수행한다. - LL
W가 V의 우측 자식 노드이고 W의 우측 서브트리에 새로운 노드를 삽입한 경우 - Left Rotation

V의 우측 서브트리의 우측 서브트리에 새로운 노드가 삽입되어 BF의 절대값이 2 이상이 되었으므로 우측 서브트리를 끌어올려야 한다. 즉, 반시계 방향의 회전이 필요하므로 Left Rotation을 수행한다. - RR

Double Rotation

Single Rotation을 수행해도 삽입 결과가 조건을 충족하지 못하는 경우가 있다. 이 경우 Double Rotation을 수행해야 한다. V를 BF의 절대값이 2 이상이면서 새로운 노드와 가장 가까운 조상 노드라 하고, W를 V의 자식 노드이며 BF의 절대값이 1 이하인 노드라 할 때,

W가 V의 좌측 자식노드이고 W의 우측 서브트리에 새로운 노드를 삽입한 경우
W가 V의 우측 자식노드이고 W의 좌측 서브트리에 새로운 노드를 삽입한 경우

두 가지 케이스가 있다. 1번 케이스를 예로 들어보자.

[그림]

위 그림에서 W는 V의 좌측 자식노드이고 W의 우측 서브트리에 x 노드를 삽입한다고 하자. V 노드의 BF가 2가 되어 roatate가 필요함을 알 수 있다. 균형을 맞추기 위해서는 $t_1$을 먼저 잡아 내려서 W의 높이 균형을 개선하고 $t_4$를 잡아 내려서 V의 높이 균형을 개선하면 된다.

R을 중심으로 left rotation 수행 - $t_1$을 잡아내림
W 위치로 끌어올려진 R을 중심으로 right rotation 수행 - $t_4$를 잡아내림

Data Structure_AVL_Tree_006

좌측 서브트리의 높이 불균형을 먼저 보정한 뒤 우측 서브트리의 높이를 추가함으로써 트리의 균형이 맞출 수 있었다.

위 과정을 모두 거치면 $t_3$의 높이만 $h-1$이 되어 V, W, R의 BF 값은 각각 -1, 0, 0이고 AVL Tree의 규칙을 만족한다. 이제 구체적인 예를 들어보자.

Data Structure_AVL_Tree_007

위 그림에서 3을 추가한다고 하면 format 1은 일반적인 BST이다. 그러나 V의 BF 값이 2가 되어 rotate를 해야 한다. V의 좌측 자식 노드의 우측 서브 트리에 새로운 노드가 추가되었으므로 먼저 추가된 우측 서브트리를 좌측으로 끌어올리는 R을 중심으로 하는 left rotation을 수행한 뒤 W 위치로 끌어올려진 R을 중심으로 우측 자식노드를 끌어내리는 right rotation을 수행하면 되겠다.

AVL Tree의 값 삽입

Data Structure_AVL_Tree_008

위에서 정리한 바와 같이 삽입 과정의 시나리오는 총 4가지 이다.

새로운 노드를 추가하여 V의 BF의 절대값이 2 이상이고 V의 자식노드 $W_l,\ W_r$ 중 높이가 더 높은 쪽이 노드가 추가된 방향일 것이다.

case 1. V의 좌측 자식 노드 $W_l$의 좌측 서브트리 $t_1$에 새로운 노드를 삽입한 경우 - LL

V를 중심으로 좌측을 끌어올려야 함 -> single right rotation
case 2. V의 좌측 자식 노드 $W_l$의 우측 서브트리 $t_2$에 새로운 노드를 삽입한 경우 - LR

$W_l$를 중심으로 우측을 올리고 V를 중심으로 좌측을 올려야 함 - double rotation (left - right)
case 3. V의 우측 자식 노드 $W_r$의 좌측 서브트리 $t_3$에 새로운 노드를 삽입한 경우 - RL

$W_r$를 중심으로 좌측을 올리고 V를 중심으로 우측을 올려야 함 - double rotation (right - left)
case 4. V의 우측 자식 노드 $W_r$의 우측 서브트리 $t_4$에 새로운 노드를 삽입한 경우 - RR

V를 중심으로 우측을 끌어올려야 함 - single left rotation

삭제의 경우엔 이와 정확히 반대로 동작하므로 뭔가 외우기엔 불편하다. 좀 더 직관적으로 정리해보자.

Data Structure_AVL_Tree_009

새로운 노드를 추가한 결과 가장 먼저 BF의 절대값이 2 이상이 된 조상 노드를 V라 하자. 그리고 V의 자식노드 중 높이가 더 높은 쪽의 노드를 W라 한다. 그리고 W의 자식 노드 중 높이가 더 높은 쪽의 노드를 X라 하자. 불균형이 최소 2번은 있어야 $BF_V$의 절대값이 2 이상이 될 것이다.

case 1. W가 V의 좌측 자식 노드이며 X가 W의 좌측 노드일 경우 - Left Left - (right rotation)

V를 중심으로 right rotation 수행 시 높이가 작아 불균형을 일으켰던 우측 자식노드에 배치되어 전체 트리의 최대 높이(현재는 좌측)가 1 감소, 우측 트리의 높이가 1 증가해 V의 BF가 2감소한다.
case 2. W가 V의 좌측 자식 노드이며 X가 W의 우측 노드일 경우 - Left Right - (left - right rotation)

right rotation 적용해 $X$를 우측에 붙이면 단순히 옆 노드로 이동했을 뿐이라 BF가 개선되지 않는다. 따라서 W를 중심으로 left rotation 수행하여 불균형 상태를 case 1로 만든다.
case 3. W가 V의 우측 자식 노드이며 X가 W의 좌측 노드일 경우 - Right Left - (right - left rotation)

left rotation 적용해 X를 좌측에 붙이면 단순히 옆 노드로 이동했을 뿐이라 BF가 개선되지 않는다. 따라서 W를 중심으로 right rotation 수행하여 불균형 상태를 case 4로 만든다.
case 4. W가 V의 우측 자식 노드이며 X가 W의 우측 노드일 경우 - Right Right - (left rotation)

V를 중심으로 left rotation 수행 시 높이가 작아 불균형을 일으켰던 좌측 자식노드에 배치되어 전체 트리의 최대 높이(현재는 우측)가 1 감소, 좌측 트리의 높이가 1 증가해 V의 BF가 2 감소한다.

python 코드

    def insert(self, val):
        self.root = self._insert_node(self.root, val)

    def _insert_node(self, cur, val):
        if not cur: # None이면 신규노드 추가하여 리턴
            return TreeNode(val)
        elif val < cur.val: # 현재 값보다 작으면 좌측 탐색
            cur.left = self._insert_node(cur.left, val)
        elif val > cur.val: # 현재 값보다 크면 우측 탐색
            cur.right = self._insert_node(cur.right, val)

        cur.height = 1 + max(self._get_height(cur.left), self._get_height(cur.right)) # 추가한 뒤 height 갱신
        balance = self._get_balance(cur) # bf 값 산출

        if balance > 1 and val < cur.left.val: # 좌측 자식노드의 좌측 트리에 추가
            cur = self._right_rotate(cur) # 좌측 자식 노드 끌어올리기
        elif balance > 1 and val > cur.left.val: # 좌측 자식노드의 우측 트리에 추가
            cur.left = self._left_rotate(cur.left) # 자식노드의 우측 끌어올림
            cur = self._right_rotate(cur) # 좌측 자식 노드 끌어올림
        elif balance < -1 and val < cur.right.val: # 우측 자식노드의 좌측 트리에 추가
            cur.right = self._right_rotate(cur.right) # 자식노드의 좌측 끌어올림
            cur = self._left_rotate(cur) # 우측 자식 노드 끌어올림
        elif balance < -1 and val > cur.right.val: # 우측 자식노드의 우측 트리에 추가
            cur = self._left_rotate(cur) # 우측 자식 노드 끌어올림

    def _get_balance(self, cur):
        if not cur:
            return 0
        return self._get_height(cur.left) - self._get_height(cur.right)

AVL Tree의 값 삭제

AVL Tree에서의 삭제는 BST에서의 삭제 시 고려사항과 Balance를 맞춰야하기 떄문에 조금 까다롭다. 삭제 시 삭제할 노드의 자식 노드의 개수를 고려하여 삭제를 했다 하자. 일반적인 BST 삭제 과정과 동일하므로 설명은 생략한다. 참고 포스트 -이진탐색트리(Binary Search Tree, BST)

삭제가 끝나면 삽입과정과 마찬가지로 4가지의 시나리오가 발생한다.

Data Structure_AVL_Tree_009

방금과 마찬가지로 삽입 / 삭제 과정에 초점을 맞추지 않고 변경이 발생한 다음 상태에 초점을 두고 결과론적으로 접근하면 된다.

새로운 노드를 추가한 결과 가장 먼저 BF의 절대값이 2 이상이 된 조상 노드를 V라 하자. 그리고 V의 자식노드 중 높이가 더 높은 쪽의 노드를 W라 한다. 그리고 W의 자식 노드 중 높이가 더 높은 쪽의 노드를 X라 하자.

case 1. W가 V의 좌측 자식 노드이며 X가 W의 좌측 노드일 경우 - Left Left - (right rotation)

V를 중심으로 right rotation 수행 시 높이가 작아 불균형을 일으켰던 우측 자식노드에 배치되어 전체 트리의 최대 높이(현재는 좌측)가 1 감소, 우측 트리의 높이가 1 증가해 V의 BF가 2감소한다.
case 2. W가 V의 좌측 자식 노드이며 X가 W의 우측 노드일 경우 - Left Right - (left - right rotation)

right rotation 적용해 $X$를 우측에 붙이면 단순히 옆 노드로 이동했을 뿐이라 BF가 개선되지 않는다. 따라서 W를 중심으로 left rotation 수행하여 불균형 상태를 case 1로 만든다.
case 3. W가 V의 우측 자식 노드이며 X가 W의 좌측 노드일 경우 - Right Left - (right - left rotation)

left rotation 적용해 X를 좌측에 붙이면 단순히 옆 노드로 이동했을 뿐이라 BF가 개선되지 않는다. 따라서 W를 중심으로 right rotation 수행하여 불균형 상태를 case 4로 만든다.
case 4. W가 V의 우측 자식 노드이며 X가 W의 우측 노드일 경우 - Right Right - (left rotation)

V를 중심으로 left rotation 수행 시 높이가 작아 불균형을 일으켰던 좌측 자식노드에 배치되어 전체 트리의 최대 높이(현재는 우측)가 1 감소, 좌측 트리의 높이가 1 증가해 V의 BF가 2 감소한다.

python 코드

    def delete(self, val):
        self.root = self._delete_node(self.root, val)

    def _delete_node(self, cur, val):
        if not cur:
            return False
        elif cur == self.root and cur.val == val:
            if cur.left and cur.right:
                pre_val = self._find_predecessor(cur.left)
                self._delete_node(cur, pre_val)
                cur.val = pre_val
            elif cur.left or cur.right:
                if cur.left:
                    self.root = cur.left
                elif cur.right:
                    self.root = cur.right
            else:
                self.root = None

        elif cur.left and cur.left.val == val:
            if cur.left.left and cur.left.right:
                pre_val = self._find_predecessor(cur.left.left)
                self._delete_node(cur, pre_val)
                cur.left.val = pre_val
                cur.left.height = 1 + \
                    max(self._get_height(cur.left.left),
                        self._get_height(cur.left.right))
            elif cur.left.left or cur.left.right:
                if cur.left.left:
                    cur.left = cur.left.left
                elif cur.left.right:
                    cur.left = cur.left.right
                cur.left.height = 1 + \
                    max(self._get_height(cur.left.left),
                        self._get_height(cur.left.right))
            else:
                cur.left = None
            cur.height = 1 + max(self._get_height(cur.left),
                                 self._get_height(cur.right))

        elif cur.right and cur.right.val == val:
            if cur.right.left and cur.right.right:
                pre_val = self._find_predecessor(cur.right.left)
                self._delete_node(cur, pre_val)
                cur.right.val = pre_val
                cur.right.height = 1 + \
                    max(self._get_height(cur.right.left),
                        self._get_height(cur.right.right))
            elif cur.right.left or cur.right.right:
                if cur.right.left:
                    cur.right = cur.right.left
                elif cur.right.right:
                    cur.right = cur.right.right
                cur.right.height = 1 + \
                    max(self._get_height(cur.right.left),
                        self._get_height(cur.right.right))
            else:
                cur.right = None
            cur.height = 1 + max(self._get_height(cur.left),
                                 self._get_height(cur.right))

        elif cur.val > val:
            cur.left = self._delete_node(cur.left, val)

        elif cur.val < val:
            cur.right = self._delete_node(cur.right, val)

        balance = self._get_balance(cur)
        if balance > 1 and self._get_balance(cur.left) >= 0:
            cur = self._right_rotate(cur)
        elif balance > 1 and self._get_balance(cur.left) < 0:
            cur.left = self_left_rotate(cur,left)
            cur = self._right_rotate(cur)
        elif balance < -1 and self._get_balance(cur.right) > 0:
            cur.right = self._right_rotate(cur.right)
            cur = self._left_rotate(cur)
        elif balance < -1 and self._get_balance(cur.right) <= 0:
            cur = self._left_rotate(cur)
        return cur

전체 코드

class TreeNode:
    def __init__(self, val, left=None, right=None, height=1):
        self.val = val
        self.left = left
        self.right = right
        self.height = height # 높이를 뜻하는 height 속성 추가 기본값=1


class AVLtree:
    def __init__(self, val):
        self.root = TreeNode(val)

    def insert(self, val):
        self.root = self._insert_node(self.root, val)

    def delete(self, val):
        self.root = self._delete_node(self.root, val)

    def _insert_node(self, cur, val):
        if not cur:
            return TreeNode(val)
        elif val < cur.val:
            cur.left = self._insert_node(cur.left, val)
        elif val > cur.val:
            cur.right = self._insert_node(cur.right, val)

        cur.height = 1 + max(self._get_height(cur.left),
                             self._get_height(cur.right))

        balance = self._get_balance(cur)
        if balance > 1 and val > cur.left.val: # Left-Right case
            cur.left = self._left_rotate(cur.left)
            cur = self._right_rotate(cur)

        elif balance > 1 and val < cur.left.val: # Left-Left case
            cur = self._right_rotate(cur)

        elif balance < -1 and val > cur.right.val: # Right-Right case
            cur = self._left_rotate(cur)

        elif balance < -1 and val < cur.right.val: # Right-Left case
            cur.right = self._right_rotate(cur.right)
            cur = self._left_rotate(cur)
        return cur

    def _delete_node(self, cur, val):
        if not cur:
            return False
        elif cur == self.root and cur.val == val:
            if cur.left and cur.right:
                pre_val = self._find_predecessor(cur.left)
                self._delete_node(cur, pre_val)
                cur.val = pre_val
            elif cur.left or cur.right:
                if cur.left:
                    self.root = cur.left
                elif cur.right:
                    self.root = cur.right
            else:
                self.root = None

        elif cur.left and cur.left.val == val:
            if cur.left.left and cur.left.right:
                pre_val = self._find_predecessor(cur.left.left)
                self._delete_node(cur, pre_val)
                cur.left.val = pre_val
                cur.left.height = 1 + \
                    max(self._get_height(cur.left.left),
                        self._get_height(cur.left.right))
            elif cur.left.left or cur.left.right:
                if cur.left.left:
                    cur.left = cur.left.left
                elif cur.left.right:
                    cur.left = cur.left.right
                cur.left.height = 1 + \
                    max(self._get_height(cur.left.left),
                        self._get_height(cur.left.right))
            else:
                cur.left = None
            cur.height = 1 + max(self._get_height(cur.left),
                                 self._get_height(cur.right))

        elif cur.right and cur.right.val == val:
            if cur.right.left and cur.right.right:
                pre_val = self._find_predecessor(cur.right.left)
                self._delete_node(cur, pre_val)
                cur.right.val = pre_val
                cur.right.height = 1 + \
                    max(self._get_height(cur.right.left),
                        self._get_height(cur.right.right))
            elif cur.right.left or cur.right.right:
                if cur.right.left:
                    cur.right = cur.right.left
                elif cur.right.right:
                    cur.right = cur.right.right
                cur.right.height = 1 + \
                    max(self._get_height(cur.right.left),
                        self._get_height(cur.right.right))
            else:
                cur.right = None
            cur.height = 1 + max(self._get_height(cur.left),
                                 self._get_height(cur.right))

        elif cur.val > val:
            cur.left = self._delete_node(cur.left, val)

        elif cur.val < val:
            cur.right = self._delete_node(cur.right, val)

        balance = self._get_balance(cur)
        # Left-Left case
        if balance > 1 and self._get_balance(cur.left) >= 0:
            cur = self._right_rotate(cur)
        # Left-Right case
        elif balance > 1 and self._get_balance(cur.left) < 0:
            cur.left = self._left_rotate(cur.left)
            cur = self._right_rotate(cur)
        # Right-Left case
        elif balance < -1 and self._get_balance(cur.right) > 0:
            cur.right = self._right_rotate(cur.right)
            cur = self._left_rotate(cur)
        # Right-Right case
        elif balance < -1 and self._get_balance(cur.right) <= 0:
            cur = self._left_rotate(cur)
        return cur

    def _find_predecessor(self, cur):
        if cur.right:
            return self._find_predecessor(cur.right)
        else:
            return cur.val

    def _left_rotate(self, cur):
        v = cur
        w = cur.right
        t = w.left
        cur = w
        w.left = v
        v.right = t
        v.height = 1 + max(self._get_height(v.left), self._get_height(v.right))
        w.height = 1 + max(self._get_height(w.left), self._get_height(w.right))
        return cur

    def _right_rotate(self, cur):
        v = cur
        w = cur.left
        t2 = w.right
        cur = w
        w.right = v
        v.left = t2
        v.height = 1 + max(self._get_height(v.left), self._get_height(v.right))
        w.height = 1 + max(self._get_height(w.left), self._get_height(w.right))
        return cur

    def _get_height(self, cur):
        if not cur:
            return 0
        return cur.height

    def _get_balance(self, cur):
        if not cur:
            return 0
        return self._get_height(cur.left) - self._get_height(cur.right)

    def traverse(self):
        return self._print(self.root, [])

    def _print(self, cur, result):
        if cur:
            self._print(cur.left, result)
            result.append(cur.val)
            self._print(cur.right, result)
        return result

avl = AVLtree(3)
avl.insert(2)
avl.insert(5)
avl.insert(1)
avl.insert(4)
avl.insert(8)
avl.insert(7)
print(f'root balance: {avl._get_balance(avl.root)}, path: {avl.traverse()}')
avl.delete(4)
print(f'root balance: {avl._get_balance(avl.root)}, path: {avl.traverse()}')

Data Structure_AVL_Tree_010

'Algorithms > Data Structure' 카테고리의 다른 글

트라이(Trie) (0)	2021.07.05
힙(Heap) (0)	2021.07.02
이진탐색트리(Binary Search Tree, BST) (0)	2021.06.28
트리, 이진트리(Tree, Binray Tree) (0)	2021.06.27
그래프(Graph) (0)	2021.06.02

스터디룸