자료구조) BST(1/3) - BST란?

일단 트리는 노드를 이용해서 사이클 없이 데이터를 적재하는 구조입니다. 

이때 자식수가 2개인 트리를 이진 트리(Binary Tree)

자식수가 2개이면서 특별한 규칙에 의해 바로 정렬까지 되는 트리를 Binary Search Tree(BST) 라고 합니다. 

특별한 규칙이란, 현재 노드를 기준으로 현재 노드보다 작은 값은 왼쪽에, 더 큰 값은 오른쪽에 배치되는 것입니다. 

그래서 왼쪽 서브트리는 기준 노드보다 다 작고, 오른쪽 서브트리는 기준 노드 보다 더 큽니다. 

BST를 구현할때는 링크드 리스트와 비슷하게 노드로 구현을 합니다. 

다른 것은 다 괜찮은데, BST에서 삭제를 하는 경우가 약간 복잡합니다. 경우의 수가 많기 때문인데요, 

아래의 경우들로 나뉘게 됩니다. 

1. 삭제할 노드의 자식 노드가 없는 경우
   1. 삭제할 노드가 부모 노드의 오른쪽에 있는 경우 : 부모 노드의 오른쪽을 None으로
   2. 삭제할 노드가 부모 노드의 왼쪽에 있는 경우 : 부모 노드의 왼쪽을 None으로
2. 삭제할 노드의 자식노드가 하나 있는 경우
   1. 삭제할 노드가 부모의 왼쪽에 위치한 경우 : 부모노드이 왼쪽을 삭제할 노드의 자식노드로 해줌
   2. 삭제할 노드가 부모의 오른쪽에 위치한 경우 : 부모노드의 오른쪽을 삭제할 노드의 자식노드로 해줌
3. 삭제할 노드의 자식노드가 있는 경우,
   1. 삭제할 노드가 부모의 왼쪽에 위치할 경우 : 가장 중앙 값이 맨 위에 오게 해야 함 → 노드의 오른쪽 자식 중 가장 작은 값을 선택 or 노드의 왼쪽 자식 중 가장 큰 값을 선택해서 부모의 왼쪽 자식으로 넣어줌 & 삭제할 노드의 왼쪽과 오른쪽 자식 노드를 대체할 노드의 왼쪽과 오른쪽 자식 노드로 넣어줘야 함
   2. 삭제할 노드가 부모의 오른쪽에 위치할 경우 : 가장 중앙 값이 맨 위에 오게 해야 함 → 노드의 오른쪽 자식 중 가장 작은 값을 선택 or 노드의 왼쪽 자식 중 가장 큰 값을 선택해서 부모의 오른쪽 자식으로 넣어줌 & 삭제할 노드의 왼쪽과 오른쪽 자식 노드를 대체할 노드의 왼쪽과 오른쪽 자식 노드로 넣어줘야 함

그래서 구현은 다음과 같습니다. 

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

        
class NodeMgmt:
    def __init__(self, head):
        self.head = head
    
    def insert(self, value):
        self.current_node = self.head
        while True:
            if value < self.current_node.value:
                if self.current_node.left != None:
                    self.current_node = self.current_node.left
                else:
                    self.current_node.left = Node(value)
                    break
            else:
                if self.current_node.right != None:
                    self.current_node = self.current_node.right
                else:
                    self.current_node.right = Node(value)
                    break
    
    def search(self, value):
        self.current_node = self.head
        while self.current_node:
            if self.current_node.value == value:
                return True
            elif value < self.current_node.value:
                self.current_node = self.current_node.left
            else:
                self.current_node = self.current_node.right
        return False        
    
    def delete(self, value):
        # 삭제할 노드 탐색
        searched = False
        self.current_node = self.head
        self.parent = self.head
        while self.current_node:
            if self.current_node.value == value:
                searched = True
                break
            elif value < self.current_node.value:
                self.parent = self.current_node
                self.current_node = self.current_node.left
            else:
                self.parent = self.current_node
                self.current_node = self.current_node.right

        if searched == False:
            return False    

        # case1 : 삭제할 노드의 자식이 없을 때 
        if  self.current_node.left == None and self.current_node.right == None:
            if value < self.parent.value:
                self.parent.left = None
            else:
                self.parent.right = None
        
        # case2 : 삭제할 노드의 자식이 한쪽만 있을 때 
        elif self.current_node.left != None and self.current_node.right == None:
            if value < self.parent.value:
                self.parent.left = self.current_node.left
            else:
                self.parent.right = self.current_node.left
        elif self.current_node.left == None and self.current_node.right != None:
            if value < self.parent.value:
                self.parent.left = self.current_node.right
            else:
                self.parent.right = self.current_node.right        
        
        # case 3 : 삭제할 노드의 자식이 양쪽다 있을때 
        elif self.current_node.left != None and self.current_node.right != None:
            # case3-1
            if value < self.parent.value:
                self.change_node = self.current_node.right
                self.change_node_parent = self.current_node.right
                if self.change_node.left == None:  # 삭제한 노드의 오른쪽 자식노드의 왼쪽 자식이 없다면
                     self.parent.left = self.change_node # 그냥 바로 붙이기
                     self.change_node.left = self.current_node.left
                else : 
                    while self.change_node.left != None: # 삭제할 노드의 오른쪽 자식의 가장 작은 것을 선택하는 과정
                        self.change_node_parent = self.change_node
                        self.change_node = self.change_node.left
                    self.change_node_parent.left = None
                    self.parent.left = self.change_node
                    self.change_node.right = self.current_node.right
                    self.change_node.left = self.current_node.left
            # case 3-2
            else:
                self.change_node = self.current_node.right
                self.change_node_parent = self.current_node.right
                if self.change_node.left == None:  # 삭제한 노드의 오른쪽 자식노드의 왼쪽 자식이 없다면
                     self.parent.right = self.change_node # 그냥 바로 붙이기
                     self.change_node.left = self.current_node.left
                else : 
                    while self.change_node.left != None:
                        self.change_node_parent = self.change_node
                        self.change_node = self.change_node.left
                    self.change_node_parent.left = None
                    self.parent.right = self.change_node
                    self.change_node.right = self.current_node.right
                    self.change_node.left = self.current_node.left

        return True

이런 BST는 노드가 균등하게 위치해 있을때 탐색, 삽입, 삭제에 O(logN)일 정도로 굉장히 빠릅니다. 

하지만 노드가 균등하게 위치하지 않을경우에는 linked list와 다를바가 없어 탐색과 삭제에서 O(n)이 걸리죠

그래서 노드를 균등하게 맞추기 위한 알고리즘 결로 자가 균형 BST(Self-Balancing BST)가 있습니다. 

자가균형 BST란 알고리즘을 통해 노드가 균형있게 배치되도록 해서 높이를 낮추는 방법입니다.

자가 균형 BST에는 크게 AVL 트리와 RED-BLACK 트리가 있습니다. 

다음번에는 자가 균형 BST를 알아볼게요