Tree

Posted on | 0 comments

Tree

트리란 empty이거나 아니면 루트와 트리의 집합으로 구성되는데 트리는 루트의 자식노드이다. 트리의 집합은 공집합일 수도 있다.

이진트리

Binary Tree는 각 노드의 자식 수가 2 이하인 트리이다. 이진트리는 컴퓨터 분야에서 널리 활용되는 기본적인 자료구조이다.

이진트리란 empty이거나, 아니면 루트와 2개의 이진트리인 왼쪽 서브트리와 오른쪽 서브트리로 구성된다.

이진트리 종류

  • 포화이진트리(Full Binary Tree)
  • 완전이진트리(Complete Binary Tree)

포화이진트리는 모든 이파리의 깊이가 같고 각 내부노드가 2개의 자식노드를 가지는 트리이다. 완전이진트리는 마지막 레벨을 제외한 각 레벨이 노드로 꽉 차있고, 마지막 레벨에는 노드들이 왼쪽부터 빠짐없이 채워진 트리이다. 포화이진트리는 완전이진트리이기도 하다.

  • 레벨 k에 있는 최대 노드 수는 2의 k-1 제곱이다. (k는 자연수)
  • 높이가 h인 포화이진트리에 있는 노드 수는 2의 h제곱 -1 이다.
  • N개의 노드를 가진 완전이진트리의 높이는 log2의 (N+1)이다.

완전이진트리를 저장하기 위해 리스트를 사용하는 경우, 자식노드들을 참조할 레퍼런스를 저장할 메모리 공간이 필요없기 때문에 매우 효율적이다. 하지만 편향이진트리를 리스트에 저장하는 경우, 트리의 높이가 커질수록 메모리 낭비가 매우 심해진다.

이진트리를 구현하기 위해서는 노드 클래스와 이진트리의 4가지 순회를 위한 메소드, 그리고 트리의 높이를 계산하는 메소드를 선언한다.

이진트리의 연산

앞에서 언급한 이진트리의 4가지 순회를 위한 메소드는 순회 방식에 따라 나뉘어진다.

  • 전위순회 (Preorder Traversal)
  • 중위순회 (Inorder Traversal)
  • 후위순회 (Postorder Traversal)
  • 레벨순회 (Level-order Traversal)

전위순회 : 전위순회는 노드 n에 도착했을 때 n을 먼저 방문한다. 그 다음에 n의 왼쪽 자식노드로 순회를 계속한다. n의 왼쪽 서브트리의 모든 노드들을 방문한 후에는 n의 오른쪽 서브트리의 모든 후손 노드들을 방문한다. (NLR)

def preorder(self, n):
  if n != None:
    print(str(n.item), ' ', end= ' ')
    if n.left:
      self.preorder(n.left)
    if n.right:
      self.preorder(n.right)

중위순회 : 노드 n에 도착하면 n의 방문을 보류하고 n의 왼쪽 서브트리로 순회를 진행한다. 즉, 왼쪽 서브트리의 모든 노드들을 방문한 후에 n을 방문한다. 그리고 n의 오른쪽 서브트리를 같은 방식으로 방문한다. (LNR)

def inorder(self, n):
  if n != None:
    if n.left:
      self.inorder(n.left)
    print(str(n.item), ' ', end= ' ')
    if n.right:
      self.inorder(n.right)

후위순회 : 노드 n에 도착하면 n의 방문을 보류하고 n의 왼쪽 서브트리로 순회를 진행한다. 그리고 n의 오른쪽 서브트리를 같은 방식으로 방문한다. 마지막에 n을 방문한다. (LRN)

def postorder(self, n):
  if n != None:
    if n.left:
      self.postorder(n.left)
    if n.right:
      self.postorder(n.right)
    print(str(n.item), ' ', end= ' ')

레벨순회 : 루트가 있는 최상위 레벨부터 시작하여 각 레벨마다 좌에서 우로 노드들을 방문한다. 레벨순회는 큐 자료구조를 활용한다.

def levelorder(self, root):
  q = [] # 리스트로 큐 자료구조 구현
  q.append(root)
  while len(q) != 0:
    t = q.pop(0) # 큐에서 첫 항목 삭제
    print(str(t.item), ' ', end=' ') # 삭제된 노드 방문
    if t.left != None: # 왼쪽자식, 오른쪽 자식 큐에 삽입
      q.append(t.left)
    if t.right != None:
      q.append(t.right)

이진트리의 높이 : 트리의 높이 = 1 + max(루트의 왼쪽 서브트리 높이, 루트의 오른쪽 서브트리 높이)이다. 여기서 1은 루트 자신을 계산에 반영한 것이다.

def height(self, root):
  if root == None:
    return 0
  return max(self.height(root.left), self.height(root.right)) + 1 # 두 자식노드의 높이 중 큰 높이 + 1

수행시간 : 앞서 설명된 각 연산은 트리의 각 노드를 1번씩만 방문하므로 O(N) 시간이 소요된다.

스레드 이진트리 : 이진트리의 기본 연산들은 레벨순회를 제외하고 모두 스택 자료구조를 사용한다. 함수의 재귀호출은 시스템 스택을 사용하기 때문이다. 스택에 사용되는 메모리 공간의 크기는 트리의 높이에 비례한다.

스택없이 이진트리의 연산을 구현하는 방법은 두 가지가 있다. 이를 스레드 이진트리(Threaded Binary Tree)라 한다.

  • Node에 부모노드를 가리키는 레퍼런스 필드를 추가로 선언하여 순회에 사용
  • 노드의 None 레퍼런스 활용(None 레퍼런스 공간에 다음에 방문할 노드의 레퍼런스 저장)

스레드 이진트리는 각 노드의 오른쪽 None 레퍼런스를 다음 방문할 노드를 참조하게 하고, 각 노드의 왼쪽 None 레퍼런스를 직접 방문한 노드를 참조하게 한 이진트리이다.

이진힙

이진힙(Binary Heap)은 우선순위큐(Priority Queue)를 구현하는 가장 기본적인 자료구조이다. 우선순위큐란 가장 높은 우선순위를 가진 항목에 접근하거나 해당 항목을 삭제하는 연산과 임의의 우선순위를 가진 항목을 삽입하는 연산을 지원하는 자료구조이다.