[자료구조] 트리

트리

• Node와 Branch를 이용해서 사이클을 이루지 않도록 구성한 데이터 구조
• 장점 : 탐색 속도를 개선할 수 있음
  
• 시간복잡도(탐색 시)
  • h : depth -> O(h) // depth만큼 탐색
  • n개의 노드개수를 가진다면, h = log(n)과 비슷해짐
    따라서 시간복잡도는 O(logn) //한번 실행시 50%의 노드를 지운다는 말과 같음
  • 하지만 만일, 한쪽으로만 균형잡힌 이진트리가 된다면, 모든 노드를 다 순회해야 하기 때문에 시간복잡도는 O(n)이 됨.

이진트리

• 노드의 최대 브랜치가 2개인 트리

이진탐색트리(Binary Search Tree)

• 이진트리 중 부모노드보다 값이 큰 노드는 오른쪽에, 부모노드보다 값이 작은 노드는 왼쪽에
  

파이썬 객체지향 프로그래밍으로 구현하기

#노드 구현
class Node:
    def __init__(self,value):
        self.value = value
        self.right = None
        self.left = None
#이진 탐색 트리에 데이터 넣기
class NodeMgmt:
    #root 노드
    def __init__(self,head):
        self.head=head
    def insert(self,value):
        self.current_node = 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.curret_node.right
                else: 
                    self.current_node.right=Node(value)
                    break
def search(self,value):
    self.currnet_node = head
    while self.currnet_node:
        #값을 찾으면 True 리턴
        if self.currnet_node.value == value:
            return True
        #왼쪽    
        elif value<self.currnet_node.value:  
            self.currnet_node=self.curret_note.left
        #오른쪽
        else:
            self.currnet_node=self.curret_note.right
    #노드를 모두 순회했는데도 value를 값으로 가진 노드를 찾지 못하면
    return False

이진트리 삭제

• leaf node 삭제
  
  1. 삭제할 node의 부모 node가 삭제할 node를 가리키지 않도록 한다.
• child node가 하나인 node 삭제
  
  1. 삭제할 node의 부모 node가 삭제할 node의 child node를 가리키도록 한다.
• child node가 두개인 node 삭제
  1. 삭제할 node의 오른쪽 자식 중, 가장 작은 값(가장 왼쪽)을 삭제할 node의 parent node가 가르키게 한다.
     • 만약 가장 작은값 노드가 오른쪽 자식을 가지고 있다면, 그 오른쪽 노드를 가장 작은값 노드의 부모의 왼쪽 브랜치가 되도록 한다.
       
  2. 삭제할 node의 왼쪽 자식 중, 가장 큰 값(가장 오른쪽)을 삭제할 node의 parent node가 가르키게 한다.

#delete
def delete(self,value):
    searched=False
    self.current_node=self.head
    self.parent=self.head
    #일단 value를 값으로 가진 노드가 있는지 찾는다
    while self.current_node:
        if self.currnet_node.value==value:
            searched=True
            break
        elif value<self.currnet_node.value:
           self.cparent=self.current_node
           self.currnet_node=self.current_node.left
        else:
           self.parent=self.current_node
           self.currnet_node=self.current_node.right
    #트리를 다 돌고도 value를 값으로 가진 노드가 없다면
    #reutrn False
    if searched==False:        
        return Fasle        
 #이후부터 케이스를 분리해서 코드 작성
 #self.current_node 가 삭제할 Node, self.parent는 삭제할 Node의 Parent Node인 상태
#case1 - 자식 노드가 없는 노드를 삭제
    if self.currnet_node.left==None and self.currnet_node.right==None:
    #삭제할 노드가 parent노드의 왼쪽에 있음
        if value<self.parnet.value:
            self.parent.left==None
    #삭제할 노드가 parent노드의 오른쪽에 있음    
        else:
            self.parent.right==None
    #해당노드 삭제        
        del self.currnet_node    
#case2 - 자식 노드가 하나 있음
    #삭제할 노드의 왼쪽에 자식이 있음 (1,3)
    if self.currnet_node.right==None and self.currnet_node.left!=None:
        #삭제할 노드가 부모 노드의 왼쪽에 있음 (1)
        if value<self.parent.value:
            self.parnet.left=self.current_node.left
       #삭제할 노드가 부모 노드의 오른쪽에 있음
       else: (3) 
           self.parent.right=self.current_node.left
    #삭제할 노드의 오른쪽에 자식이 있음 (2,4)      
    elif self.currnet_node.right!=None and self.currnet_node.left-=None:
        #삭제할 노드가 부모의 왼쪽에 있음(2)
        if value<self.parnet.value:
            self.parent.left=self.current_node.right
        #삭제할 노드가 부모의 오른쪽에 있음(4)
        else:
            self.parent.right=self.current_node.right         

# case3 - 자식이 2개 일 때 
        #삭제할 노드가 부모 노드의 왼쪽에 있음
        if value < self.parent.value:
            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
            #self.change_node가 가장 왼쪽 노드가 된 상태
            #가장 왼쪽 노드의 오른쪽 자식이 있음
            if self.change_node.right != None:
                #가장 왼쪽 노드의 부모의 왼쪽 브런치에 그 오른쪽 자식을 연결
                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