[자료구조] 트리(Tree) (Python)

1. 기본 구조와 용어

• 트리(Tree): Node와 Branch를 이용하여, 사이클을 이루지 않도록 구성한 데이터 구조

 

• 노드(Node): 트리에서 데이터를 저장하는 기본 요소로, Branch 정보 또한 포함
• 간선(Edge): 노드와 노드를 연결하는 연결선
• Root Node: 트리 맨 위의 노드
• Leaf Node: Child Node가 하나도 없는 노드
• Depth: 트리에서 Node가 가질 수 있는 최대 Level

2. 이진 탐색 트리(Binary Search Tree)

• 이진 트리에 추가적인 조건이 있는 트리 (왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값)

3. Python Linked list로 간단한 Binary Seach Tree 구현

• Python class를 통해 Linked list를 구현
• NodeMgmt class의 (insert, search, delete) 함수를 통해 기능들을 구현

class Node:
    def __init__(self,value):#이진트리이므로 left와 right만 있어도 됨
        self.value = value
        self.left = None
        self.right = None

class NodeMgmt:
    def __init__(self,head): #root노드가 head
        self.head=head
        
    #원하는 값을 트리안에 넣어주는 기능
    def insert(self,value):
        self.current_node = self.head #현재 노드는 head로 잡고
        while True: #순회
            #insert하려는  current_node.value보다 작을 때
            if value < self.current_node.value: 
                if self.current_node.left != None: #left가 있으면 current를 current.left로 이동
                    self.current_node = self.current_node.left
                else: #left가 없으면 left부분에 value값을 넣어줌
                    self.current_node.left = Node(value)
                    break
                    
            #insert하려는 값이 current_node.value보다 클 때
            else:
                if self.current_node.right != None: #아래 아무것도 없다면 current.right로 이동
                    self.current_node = self.current_node.right
                else: #right가 없으면 right부분에 value값을 넣어줌
                    self.current_node.right = Node(value)
                    break
    
    #어떤 값이 존재하는지 판단하는 기능
    def search(self, value):
        self.current_node = self.head
        
        while self.current_node: #current_node가 none이 되면 종료
            if self.current_node.value == value: #현재 노드가 내가 원하는 값인지
                return True
                break
            elif value < self.current_node.value:
                self.current_node = self.current_node.left
            else:
                self.current_node = self.current_node.right
        return False    
    
    # 원하는 value의 노드를 삭제하는 기능
    def delete(self, value):
        searched = False
        self.current_node = self.head
        self.parent = self.head
        
    	# 삭제할 Node 탐색
        while self.current_node:
            if self.current_node.value == value:
                searched = True
                break #찾으면 break
            
            elif value < 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
    
    #탐색이 끝나면
    #Case를 분리하여 삭제해나가는 process
    
#1 leaf node 삭제
        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
            del self.current_node
           
    
    
#2 child의 left만 가지고 있는 노드 삭제
        if self.current_node.left != None and self.current_node.right==None:
        #current가 parent 왼쪽인지 오른쪽인지
            if vale<self.parent.value: #왼쪽일 때
                self.parent.left = self.current_node.left
            else: #오른쪽일 때
                self.parent.right = self.current_node.left
    
    #child의 right만 가지고 있는 노드를 삭제할 때 똑같은 방식으로 처리
        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
            
            
#3 Child Node가 두개인 node 삭제
    #삭제할 Node의 오른쪽 자식 중 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
        
    #3-1 삭제할 node가 parent node 왼쪽에 위치
    #3-1-1 삭제할 node의 오른쪽 child가 child 없을 때
    #3-1-2 삭제할 node의 오른쪽 child가 child 있을 때
    
    #3-2 삭제할 node가 parent node 오른쪽에 위치
    #3-2-1 삭제할 node의 오른쪽 child가 child 없을 때
    #3-2-2 삭제할 node의 오른쪽 child가 child 있을 때
    
        if self.current_node.left != None and self.current_node.right != None:
            if value<self.parent.value: #3-1
                self.change_node = self.current_node.right
                self.change_node_parent = self.current_node.right
                while self.change_node.left != None:#left 타고 최대한 간 후
                    self.change_node.parent = self.change_node
                    self.change_node = self.change_node.left
                
                if self.change_node.right != None: #3-1-2
                    self.change_node_parent.left = self.change_node.right
                else:
                    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.change_node.left
            
            else:
                self.change_node = self.current_node.right
                self.change_node_parent = self.current_node.right
                while self.change_node.left != None:
                    self.change_node_parent = self.change_node
                    self.change_node = self.change_node.left
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent.right = self.change_node
                self.change_node.left = self.current_node.left
                self.change_node.right = self.current_node.right

[insert 함수]

• 맨 위의 노드를 current_node로 잡기
• depth 하나씩 늘어날 때마다 넣고자 하는 value를 current_node.value와 비교하여 어떤 방향으로 내려갈지 결정
• 쭉쭉 내려가다가 (current_node.value보다 큰데 current_node.right가 비어있을 때), (current_node.value보다 작은데 current_node.left가 비어있을 때)의 경우에는 그 위치에 원하는 value가 담긴 노드를 만들어준다.

[search 함수]

• 그냥 간단하게 트리를 한번 쭉 훑으면서 찾고자 하는 value가 있는지 확인하는 함수

[delete 함수]

• 상당히 복잡하다;; 머릿속으로 각각의 상황을 잘 분할하는 것이 중요
• 먼저 삭제하고자 하는 value를 가지고 있는 노드를 탐색하여 current_node로 설정
• 트리 구조에서 하나의 노드를 삭제하면 이를 반영하여 노드간 연결을 수정해주어야 함
• 그렇기에 삭제하려는 노드가 어떤 연결관계를 가졌는지에 따라 여러 경우를 따져서 분할해준 뒤 하나하나씩 정복해나가는 방식을 사용

##분할해주기##

삭제할 노드의...

 

1) child가 하나도 없을 때(leaf node일 때)

 

2) child가 하나 있을 때

2-1) child의 left만 가지고 있을 때

2-2) child의 right만 가지고 있을 때

 

3) child가 두 개 있을 때

##삭제할 Node의 오른쪽 자식 중 작은 값을 삭제할 Node의 Parent Node가 가리키도록  하는 방식 이용

 

3-1) 삭제할 node가 parent node 왼쪽에 위치
3-1-1) 삭제할 node의 오른쪽 child가 child 없을 때
3-1-2) 삭제할 node의 오른쪽 child가 child 있을 때
    
3-2) 삭제할 node가 parent node 오른쪽에 위치
3-2-1) 삭제할 node의 오른쪽 child가 child 없을 때

3-2-2) 삭제할 node의 오른쪽 child가 child 있을 때

 

 

4. BST 시간복잡도와 단점

• Tree의 Depth가 1만큼 증가하면 탐색해야할 데이터가 반으로 줄어든다. -> 평균 시간복잡도: O(logn)
• But!! 가장 최악의 경우에는 링크드 리스트와 동일한 성능 -> 최악 시간복잡도: O(n)