[자료구조와 알고리즘] #7. 트리

 

 

---

#7. 트리

트리

노드와 엣지를 이용하여 데이터의 배치 형태를 추상화한 자료 구조 

 

용어 정리 

• 노드 (nodes)
• 간선 (edges)
• 루트 노드 (root node), 리프 노드 (leaf nodes), 내부 노드 (internal nodes)
• 부모 (parent) 노드와 자식 (child) 노드 : 루트에 가까울수록 부모, 리프에 가까울수록 자식 
• 노드의 수준 (level) : 루트노드는 레벨0 , 하나씩 내려갈수록 레벨 +1 
• 노드의 차수 (degree) : 서브 트리의 수 (리프 노드로 향하는 간선의 수로 계산) 
• 트리의 높이 (height)  또는, 깊이 (depth) : 최대 레벨 +1 
• 부분 트리 (서브트리; subtrees) : 다른 노드를 루트로 두는 서브트리를 만들 수 있음 
• 이진 트리 (binary trees) : 모든 노드의 차수가 2 이하인 트리 
  • 재귀 정의 : 빈 트리이거나(터미널 조건) 루트노드 + 왼쪽 서브트리 + 오른쪽 트리 (왼쪽,오른쪽 서브트리 또한 이진트리) 
• 포화 이진 트리 (full binary trees) : 모든 레벨에서 노드들이 모두 채워져있는 이진 트리. 높이가 k라면 노드의 개수는 2**k-1 
• 완전 이진 트리 (complete binary trees) : 높이가 k인 완전이진트리는 레벨 k-2까지는 모든 노드가 2개의 자식을 가진 포화이진트리이나 레벨 k-1에서는 왼쪽에서부터 노드가 순차적으로 채워져있는 이진트리 

 

이진 트리

연산의 정의

• size() : 총 노드 수를 구함 
• depth() : 현재 트리의 깊이를 구함 
• traversal() : 순회 

이진 트리 구현 

• 노드
  • 데이터
  • left child, right child

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

• 트리
  • root 

class BinaryTree:
	def __init__(self,r):
    	self.root = r

• size()
  • 전체 이진 트리의 사이즈 = left subtree의 사이즈 + right subtree의 사이즈 + 1 (자기자식) → 재귀적

class Node : 

	def size(self):
    		l = self.left.size() if self.left else 0 
        	r = self.rigth.size() if self.right else 0
        	return l + r + 1
            
class BinaryTree:
	
    def size(self):
    	if self.root :
        	return self.root.size()
        else :
        	return 0

 

• depth()
  • Left subtree의 depth, Right subtree의 depth 중 맥스값 + 1 

class Node:

	def depth(self):
    	l = self.left.depth() if self.left else 0 
        r = self.right.depth() if self.right else 0 
        return max(l,r)+1 
    
class BinaryTree:
	def depth(self):
    	if self.root :
        	return self.root.depth()
        else :
        	return 0

 

이진 트리의 순회 

• 깊이 우선 순회
  • 중위 순회
    • left subtree 순회
    • 자기자신 확인
    • right subtree 순회 

class Node :
	def inorder(self):
    	traversal = []
        if self.left : 
        	traversal += self.left.inorder() 
        traversal.append(self.data)
        if self.rigth :
        	traversal += self.right.inorder()
            
        return traversal 
        
        
class BinaryTree :
	def inorder(self):
    	if self.root:
        	return self.root.inorder()
        else
        	return 0

• 전위 순회
  • 자기자신 확인
  • left subtree 순회
  • right subtree 순회

class Node:

    def preorder(self):
        traversal = []
        traversal.append(self.data)
        if self.left:
            traversal += self.left.preorder()
        if self.right:
            traversal += self.right.preorder()
        return traversal


class BinaryTree:

    def preorder(self):
        if self.root:
            return self.root.preorder()
        else:
            return []

• 후위 순회 
  
  • left subtree 순회
  • right subtree 순회
  • 자기자신 확인

class Node:

    def postorder(self):
        traversal = []
        
        if self.left:
            traversal += self.left.postorder()
            
        if self.right:
            traversal += self.right.postorder()
            
        traversal.append(self.data)
        
        return traversal


class BinaryTree:

     def postorder(self):
        if self.root:
            return self.root.postorder()
        else:
            return []

• 넓이 우선 순회
  • 원칙
    • 수준(레벨)이 낮은 노드를 우선으로 방문 (즉 루트부터) 
    • 같은 수준의 노드들 사이에서는 부모 노드의 방문 순서에 따라 방문 
    • 왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문 
    • 한 노드를 방문했을 때, 나중에 방문할 자식 노드들을 순서대로 기록해둬야 함 
  • 알고리즘 설계
    • 빈 큐를 사용 
    • 루트 노드를 먼저 넣고 출력 
    • 왼쪽부터 자식을 큐에 넣음 
    • 왼쪽 자식을 먼저 빼고 왼쪽 자식의 자식들을 큐에 넣음
    • 오른쪽 자식을 큐에서 뺌 
    • 오른쪽 자식의 자식을 큐에 넣음 
    • ... 이를 한 노드에 대한 처리 (자기자신이 빠진 다음 딸린 자식을 넣음. 이가 완료되면 그 다음 노드를 뺌) 반복 

class BinaryTree:

	def btf(self):
    #1. traversal , q 로 빈 리스트와 빈 큐 마련
    
    #2. 빈 트리가 아닌 경우 root node를 enqueue 
    
    #3. q가 비어 있지 않는 동안 
    #3.1 node <- q에서 원소를 추출 (dequeue)
    #3.2 node를 방문 (리스트에 넣기)
    #3.3 node의 왼쪽 오른쪽 자식이 있다면 이들을 q에 추가 
    #4. q가 비면 모든 노드 방문 완료
    
    
class BinaryTree:

    def __init__(self, r):
        self.root = r


    def bft(self):
        q = ArrayQueue()
        traversal = []
        
        if self.root != None : 
            q.enqueue(self.root)
        
        while not q.isEmpty() :
            node = q.dequeue()
            traversal.append(node.data)
            
            if node.left :
                q.enqueue(node.left)
            if node.right :
                q.enqueue(node.right)
        
        return traversal

※ 유의점 

queue에 넣는 것은 해당 노드 그 자체이지만, 리스트에 넣는 것은 데이터를 넣어야 함 

 

 

이진탐색 트리 

• 정의 : 모든 노드에 대해서 (1) 왼쪽 서브 트리에 있는 데이터는 모두 현재 노드의 값보다 작고, (2) 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값도다 큰 성질을 만족하는 이진 트리  (단 중복되는 데이터 원소는 없는 것으로 가정) 
• 장점 : 배열을 이용한 이진탐색보다 데이터 원소의 추가, 삭제가 용이함 
• 단점 : 공간 소요가 큼 O(logn) 

 

 

 

 

추상적 자료 구조 

• 데이터 표현 : 각 노드는 key, value 쌍으로 구성 
• key를 이용해서 검색 가능하며 보다 복잡한 데이터 레코드로 확장 가능 

 

연산 정의 

• insert(key,data)
• remove(key) :어려움 
• lookup(key) : 키를 가지고 특정 원소를 검색 
• inorder() : 키의 순서대로 데이터 원소를 나열 
• min(), max() : 최소 최대 키를 가지는 원소를 각각 탐색 

class Node:
	def__init__(self,key,data):
    	self.key = key
        self.data = data
        self.left = None
        self.right = None
        
    def inorder(self):
    	traversal = []
        if self.left :
        	traversal += self.left.inorder()
        traversal.append(self)                 #노드 데이터가 아니라 노드자체의 리스트를 만들게 함 
        if self.right:
        	traversal += self.right.inorder()
        return traversal 
        

    def min(self):                      #노드 기준으로 왼쪽에 작은 값이 있으므로 왼쪽에서 찾기 
    	if self.left:
        	return self.left.min()        
        else :
        	return self      
            
    def lookup(self,key,parent=None):
    	if key<self.key:
        	if self.left :
            	return self.left.lookup(key,self)    #self.left의 부모는 self이기에 
            else : return None,None 
            
        elif key>self.key:
        	if self.right:
            	return self.right.lookup(key,self)
            else : return None,None
        else : 
        	return self,parent 
     
    def insert(self, key, data):
        if key < self.key:                  #주어진 Key값이 selfkey보다 작으면
            if self.left :                  #왼쪽이 존재할 경우
                self.left.insert(key,data)  #왼쪽에 삽입 
            else :
                self.left = Node(key,data)  #왼쪽이 존재하지 않으면 왼쪽 노드에 새노드만들기 
                
        elif key > self.key:
            if self.right:
                self.right.insert(key,data)
            else:
                self.right = Node(key,data)
                
        else : 
            raise KeyError('중복된 값이 있습니다')
 
 
class BinSearchTree:
	def__init__(self):
    	self.root = None          #이진탐색에서는 none으로 설정 
        
    def inorder(self):
    	if self.root:
        	return self.root.inorder()
        else : 
        	return None
            
    def min(self):
    	if self.root:
        	return self.root.min()       #루트에서 부터 시작해서 미니멈을 찾아라 
        else :
        	return None 
            
    def lookup(self.key):
    	if self.root:
        	return self.root.lookup(key)
        else : return None, None 
        
    def insert(self,key,value):
    	if self.root:
        	self.root.insert(key,data)
        else:                            #루트가 없을 경우 새 노드를 만든다 
        	self.root = Node(key,data)

 

• remove() 연산 설계 
  • 과정
    • 키를 이용해서 노드를 찾는다. 해당 키 노드가 없으면 삭제 안함. 찾은 노드의 부모 노드도 알고 있어야 함 
    • 찾은 노드를 제거한 뒤 이진 탐색 트리 성질을 만족하도록 트리의 구조를 정리해야 함 
  • 설계
    • 입력 : key, 출력 : 삭제한 경우 True,  해당 키의 노드가 없는 경우 False 
    • 삭제된 노드가
      • 말단(리프)노드인 경우 , 그냥 노드를 없애고 부모 노드의 링크를 조정(왼오 판단)
        • 삭제되는 노드가 루트인 경우 self.root = None
      • 자식을 하나 가지고 있는 경우, 삭제되는 노드 자리에 그 자식을 대신 배치(왼오 판단), 부모 노드 링크 조정(왼오판단)
        • 삭제되는 노드가 루트인 경우 대신 들어오는 자식이 새로 루트가 됨 
      • 자식을 둘 가지고 있는 경우, 삭제되는 노드보다 바로 다음 큰 키를 가진 노드를 찾아(오른쪽 →왼쪽 서브트리 탐색. 석세서라 지칭)  그 노드를 삭제되는 노드 자리에 대신 배치한 뒤, 기존 석세서 노드 삭제. 기존 석세서 노드의 자식을 기존 석세서 노드의 부모 노드에 연결 
        • 석세서가 오른쪽에 있는 경우엔 if문으로 예외처리해서 진행해야 함  

class BinSearchTree:
    def remove(self, key):
        node, parent = self.lookup(key)
        if node:
            nChildren = node.countChildren()
            # The simplest case of no children
            if nChildren == 0:
                # 만약 parent 가 있으면
                # node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
                # parent.left 또는 parent.right 를 None 으로 하여
                # leaf node 였던 자식을 트리에서 끊어내어 없앱니다.
                if parent:
                    if node.key < parent.key :      #key 크기로 왼오 구분 가능 
                        parent.left = None
                    else :
                        parent.right = None
                # 만약 parent 가 없으면 (node 는 root 인 경우)
                # self.root 를 None 으로 하여 빈 트리로 만듭니다.
                else:
                    self.root = None 
            # When the node has only one child
            elif nChildren == 1:
                # 하나 있는 자식이 왼쪽인지 오른쪽인지를 판단하여
                # 그 자식을 어떤 변수가 가리키도록 합니다.
                if node.left:
                    c = node.left
                else:
                    c = node.right 
                # 만약 parent 가 있으면
                # node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
                # 위에서 가리킨 자식을 대신 node 의 자리에 넣습니다.
                if parent:
                    if node.key < parent.key:
                        parent.left = c  
                    else:
                        parent.right = c 
                # 만약 parent 가 없으면 (node 는 root 인 경우)
                # self.root 에 위에서 가리킨 자식을 대신 넣습니다.
                else:
                    self.root = c
            # When the node has both left and right children
            else:
                parent = node
                successor = node.right
                # parent 는 node 를 가리키고 있고,
                # successor 는 node 의 오른쪽 자식을 가리키고 있으므로
                # successor 로부터 왼쪽 자식의 링크를 반복하여 따라감으로써
                # 순환문이 종료할 때 successor 는 바로 다음 키를 가진 노드를,
                # 그리고 parent 는 그 노드의 부모 노드를 가리키도록 찾아냅니다.
                while successor.left:              
                    #successor = successor.left 
                    #parent = successor.parent   .parent는 없음 
                    parent = successor 
                    successor = parent.left
                # 삭제하려는 노드인 node 에 successor 의 key 와 data 를 대입합니다.
                node.key = successor.key
                node.data = successor.data
                # 이제, successor 가 parent 의 왼쪽 자식인지 오른쪽 자식인지를 판단하여
                # 그에 따라 parent.left 또는 parent.right 를
                # successor 가 가지고 있던 (없을 수도 있지만) 자식을 가리키도록 합니다.
                #노드는 왼쪽 자식을 가질 수 없습니다. 왼쪽 자식이 있었다면 위에서 설명한 과정에서 그 링크를 따라가서 해당 자식 노드를 successor 로 택했을 것이기 때문입니다. 한편, 오른쪽 자식은 가질 수 있습니다. 이 오른쪽 자식은 (존재한다면) successor 노드가 삭제된 노드의 위치를 대신하게 된 이후에 successor 의 자리를 차지해야 합니다
                if parent.left == successor :
                    parent.left = successor.right 

                elif parent.right == successor :
                    parent.right = successor.right 

            return True

        else:
            return False
            
            
class Node:

	def countChildren(self):                      #자식수 확인하는 메서드 구현 
    	count = 0
        if self.left : 
        	count+=1
        if self.right:
        	count +=1
        else : None