다음 파이썬 프로그램의 실행 결과는?cnt = 0class Node: … | [7급 국가직 알고리즘] 26년 1회차 기출문제 상세 페이지

다음 파이썬 프로그램의 실행 결과는?
cnt = 0
class Node:
    def __init__(self,key,h,lf = None,rg = None):
        self.key = key
        self.h = h
        self.lf = lf
        self.rg = rg
class TREE:
    def __init__(self):
        self.r = None
    def h(self, n):
        if n == None:
            return 0
        return n.h
    def put(self, key):
        self.r = self.putitem(self.r,key)
    def putitem(self, n, key):
        if n == None:
            return Node(key, 1)
        if n.key > key:
            n.lf = self.putitem(n.lf,key)
        elif n.key < key:
            n.rg = self.putitem(n.rg,key)
        else:
            return n
        n.h = max(self.h(n.lf),self.h(n.rg)) + 1
        return self.bal(n)
    def bal(self, n):
        global cnt
        if self.bf(n) > 1:
            if self.bf(n.lf) < 0:
                n.lf = self.lf(n.lf)
                cnt += 1
            n = self.rg(n)
            cnt += 1
        elif self.bf(n) < -1:
            if self.bf(n.rg) > 0:
                n.rg = self.rg(n.rg)
                cnt += 1
            n = self.lf(n)
            cnt += 1
        return n
    def rg(self, j):
        i = j.lf
        j.lf = i.rg
        i.rg = j
        j.h = max(self.h(j.lf),self.h(j.rg)) + 1
        i.h = max(self.h(i.lf),self.h(i.rg)) + 1
        return i
    def lf(self, j):
        i = j.rg
        j.rg = i.lf
        i.lf = j
        j.h = max(self.h(j.lf),self.h(j.rg)) + 1
        i.h = max(self.h(i.lf),self.h(i.rg)) + 1
        return i
    def bf(self, n):
        return self.h(n.lf) - self.h(n.rg)
if __name__ == '__main__':
    t = TREE()
    value = [5, 22, 3, 14, 2, 19]
    for i in value:
        t.put(i)
    print(cnt)

1

2

3

4

프로그램은 회전 횟수 2를 출력한다.
코드는 AVL 트리이며, 메서드 rg는 오른쪽 회전, lf는 왼쪽 회전이고 회전 1회마다 cnt가 1 증가한다.
5, 22, 3, 14, 2 삽입: 모든 노드의 균형 인수가 -1~1 범위여서 회전 없음 → 5(왼쪽 3[2], 오른쪽 22[왼쪽 14])
19 삽입: 22 → 14의 오른쪽에 들어가 노드 22의 균형 인수가 2, 왼쪽 자식 14의 균형 인수가 -1이 된다.
LR 경우이므로 14에서 왼쪽 회전(cnt=1) 후 22에서 오른쪽 회전(cnt=2) → 5(왼쪽 3[2], 오른쪽 19[14, 22])
따라서 최종 출력은 2이다.