균형이진 트리 회전 ( rotation )

이진탐색트리(BST) 는 부모노드의 왼쪽 자식은 부모노드 키값보다 작은 노드들이 오른쪽 자식은 부모노드 키값보다 큰 노드들이 위치하게 됩니다. 이진탐색트리의 검색, 삽입, 삭제 로직은 아래 글에서 확인해주세요 ^^ 👇🏻👇🏻👇🏻👇🏻

https://p-james-y.tistory.com/19

이진 탐색 트리 ( Binary Search Tree )

이진탐색트리의 연산 시간복잡도는 최대 트리의 높이인 O(h) 입니다. 높이가 (데이터 갯수(n) - 1) 일때는 시간복잡도는 O(n)이 됩니다. 다음과 같은 경우입니다. 

높이가 n-1 인 이진탐색트리

균형이진트리는 트리의 높이를 log(n) 으로 유지 해주기 위해 조정된 트리입니다. 높이를 조정하기 위해 쓰이는 방법이 회전입니다. 

특정 노드를 기준으로 오른쪽으로 회전 또는 왼쪽으로 회전할수 있습니다. 오른쪽 회전을 그림을 통해 한번 알아보겠습니다.

 

오른쪽으로 회전 ↩️ 

오른쪽으로 회전(rotation)

 

오른쪽으로 회전하는 것을 코드로 구현해보겠습니다.

class BST:
    def __init__(self):
        self.root = None
        self.size = 0

    def __len__(self):
        return self.size

    def __iter__(self):
        return self.root.__iter__() # 노드 클래스에 있는 __iter__ 메서드를 호출 ( ex preOrder )
	
    # z노드 기준으로 오른쪽으로 회전
    def rotateRight(self, z):
    	if not z: return # z 노드가 없으면 return
        
        x = z.left # z 의 왼쪽은 x 노드
        
        if x == None: return # x 노드가 없으면 return
        
        b = x.right # x 의 오른쪽 노드는 b 노드
        x.parent = z.parent # x의 부모노드는 z의 부모노드로 링크 (1)
        
        if z.parent: # z의 부모가 있다면
            if z.parent.left == z: # z가 z 부모노드의 왼쪽 자식노드였다면
                z.parent.left = x # x가 z 부모노드의 왼쪽 자식노드로 링크 (2)
            else: # z가 z 부모노드의 오른쪽 자식노드였다면
                z.parent.right = x # x가 z 부모노드의 오른쪽 자식노드로 링크 (2)
                
        x.right = z # x의 오른쪽 자식노드는 z (3)
        z.parent = x # z의 부모노드는 x (4)
        z.left = b # z의 왼쪽 자식노드는 기존 x의 오른쪽 자식노드 (5)
        if b: b.parent = z # b의 부모노드는 z (6)
        if self.root == z: # root 노드가 z 였다면
            self.root = x # x를 루트노드로

왼쪽으로 회전 ↪️

왼쪽으로 회전

왼쪽으로 회전하는 것을 코드로 구현해보겠습니다.

class BST:
    def __init__(self):
        self.root = None
        self.size = 0

    def __len__(self):
        return self.size

    def __iter__(self):
        return self.root.__iter__() # 노드 클래스에 있는 __iter__ 메서드를 호출 ( ex preOrder )
	
    # z노드 기준으로 왼쪽으로 회전
    def rotateLeft(self, z):
    	if not z: return # z가 없으면 return
        
        x = z.right # z 의 오른쪽 자식은 x 
        
        if x == None: return # x 노드가 없으면 return
        
        b = x.left # x 의 왼쪽자식은 b
        x.parent = z.parent # x의 부모는 z로 링크 (1)
        
        if z.parent: # z의 부모가 있다면
            if z.parent.left == z: # z가 z 부모의 왼쪽 자식이었다면
                z.parent.left = x # x를 z 부모의 왼쪽 자식으로 링크 (2)
            else: # z가 z 부모의 오른쪽 자식이었다면
                z.parent.right = x # x를 z 부모의 오른쪽 자식으로로 링크 (2)
                
        x.left = z # x의 왼쪽자식은 z (3)
        z.parent = x # z의 부모는 x (4)
        z.right = b # z의 오른쪽 자식은 기존 x의 왼쪽자식 (5)
        if b: b.parent = z # b의 부모는 z (6)
        if self.root == z: # root 가 z 였다면
            self.root = x # x를 루트로

회전의 시간복잡도

회전의 시간복잡도는 노드간의 링크를 바꿔주는 것이 전부입니다. 따라서 O(1) 상수 시간이 걸립니다.

 

Reference

https://www.youtube.com/watch?v=PIidtIBCjEg&t=7s 

강의를 보며 정리하였습니다