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

    2021. 7. 29.

    by. ziasu

    반응형

    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)

     

     

    반응형

    댓글