탐색트리

• 저장된 데이터에 대해 탐색, 삽입, 삭제, 갱신 등의 연산을 수행할 수 있는 자료구조
• 1차원 리스트나 연결리스트는 각 연산을 수행하는데 O(N) 시간이 소요
• 스택이나 큐는 특정 작업에 적합한 자료구조.
• 탐색트리 종류
  • 이진탐색트리,
  • AVL트리,
  • 2-3트리,
  • 레드블랙트리,
  • B-트리

이진탐색(Binary Search)

정렬된 데이터의 중간에 위치한 항목을 기준으로 데이터를 두 부분으로 나누어 가며 특정 항목을 찾는 탐색방법

binary_search(left, right, t):
  if left > right: 
    return None
  
  mid = (left + right) // 2

  if a[mid] == t: 
    return mid

  if a[mid] > t:  
    binary_search(left, mid-1, t)
  else: 
    binary_search(mid+1, right, t)

이진탐색트리(Binary Search Tree)

• 이진탐색(Binary Search)의 개념을 트리 형태의 구조에 접목한 자료구조
• 트리를 중위순회(Inorder Traversal)하면 정렬되어 출력
• 이진탐색트리는 이진트리로서 각 노드가 다음과 같은 조건을 만족한다.
  • 각 노드 n의 키가 n의 왼쪽 서브트리에 있는 키들보다 (같거나) 크고, n의 오른쪽 서브트리에 있는 키들보다 작다.

class Node:
    def __init__(self, key, value, left=None, right=None): # 노드 생성자
        self.key   = key
        self.value = value 
        self.left  = left 
        self.right = right 

class BST:           
    def __init__(self): # 트리 생성자
        self.root = None 

    def get(self, k): # 탐색 연산
        return self.get_item(self.root, k)
    
    def get_item(self, n, k):
        if n == None:
            return None # key를 발견 못함
        if n.key > k: # 왼쪽 서브트리 탐색
            return self.get_item(n.left, k)
        elif n.key < k: # 오른쪽 서브트리 탐색 
            return self.get_item(n.right, k) 
        else:
            return n.value # key를 가진 노드 발견

    def put(self, key, value): # 삽입 연산
        self.root = self.put_item(self.root, key, value)
        
    def put_item(self, n, key, value):
        if n == None:
            return Node(key, value) 
        if n.key > key: # 왼쪽 서브트리에 삽입
            n.left = self.put_item(n.left, key, value)
        elif n.key < key: # 오른쪽 서브트리에 삽입
            n.right = self.put_item(n.right, key, value) 
        else: # 노드 n의 value 갱신
            n.vlaue = value
        return n

    def delete_min(self): # 최솟값 삭제
        if self.root == None:
            print('트리가 비어 있음')
        self.root = self.del_min(self.root)
        
    def del_min(self, n):
        if n.left == None:
            return n.right  # n의 오른쪽자식 리턴
        n.left = self.del_min(n.left) # n의 왼쪽자식으로 재귀호출
        return n

    def delete(self, k): # 삭제 연산
        self.root = self.del_node(self.root, k)
         
    def del_node(self, n, k):
        if n == None:
            return None
        if n.key > k: # 왼쪽자식으로 이동
            n.left = self.del_node(n.left, k)   
        elif n.key < k: # 오른쪽자식으로 이동
            n.right = self.del_node(n.right, k) 
        else: # 삭제할 노드 발견
            if n.right == None: # case 0, 1
                return n.left   
            if n.left == None:  # case 1
                return n.right 
            target = n          # case 2, Line 66-69          
            n = self.minimum(target.right) # 중위 후속자를 찾아서 n이 참조하게 함
            n.right = self.del_min(target.right)
            n.left  = target.left
        return n
    
    def min(self): # 최솟값 가진 노드 찾기
        if self.root == None:
            return None
        return self.minimum(self.root)
    
    def minimum(self, n):
        if n.left == None:
            return n
        return self.minimum(n.left)
    
    def preorder(self, n): # 전위순회
        if n != None:
            print(str(n.key),' ', end='')
            if n.left:
                self.preorder(n.left)
            if n.right:
                self.preorder(n.right)
 
    def inorder(self, n): # 중위순회
        if n != None:
            if n.left:
                self.inorder(n.left)
            print(str(n.key),' ', end='')
            if n.right:
                self.inorder(n.right)

    def postorder(self, n): # 후위순회
        if n != None:
            if n.left:
                self.postorder(n.left)
            if n.right:
                self.postorder(n.right)
            print(str(n.key),' ', end='')
              
    def levelorder(self, root): # 레벨순회
        q = []
        q.append(root)
        while len(q) != 0:  
            t = q.pop(0) 
            print(str(t.key), ' ', end='')
            if t.left != None: 
                q.append(t.left)  
            if t.right != None: 
                q.append(t.right)

최솟값 찾기

• 최솟값은 루트노드로부터 왼쪽 자식을 따라 내려가며, None을 만났을 때 None의 부모가 가진 value

최솟값 삭제 연산

• 최솟값을 가진 노드를 삭제하는 것은 최솟값을 가진 노드 n을 찾아낸 뒤, n의 부모 p와 n의 오른쪽 자식 c를 연결
• 이 때 c 가 None이더라도 자식으로 연결
• delete_min()은 임의의 value를 가진 노드를 삭제하는 delete()에서 사용

삭제 연산

• 우선 삭제하고자 하는 노드를 찾은 후 이진탐색트리 조건을 만족하도록 삭제된 노드의 부모와 자식(들)을 연결해 주어야
• 삭제되는 노드가 자식이 없는 경우(case 0), 자식이 하나인 경우(case 1), 자식이 둘인 경우(case 2)로 나누어 delete 연산을 수행
  • Case 0: 삭제해야 할 노드 n의 부모가 n을 가리키던 레퍼런스를 None으로 만든다.
  • Case 1: n가 한쪽 자식인 c만 가지고 있다면, n의 부모와 n의 자식 c를 직접 연결
  • Case 2: n의 부모는 하나인데 n의 자식이 둘이므로 n의 자리에 중위순회하면서 n을 방문하기 직전 노드(Inorder Predecessor, 중위 선행자) 또는 직후에 방문되는 노드(Inorder Successor, 중위 후속자)로 대체

AVL 트리

• AVL 트리는 트리가 한쪽으로 치우쳐 자라나는 현상을 방지하여 트리 높이의 균형(Balance)을 유지하는 이진탐색트리
• 균형(Balanced) 이진트리를 만들면 N개의 노드를 가진 트리의 높이가 O(logN)이 되어 탐색, 삽입, 삭제 연산의 수행시간이 O(logN)으로 보장
• AVL트리는 삽입이나 삭제로 인해 균형이 깨지면 회전 연산을 통해 트리의 균형을 유지한다.
• AVL트리는 임의의 노드 x에 대해 x의 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이가 1을 넘지 않는 이진탐색트리이다.

class Node:          
    def __init__(self, key, value, height, left=None, right=None): # Node 생성자
        self.key    = key
        self.value  = value
        self.height = height
        self.left   = left 
        self.right  = right    

class AVL: 
    def __init__(self): # AVL트리 생성자
        self.root = None
    
    def height(self, n): # 높이 리턴 
        if n == None: 
            return 0
        return n.height
    
    def put(self, key, value): # 삽입 연산
        self.root = self.put_item(self.root, key, value)
        
    def put_item(self, n, key, value): 
        if n == None:
            return Node(key, value, 1)
        if n.key > key:         
            n.left = self.put_item(n.left,  key, value)
        elif n.key < key:
            n.right = self.put_item(n.right, key, value)
        else: 
            n.value = value  # key가 이미 트리에 있으므로 value 갱신
            return n       
        n.height = max(self.height(n.left), self.height(n.right)) + 1
        return self.balance(n) # 노드 n의 균형 점검 및 불균형을 바로 잡음
    

    def balance(self, n): # 불균형 처리
        if self.bf(n) > 1:  #노드 n의 왼쪽 서브트리가 높아서 불균형 발생
            if self.bf(n.left) < 0: # 노드 n의 왼쪽 자식의 오른쪽서브트리가 높은 경우
                n.left = self.rotate_left(n.left) # LR-회전           
            n = self.rotate_right(n) # LL-회전
        
        elif self.bf(n) < -1: #노드 n의 오른쪽 서브트리가 높아서 불균형 발생
            if self.bf(n.right) > 0: # 노드 n의 오른쪽자식의 왼쪽 서브트리가 높은 경우
                n.right = self.rotate_right(n.right) # RL-회전            
            n = self.rotate_left(n) # RR-회전      
        return n
    
    def bf(self, n): # bf 계산
        return self.height(n.left) - self.height(n.right)       
    
    def rotate_right(self, n): # 우로 회전
        x = n.left
        n.left = x.right
        x.right = n
        n.height = max(self.height(n.left), self.height(n.right)) + 1 # 높이 갱신
        x.height = max(self.height(x.left), self.height(x.right)) + 1 # 높이 갱신
        return x  # 회전 후 x가 n의 이전 자리로 이동되었으므로 
    
    def rotate_left(self, n): # 좌로 회전
        x = n.right
        n.right = x.left
        x.left = n
        n.height = max(self.height(n.left), self.height(n.right)) + 1 # 높이 갱신
        x.height = max(self.height(x.left), self.height(x.right)) + 1 # 높이 갱신
        return x  # 회전 후 x가 n의 이전 자리로 이동되었으므로 
      
    def delete(self, key): # 삭제 연산
        self.root = self.delete_node(self.root, key)
         
    def delete_node(self, n, key):
        if n == None:
            return None
        if n.key > key: # 왼쪽 자식으로 이동
            n.left = self.delete_node(n.left, key)   
        elif n.key < key: # 오른쪽 자식으로 이동
            n.right = self.delete_node(n.right, key) 
        else:  # 삭제할 노드 발견
            if n.right == None: # case 0, 1
                return n.left   
            if n.left == None:  # case 1
                return n.right 
            target = n          # case 2
            n = self.minimum(target.right) # 중위 후속자를 찾아서 n이 참조하게 함
            n.right = self.del_min(target.right)
            n.left  = target.left              
        n.height = max(self.height(n.left), self.height(n.right)) + 1
        return self.balance(n)
    
    def delete_min(self):  # 최솟값 삭제
        if self.root == None:
            print('트리가 비어 있음')
        self.root = self.del_min(self.root)
          
    def del_min(self, n): 
        if n.left == None:
            return n.right
        n.left = self.del_min(n.left)
        n.height = max(self.height(n.left), self.height(n.right)) + 1
        return self.balance(n)
  
    def min(self): # 최솟값 찾기
        if self.root == None:
            return None
        return self.minimum(self.root)
    
    def minimum(self, n):
        if n.left == None:
            return n
        return self.minimum(n.left)
    
    def preorder(self, n): # 전위순회
        print(str(n.key),' ', end='')
        if n.left:
            self.preorder(n.left)
        if n.right:
            self.preorder(n.right)
 
    def inorder(self, n): # 중위순회
        if n.left:
            self.inorder(n.left)
        print(str(n.key), ' ', end='')
        if n.right:
            self.inorder(n.right)

#from avl import AVL
#if __name__ == '__main__':
t = AVL()
t.put(75, 'apple') 
t.put(80, 'grape')
t.put(85, 'lime')
t.put(20, 'mango') 
t.put(10, 'strawberry')
t.put(50, 'banana')
t.put(30, 'cherry')
t.put(40, 'watermelon')
t.put(70, 'melon') 
t.put(90, 'plum')
print('전위순회:\t', end='')
t.preorder(t.root)
print('\n중위순회:\t', end='')
t.inorder(t.root)
print('\n75와 85 삭제 후:')    
t.delete(75)
t.delete(85)
print('전위순회:\t', end='')
t.preorder(t.root)
print('\n중위순회:\t', end='')
t.inorder(t.root)

전위순회:	75  40  20  10  30  50  70  85  80  90  
중위순회:	10  20  30  40  50  70  75  80  85  90  
75와 85 삭제 후:
전위순회:	40  20  10  30  80  50  70  90  
중위순회:	10  20  30  40  50  70  80  90