[자료구조] 이진 트리 & 힙

트리  

트리

정점(node)과 간선(edge)을 이용하여 데이터의 배치 형태를 추상화한 자료 구조로, 순환하는 길이 없는 그래프라고 말할 수 있다.

• 루트 노드 (root node) : 트리의 최상단 노드
• 리프 노드 (leaf nodes) : 트리의 최하단 노드
• 내부 노드 (internal nodes) : 루트와 리프 사이에 위치한 노드
• 부모 (parent) 노드와 자식 (child) 노드 : 정점의 바로 위 노드가 부모 노드, 바로 아래 노드가 자식 노드 (부모의 부모는 조상노드, 자식의 자식은 후손 노드)
• 노드의 수준 (level) :  root로 부터 각각의 노드까지 도달하기 위해 거쳐야하는 간선의 수 (root = level 0)
• 노드의 차수 (degree) : 자식 노드의 수
• 트리의 높이 (height) 또는 깊이 (depth) : 노드의 최대 level + 1
• 부분 트리 (서브트리; subtrees) : 트리의 어느 한 노드를 root로 설정하여 만든 트리
• 이진 트리 (binary trees) : 모든 노드의 차수가 2 이하인 트리, empty 트리도 이진 트리이다.
• 포화 이진 트리 (full binary trees) : 모든 레벨에서 노드들이 모두 채워져 있는 이진 트리
• 완전 이진 트리 (complete binary trees) : 높이가 k인 트리로 가정했을때, k-2까지는 포화 이진 트리이면서 k-1의 좌측부터 순차적으로 채워져 있는 이진 트리

---

이진 트리

이진트리는 재귀적인 방법으로 쉽게 구현 가능하며, 구현하기 위해 필요한 연산은 다음과 같다.

• size() - 현재 트리에 포함되어 있는 노드의 수를 구함
• depth() - 현재 트리의 깊이 (또는 높이) 를 구함
• traversal() - 트리의 각 노드를 정해진 순서로 방문함
• 깊이 우선 순회 DFS (재귀를 통해 구현)
  • 중위 순회 (in-order traverasl): 왼쪽 서브트리를 순회한 뒤 노드 x 를 방문, 그리고 나서 오른쪽 서브트리를 순회
  • 전위 순회 (pre-order traversal): 노드 x 를 방문한 후에 왼쪽 서브트리를 순회, 마지막으로 오른쪽 서브트리를 순
  • 후위 순회 (post-order traversal): 왼쪽 서브트리를 순회, 오른쪽 서브트리를 순회, 그리고 나서 마지막으로 노드 x 를 방문

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

    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

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

깊이 우선 순회에서의 중위 순회 방식과 size,depth 탐색을 위한 코드이다. 각각 노드 위치에서의 탐색을 위한 class이며, 트리 전체를 탐색하려면 root의 여부를 따진 뒤, self.root.size()등을 호출해가며 사용하면 된다. 전위 순회와, 후외 순회는 중위 순회와 구현 방식이 거의 흡사하기 때문에 생략하였다.

• 너비 우선 순회 DFS (큐를 통해 구현)

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

---

이진 탐색 트리

이진 탐색 트리는 모든 노드에 대해서 왼쪽 서브트리에 들어 있는 데이터는 모두 현재 노드의 값 보다 작고 오른쪽 서브트리에 들어 있는 데이터는 모두 현재 노드의 값보다 크도록 트리를 유지한다. 이러한 성질을 만족하는 이진 트리가 이진 탐색 트리인것이다.
이진 탐색 트리의 각 노드는 key-value 쌍으로 이루어져 있으며, key를 이용해서 검색이 가능하다.
배열을 사용한 이진 탐색보다 데이터 원소의 추가 삭제가 용이하다는 장점이 있지만, 메모리 차지가 크다는 단점이 있다.

• insert(): 트리에 주어진 데이터 원소를 추가
• remove(): 특정 원소를 트리로부터 삭제
• lookup(): 특정 원소를 검색 (탐색)
• inorder(): 키의 순서대로 데이터 원소들을 나열
• min(), max(): 최소 키, 최대 키를 가지는 원소를 각각 탐색

 이때 주의 깊게 봐야할 것은 원소의 삭제이다. 이진 탐색 트리의 성질을 계속해서 만족하기 위해서는 삭제 시 트리의 구조를 재정의 할 필요가 있다. 이 때문에 원소 삭제 시, 해당 노드의 부모 노드를 같이 반환해야 한다. 삭제되는 노드의 경우는 보통 아래와 같다

• 리프 노드인 경우
  • 노드 삭제 후, 보모 노드와의 링크 삭제
  • root이면서 leaf일 때는 self.root = None
• 하나의 자식을 가지는 노드인 경우
  • 자식 노드를 자신의 자리에 배치 후, 자식 노드 위치를 삭제
  • 삭제되는 노드가 root일 경우에는 자식을 새로운 root로 설정해야함.
• 두개의 자식을 가지는 노드인 경우
  • 삭제되는 노드의 바로 다음 크기(크거나 작은)의 키를 가지는 노드를 찾아 자신의 자리에 배치 후, 해당 노드의 원래 위치를 삭제
  • 오른쪽 노드의 가장 작은 값이나, 왼쪽 노드의 가장 큰값이 제일 근접한 값이 된다.

이렇게 노드의 자식에 따라 경우가 나뉘기 때문에 각 노드가 몇개의 자식을 가지는지 파악하기 위한 메서드가 필요하다.

    def remove(self, key):
        node, parent = self.lookup(key)
        if node:
            nChildren = node.countChildren()
            # The simplest case of no children
            if nChildren == 0:
                if parent:
                    if node == parent.left:
                        parent.left = None
                    else:
                        parent.right = None
                else:
                    self.root = None
                    
            # When the node has only one child
            elif nChildren == 1:
                if node.left:
                    child = node.left
                else:
                    child = node.right
                if parent:
                    if node == parent.left:
                        parent.left = child
                    else:
                        parent.right = child
     
                else:
                    self.root = child
                    
            # When the node has both left and right children
            else:
                parent = node
                successor = node.right
                while successor.left:
                    parent = successor
                    successor = successor.left
                node.key = successor.key
                node.data = successor.data
           
                if successor == parent.left:
                    parent.left = successor.right
                else:
                    parent.right = successor.right

            return True

        else:
            return False

 

---

 힙   

힙은 루트 노드가 언제나 최대값 또는 최소값을 가지는 완전 이진 트리 이다. 이 경우에 힙을 최대힙 혹은 최소힙이라고 부른다.
이진 탐색 트리와는 다르게 부모 노드는 무조건 자식 노드보다 큰 값을 지니기만 하면 된다. 즉, 원소들이 정확한 크기 순으로 정렬되어 있지 않음을 뜻하는 것이다. 따라서 특정 키 값을 가지는 원소의 탐색이 어렵다. 
다음은 최대힙의 대표적인 연산이다. 위에서 말했듯이 원소 접근이 쉽지 않아 검색과 순회 연산이 없다. 하지만 삽입, 삭제가 O(logN)만에 이루어진다는게 힙의 장점이다.

• insert(item) -  새로운 원소 삽입
  • 트리의 마지막 자리에 새로운 원소를 임시로 저장
  • 부모 노드와 키 값을 비교해가며 최대힙의 성질을 만족할 때까지 위로 이동
• remove - 최대 원소(root node)삭제 후 반환
  • 트리의 마지막 자리 노드를 임시로 루트 노드의 자리에 배치
  • 자식 노드들과 값 비교해가며 더 큰값을 지닌 자식과 자리를 바꿔 아래로 이동

힙을 배열을 이용해서 표현해보자. 현재 위치의 노드를 m이라 하면 인접한 노드들을 다음과 같이 표현가능하다.
- 왼쪽 자식의 번호 : 2*m
- 오른쪽 자식의 번호 : 2*m+1
- 부모 노드의 번호 : m // 2

def remove(self):
        if len(self.data) > 1:
            self.data[1], self.data[-1] = self.data[-1], self.data[1]
            data = self.data.pop(-1)
            self.maxHeapify(1)
        else:
            data = None
        return data


def maxHeapify(self, i):
        left = 2*i
        right = 2*i+1

        smallest = i
        if left < len(self.data)and self.data[left] > self.data[smallest]:
            smallest = left

        if right < len(self.data)and self.data[right] > self.data[smallest]:
            smallest = right

        if smallest != i:
            self.data[i], self.data[smallest] = self.data[smallest], self.data[i]
            self.maxHeapify(smallest)
            
def insert(self, item):
        self.data.append(item)
        if len(self.data) < 2:
            return True
        else:
            idx = len(self.data) - 1
            while idx > 1 and self.data[idx] > self.data[idx // 2]:
                self.data[idx], self.data[idx // 2] = self.data[idx // 2], self.data[idx]
                idx //= 2
        return True

파이썬의 라이브러리를 통해 사용가능하며, import heapq를 작성 후 사용하면 된다.