[코딩테스트] 4주차: 트리와 이진 탐색 트리

트리와 이진 탐색 트리

학습 주제

• 트리의 기본 개념과 순회 방법 (전위, 중위, 후위 순회)
• 이진 탐색 트리 (BST)의 삽입, 삭제, 탐색
• 균형 잡힌 트리 (AVL 트리, 레드-블랙 트리)

학습 목표

• 트리 자료구조의 기본 개념을 이해하고 구현할 수 있다.
• 이진 탐색 트리의 삽입, 삭제, 탐색 연산을 구현할 수 있다.
• 균형 잡힌 트리의 개념을 이해하고 기본적인 구현을 할 수 있다.

학습 자료

• 트리의 기본 개념 설명 및 구현
• 이진 탐색 트리 (BST) 설명 및 구현
• AVL 트리와 레드-블랙 트리의 기본 개념 설명

실습 문제

트리 순회 (전위, 중위, 후위 순회)

• 주어진 트리를 전위, 중위, 후위 순회하는 함수를 작성하세요.

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

def pre_order(root):
    if root:
        print(root.val, end=' ')
        pre_order(root.left)
        pre_order(root.right)

def in_order(root):
    if root:
        in_order(root.left)
        print(root.val, end=' ')
        in_order(root.right)

def post_order(root):
    if root:
        post_order(root.left)
        post_order(root.right)
        print(root.val, end=' ')

# Test
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print("Pre-order traversal:")
pre_order(root)  # 1 2 4 5 3
print("\nIn-order traversal:")
in_order(root)  # 4 2 5 1 3
print("\nPost-order traversal:")
post_order(root)  # 4 5 2 3 1

 

2. 이진 탐색 트리 (BST) 삽입, 삭제, 탐색

• 이진 탐색 트리를 구현하고, 삽입, 삭제, 탐색 연산을 수행하는 함수를 작성하세요.

class BSTNode:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def insert(root, key):
    if root is None:
        return BSTNode(key)
    else:
        if root.val < key:
            root.right = insert(root.right, key)
        else:
            root.left = insert(root.left, key)
    return root

def search(root, key):
    if root is None or root.val == key:
        return root
    if root.val < key:
        return search(root.right, key)
    return search(root.left, key)

def delete_node(root, key):
    if root is None:
        return root
    if key < root.val:
        root.left = delete_node(root.left, key)
    elif key > root.val:
        root.right = delete_node(root.right, key)
    else:
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left
        temp = min_value_node(root.right)
        root.val = temp.val
        root.right = delete_node(root.right, temp.val)
    return root

def min_value_node(node):
    current = node
    while(current.left is not None):
        current = current.left
    return current

# Test
root = BSTNode(50)
root = insert(root, 30)
root = insert(root, 20)
root = insert(root, 40)
root = insert(root, 70)
root = insert(root, 60)
root = insert(root, 80)

print("In-order traversal of the BST:")
in_order(root)  # 20 30 40 50 60 70 80

print("\nSearch for 40 in the BST:")
print(search(root, 40))  # Node with value 40

print("\nDelete 20 from the BST:")
root = delete_node(root, 20)
in_order(root)  # 30 40 50 60 70 80

 

3. 균형 잡힌 트리 (AVL 트리)

• AVL 트리를 구현하고, 삽입 연산을 수행하는 함수를 작성하세요.

class AVLNode:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key
        self.height = 1

def insert_avl(root, key):
    if not root:
        return AVLNode(key)
    elif key < root.val:
        root.left = insert_avl(root.left, key)
    else:
        root.right = insert_avl(root.right, key)

    root.height = 1 + max(get_height(root.left), get_height(root.right))

    balance = get_balance(root)
    if balance > 1 and key < root.left.val:
        return right_rotate(root)
    if balance < -1 and key > root.right.val:
        return left_rotate(root)
    if balance > 1 and key > root.left.val:
        root.left = left_rotate(root.left)
        return right_rotate(root)
    if balance < -1 and key < root.right.val:
        root.right = right_rotate(root.right)
        return left_rotate(root)
    return root

def get_height(root):
    if not root:
        return 0
    return root.height

def get_balance(root):
    if not root:
        return 0
    return get_height(root.left) - get_height(root.right)

def right_rotate(z):
    y = z.left
    T3 = y.right
    y.right = z
    z.left = T3
    z.height = 1 + max(get_height(z.left), get_height(z.right))
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    return y

def left_rotate(z):
    y = z.right
    T2 = y.left
    y.left = z
    z.right = T2
    z.height = 1 + max(get_height(z.left), get_height(z.right))
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    return y

# Test
root = None
values = [10, 20, 30, 40, 50, 25]
for value in values:
    root = insert_avl(root, value)

print("In-order traversal of the AVL tree:")
in_order(root)  # 10 20 25 30 40 50

 

추가 학습 자료

• Binary Search Tree (BST) - GeeksforGeeks
• AVL Tree - GeeksforGeeks
• Tree Traversals (Inorder, Preorder, Postorder) - GeeksforGeeks

---

추천 문제

백준 (Baekjoon)

1. 문제명: 트리 순회
   • 설명: 주어진 트리에 대해 전위, 중위, 후위 순회를 수행하는 문제입니다.
   • 문제 유형: 트리, 트리 순회
   • 난이도: 실버 I
   • 주소: 트리 순회
2. 문제명: 이진 검색 트리
   • 설명: 주어진 노드들을 삽입하여 이진 검색 트리를 구성하고, 후위 순회를 수행하는 문제입니다.
   • 문제 유형: 트리, 이진 검색 트리 (BST)
   • 난이도: 골드 V
   • 주소: 이진 검색 트리
3. 문제명: 트리의 높이와 너비
   • 설명: 주어진 이진 트리에 대해 각 레벨의 너비를 계산하고, 가장 넓은 레벨과 그 너비를 구하는 문제입니다.
   • 문제 유형: 트리
   • 난이도: 골드 II
   • 주소: 트리의 높이와 너비

프로그래머스 (Programmers)

1. 문제명: 가장 먼 노드
   • 설명: 트리에서 특정 노드로부터 가장 먼 노드를 찾는 문제입니다.
   • 문제 유형: 트리, 그래프 탐색 (BFS)
   • 난이도: 레벨 3
   • 주소: 가장 먼 노드
2. 문제명: 길 찾기 게임
   • 설명: 주어진 노드 좌표를 이용해 이진 탐색 트리를 구성하고, 전위 순회와 후위 순회를 수행하는 문제입니다.
   • 문제 유형: 트리, 이진 탐색 트리 (BST), 트리 순회
   • 난이도: 레벨 3
   • 주소: 길 찾기 게임
3. 문제명: 단어 변환
   • 설명: 주어진 단어 목록에서 시작 단어에서 목표 단어로 변환하는 데 필요한 최소 변환 횟수를 구하는 문제입니다. (그래프 탐색 문제로 트리와 유사한 구조)
   • 문제 유형: 그래프 탐색 (BFS, DFS)
   • 난이도: 레벨 3
   • 주소: 단어 변환