트리는 계층적인 구조를 나타내는 비선형 자료구조입니다. 각 노드는 데이터와 해당 노드와 연결된 자식 노드들의 집합을 가지고 있습니다. 트리의 가장 상위에 위치한 노드는 루트(root)라고 불리며, 각 노드는 1개의 부모 노드와 여러 개의 자식 노드를 가질 수 있습니다.

트리는 다양한 목적으로 사용될 수 있으며, 많은 종류의 트리가 있습니다. 여기에서는 몇 가지 주요한 트리의 종류를 살펴보겠습니다.

이진 트리 (Binary Tree)

이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리입니다. 각 노드의 왼쪽 자식 노드와 오른쪽 자식 노드는 순서대로 왼쪽 자식과 오른쪽 자식이라고 불립니다. 이진 트리는 매우 유용하며, 데이터의 삽입, 삭제, 검색 등 다양한 작업에 사용될 수 있습니다.

이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리는 이진 트리의 한 종류로, 다음 규칙을 따릅니다. 어떤 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값들만 있고, 오른쪽 서브트리에는 해당 노드보다 큰 값들만 있어야 합니다. 이 규칙으로 인해 이진 탐색 트리는 검색 작업에 매우 효율적입니다.

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

class BinarySearchTree:
  def __init__(self):
    self.root = None
    
  def insert(self, data):
    if self.root is None:
      self.root = Node(data)
    else:
      self._insert_helper(self.root, data)
      
  def _insert_helper(self, current, data):
    if data < current.data:
      if current.left is None:
        current.left = Node(data)
      else:
        self._insert_helper(current.left, data)
    elif data > current.data:
      if current.right is None:
        current.right = Node(data)
      else:
        self._insert_helper(current.right, data)

AVL 트리

AVL 트리는 이진 탐색 트리의 한 종류로, 높이 균형을 유지하는 특징이 있습니다. 각 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 최대 1이 되도록 균형을 조절해줍니다. 이러한 높이 균형을 유지함으로써 탐색 작업의 평균 시간 복잡도를 O(log n)으로 유지할 수 있습니다.

힙 (Heap)

힙은 최댓값 또는 최솟값을 빠르게 찾기 위해 사용하는 트리 기반의 자료구조입니다. 힙은 일반적으로 완전 이진 트리 구조를 가지며, 부모 노드의 값이 자식 노드의 값보다 큰지 또는 작은지에 따라 최대 힙 또는 최소 힙으로 분류됩니다.

import heapq

# 최소 힙 구현
heap = []
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)
print(heap)  # [1, 3, 7, 4]

# 최소값 삭제
heapq.heappop(heap)
print(heap)  # [3, 4, 7]

그래프 (Graph)

그래프는 정점과 정점 사이의 관계를 표현하는 자료구조입니다. 트리는 그래프의 일종으로 볼 수 있으며, 사이클이 없는 연결된 그래프를 트리라고 합니다. 그래프는 방향 그래프와 무방향 그래프로 나뉘며, 각 정점은 다른 정점들과 연결된 간선(edge)으로 표현됩니다.

결론

트리는 다양한 종류와 용도를 가지는 중요한 자료구조입니다. 이진 트리, 이진 탐색 트리, AVL 트리, 힙 등은 데이터 구조와 알고리즘 문제를 해결하는데 있어서 유용하게 사용됩니다. 그래프 역시 트리의 확장 개념으로 많은 문제들을 해결할 수 있는 강력한 도구입니다. 이러한 자료구조들을 활용하여 프로그래밍 문제를 효율적으로 해결할 수 있습니다.