[코딩 테스트] 16일차: 트리 알고리즘

트리 알고리즘

트리는 노드와 간선으로 이루어진 자료구조로, 사이클이 없는 연결 그래프입니다. 이진 트리, 이진 탐색 트리(BST), AVL 트리, 힙(Heap) 등 다양한 트리 구조가 있으며, 각기 다른 특성과 용도를 가지고 있습니다.

이진 트리와 이진 탐색 트리 (BST)

이진 트리는 각 노드가 최대 두 개의 자식을 가지는 트리입니다. 이진 탐색 트리(BST)는 이진 트리의 일종으로, 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 값을 가지는 트리입니다.

 

예제: 이진 탐색 트리 구현

JavaScript

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(value) {
    const newNode = new TreeNode(value);
    if (!this.root) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);
    }
  }

  insertNode(node, newNode) {
    if (newNode.value < node.value) {
      if (!node.left) {
        node.left = newNode;
      } else {
        this.insertNode(node.left, newNode);
      }
    } else {
      if (!node.right) {
        node.right = newNode;
      } else {
        this.insertNode(node.right, newNode);
      }
    }
  }

  search(value) {
    return this.searchNode(this.root, value);
  }

  searchNode(node, value) {
    if (!node) {
      return false;
    }
    if (value < node.value) {
      return this.searchNode(node.left, value);
    } else if (value > node.value) {
      return this.searchNode(node.right, value);
    } else {
      return true;
    }
  }
}

const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(3);
bst.insert(7);

console.log(bst.search(7)); // true
console.log(bst.search(8)); // false

Python

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        new_node = TreeNode(value)
        if not self.root:
            self.root = new_node
        else:
            self._insert_node(self.root, new_node)

    def _insert_node(self, node, new_node):
        if new_node.value < node.value:
            if not node.left:
                node.left = new_node
            else:
                self._insert_node(node.left, new_node)
        else:
            if not node.right:
                node.right = new_node
            else:
                self._insert_node(node.right, new_node)

    def search(self, value):
        return self._search_node(self.root, value)

    def _search_node(self, node, value):
        if not node:
            return False
        if value < node.value:
            return self._search_node(node.left, value)
        elif value > node.value:
            return self._search_node(node.right, value)
        else:
            return True

bst = BinarySearchTree()
bst.insert(10)
bst.insert(5)
bst.insert(15)
bst.insert(3)
bst.insert(7)

print(bst.search(7)) # True
print(bst.search(8)) # False

AVL 트리

AVL 트리는 이진 탐색 트리의 일종으로, 삽입이나 삭제 후에 스스로 균형을 맞추는 자가 균형 이진 탐색 트리입니다. 각 노드의 왼쪽 서브트리와 오른쪽 서브트리 높이 차이가 최대 1이 되도록 유지합니다.

 

예제: AVL 트리 구현

JavaScript

class AVLTreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
    this.height = 1;
  }
}

class AVLTree {
  constructor() {
    this.root = null;
  }

  insert(value) {
    this.root = this._insertNode(this.root, value);
  }

  _insertNode(node, value) {
    if (!node) {
      return new AVLTreeNode(value);
    }

    if (value < node.value) {
      node.left = this._insertNode(node.left, value);
    } else if (value > node.value) {
      node.right = this._insertNode(node.right, value);
    } else {
      return node;
    }

    node.height = 1 + Math.max(this._getHeight(node.left), this._getHeight(node.right));

    const balance = this._getBalance(node);

    if (balance > 1 && value < node.left.value) {
      return this._rotateRight(node);
    }

    if (balance < -1 && value > node.right.value) {
      return this._rotateLeft(node);
    }

    if (balance > 1 && value > node.left.value) {
      node.left = this._rotateLeft(node.left);
      return this._rotateRight(node);
    }

    if (balance < -1 && value < node.right.value) {
      node.right = this._rotateRight(node.right);
      return this._rotateLeft(node);
    }

    return node;
  }

  _rotateLeft(z) {
    const y = z.right;
    const T2 = y.left;

    y.left = z;
    z.right = T2;

    z.height = 1 + Math.max(this._getHeight(z.left), this._getHeight(z.right));
    y.height = 1 + Math.max(this._getHeight(y.left), this._getHeight(y.right));

    return y;
  }

  _rotateRight(z) {
    const y = z.left;
    const T3 = y.right;

    y.right = z;
    z.left = T3;

    z.height = 1 + Math.max(this._getHeight(z.left), this._getHeight(z.right));
    y.height = 1 + Math.max(this._getHeight(y.left), this._getHeight(y.right));

    return y;
  }

  _getHeight(node) {
    if (!node) {
      return 0;
    }
    return node.height;
  }

  _getBalance(node) {
    if (!node) {
      return 0;
    }
    return this._getHeight(node.left) - this._getHeight(node.right);
  }
}

const avl = new AVLTree();
avl.insert(10);
avl.insert(20);
avl.insert(30);
avl.insert(40);
avl.insert(50);
avl.insert(25);

console.log(JSON.stringify(avl.root, null, 2));

Python

class AVLTreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.height = 1

class AVLTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        self.root = self._insert_node(self.root, value)

    def _insert_node(self, node, value):
        if not node:
            return AVLTreeNode(value)

        if value < node.value:
            node.left = self._insert_node(node.left, value)
        elif value > node.value:
            node.right = self._insert_node(node.right, value)
        else:
            return node

        node.height = 1 + max(self._get_height(node.left), self._get_height(node.right))

        balance = self._get_balance(node)

        if balance > 1 and value < node.left.value:
            return self._rotate_right(node)

        if balance < -1 and value > node.right.value:
            return self._rotate_left(node)

        if balance > 1 and value > node.left.value:
            node.left = self._rotate_left(node.left)
            return self._rotate_right(node)

        if balance < -1 and value < node.right.value:
            node.right = self._rotate_right(node.right)
            return self._rotate_left(node)

        return node

    def _rotate_left(self, z):
        y = z.right
        T2 = y.left

        y.left = z
        z.right = T2

        z.height = 1 + max(self._get_height(z.left), self._get_height(z.right))
        y.height = 1 + max(self._get_height(y.left), self._get_height(y.right))

        return y

    def _rotate_right(self, z):
        y = z.left
        T3 = y.right

        y.right = z
        z.left = T3

        z.height = 1 + max(self._get_height(z.left), self._get_height(z.right))
        y.height = 1 + max(self._get_height(y.left), self._get_height(y.right))

        return y



    def _get_height(self, node):
        if not node:
            return 0
        return node.height

    def _get_balance(self, node):
        if not node:
            return 0
        return self._get_height(node.left) - self._get_height(node.right)

avl = AVLTree()
avl.insert(10)
avl.insert(20)
avl.insert(30)
avl.insert(40)
avl.insert(50)
avl.insert(25)

def print_tree(node, level=0, prefix="Root: "):
    if node is not None:
        print(" " * (level * 4) + prefix + str(node.value))
        if node.left: print_tree(node.left, level + 1, "L--- ")
        if node.right: print_tree(node.right, level + 1, "R--- ")

print_tree(avl.root)

힙 (Heap)

힙은 완전 이진 트리로, 최대 힙(max-heap)과 최소 힙(min-heap)으로 분류됩니다. 최대 힙에서는 부모 노드가 자식 노드보다 크거나 같고, 최소 힙에서는 부모 노드가 자식 노드보다 작거나 같습니다.

 

예제: 최소 힙 구현

JavaScript

class MinHeap {
  constructor() {
    this.heap = [];
  }

  insert(value) {
    this.heap.push(value);
    this._heapifyUp(this.heap.length - 1);
  }

  extractMin() {
    if (this.heap.length === 0) {
      return null;
    }
    if (this.heap.length === 1) {
      return this.heap.pop();
    }
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this._heapifyDown(0);
    return min;
  }

  _heapifyUp(index) {
    let parentIndex = Math.floor((index - 1) / 2);
    while (index > 0 && this.heap[parentIndex] > this.heap[index]) {
      [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
      index = parentIndex;
      parentIndex = Math.floor((index - 1) / 2);
    }
  }

  _heapifyDown(index) {
    let smallest = index;
    const leftChild = 2 * index + 1;
    const rightChild = 2 * index + 2;

    if (leftChild < this.heap.length && this.heap[leftChild] < this.heap[smallest]) {
      smallest = leftChild;
    }
    if (rightChild < this.heap.length && this.heap[rightChild] < this.heap[smallest]) {
      smallest = rightChild;
    }
    if (smallest !== index) {
      [this.heap[smallest], this.heap[index]] = [this.heap[index], this.heap[smallest]];
      this._heapifyDown(smallest);
    }
  }
}

const minHeap = new MinHeap();
minHeap.insert(3);
minHeap.insert(1);
minHeap.insert(6);
minHeap.insert(5);
minHeap.insert(2);
minHeap.insert(4);

console.log(minHeap.extractMin()); // 1
console.log(minHeap.extractMin()); // 2
console.log(minHeap.extractMin()); // 3

Python

class MinHeap:
    def __init__(self):
        self.heap = []

    def insert(self, value):
        self.heap.append(value)
        self._heapify_up(len(self.heap) - 1)

    def extract_min(self):
        if len(self.heap) == 0:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()
        min_value = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._heapify_down(0)
        return min_value

    def _heapify_up(self, index):
        parent_index = (index - 1) // 2
        while index > 0 and self.heap[parent_index] > self.heap[index]:
            self.heap[parent_index], self.heap[index] = self.heap[index], self.heap[parent_index]
            index = parent_index
            parent_index = (index - 1) // 2

    def _heapify_down(self, index):
        smallest = index
        left_child = 2 * index + 1
        right_child = 2 * index + 2

        if left_child < len(self.heap) and self.heap[left_child] < self.heap[smallest]:
            smallest = left_child
        if right_child < len(self.heap) and self.heap[right_child] < self.heap[smallest]:
            smallest = right_child
        if smallest != index:
            self.heap[smallest], self.heap[index] = self.heap[index], self.heap[smallest]
            self._heapify_down(smallest)

min_heap = MinHeap()
min_heap.insert(3)
min_heap.insert(1)
min_heap.insert(6)
min_heap.insert(5)
min_heap.insert(2)
min_heap.insert(4)

print(min_heap.extract_min()) # 1
print(min_heap.extract_min()) # 2
print(min_heap.extract_min()) # 3

연습 문제

문제 1: 이진 탐색 트리의 최소 값과 최대 값 찾기

이진 탐색 트리에서 최소 값과 최대 값을 찾는 프로그램을 작성하세요.

JavaScript

class BinarySearchTree {
  // ... (이전 코드와 동일)

  findMin() {
    return this._findMinNode(this.root).value;
  }

  _findMinNode(node) {
    if (node.left === null) {
      return node;
    }
    return this._findMinNode(node.left);
  }

  findMax() {
    return this._findMaxNode(this.root).value;
  }

  _findMaxNode(node) {
    if (node.right === null) {
      return node;
    }
    return this._findMaxNode(node.right);
  }
}

const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(3);
bst.insert(7);

console.log(bst.findMin()); // 3
console.log(bst.findMax()); // 15

Python

class BinarySearchTree:
    # ... (이전 코드와 동일)

    def find_min(self):
        return self._find_min_node(self.root).value

    def _find_min_node(self, node):
        if node.left is None:
            return node
        return self._find_min_node(node.left)

    def find_max(self):
        return self._find_max_node(self.root).value

    def _find_max_node(self, node):
        if node.right is None:
            return node
        return self._find_max_node(node.right)

bst = BinarySearchTree()
bst.insert(10)
bst.insert(5)
bst.insert(15)
bst.insert(3)
bst.insert(7)

print(bst.find_min()) # 3
print(bst.find_max()) # 15

문제 2: 힙에서 K번째 작은 요소 찾기

주어진 힙에서 K번째 작은 요소를 찾는 프로그램을 작성하세요.

JavaScript

function findKthSmallest(heap, k) {
  const minHeap = new MinHeap();
  heap.forEach(value => minHeap.insert(value));

  for (let i = 0; i < k - 1; i++) {
    minHeap.extractMin();
  }
  return minHeap.extractMin();
}

const heap = [3, 1, 6, 5, 2, 4];
const k = 3;
console.log(findKthSmallest(heap, k)); // 3

Python

def find_kth_smallest(heap, k):
    min_heap = MinHeap()
    for value in heap:
        min_heap.insert(value)

    for _ in range(k - 1):
        min_heap.extract_min()
    return min_heap.extract_min()

heap = [3, 1, 6, 5, 2, 4]
k = 3
print(find_kth_smallest(heap, k)) # 3

결론

이번 글에서는 코딩 테스트 준비를 위해 트리 알고리즘에 대해 배웠습니다. 이를 통해 이진 탐색 트리(BST), AVL 트리, 힙(Heap)의 개념과 구현 방법을 익혔습니다. 다음 글에서는 그래프의 심화 알고리즘에 대해 알아보겠습니다.

다음 글에서 만나요!