[알고리즘] Week 5: 탐색 알고리즘 II - 이진 탐색 트리 및 균형 트리

Day 1: 이진 탐색 트리 (Binary Search Tree)

• 강의 내용:
  • 이진 탐색 트리의 개념
    • 이진 탐색 트리의 정의 및 특징
    • 이진 탐색 트리의 시간 복잡도 분석 (평균 O(log n), 최악 O(n))
  • 이진 탐색 트리의 주요 연산
    • 삽입, 삭제, 탐색
• 실습:
  • 이진 탐색 트리 구현 및 기본 연산

# 이진 탐색 트리 노드 클래스 정의
class TreeNode:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

# 이진 탐색 트리 삽입 함수 정의
def insert(root, key):
    if root is None:
        return TreeNode(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)

# 이진 탐색 트리 사용 예제
root = TreeNode(10)
root = insert(root, 5)
root = insert(root, 20)
root = insert(root, 3)
root = insert(root, 7)
root = insert(root, 15)
root = insert(root, 25)

# 탐색 예제
result = search(root, 15)
print("이진 탐색 트리에서 15의 탐색 결과:", result.val if result else "찾을 수 없음")

 

Day 2: 이진 탐색 트리의 삭제 연산

• 강의 내용:
  • 이진 탐색 트리의 삭제 연산
    • 삭제 연산의 경우의 수 (자식 노드가 없는 경우, 하나인 경우, 두 개인 경우)
    • 시간 복잡도 분석
  • 삭제 연산 구현
• 실습:
  • 이진 탐색 트리의 삭제 연산 구현 및 예제

# 이진 탐색 트리 삭제 함수 정의
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

# 이진 탐색 트리 삭제 연산 예제
root = delete_node(root, 20)
print("노드 20 삭제 후 전위 순회 결과:")
def preorder(root):
    if root:
        print(root.val, end=' ')
        preorder(root.left)
        preorder(root.right)

preorder(root)  # 10 5 3 7 25 15

 

Day 3: 균형 트리의 개념

• 강의 내용:
  • 균형 트리의 정의와 필요성
    • 균형 트리의 개념
    • 균형 트리가 필요한 이유
  • 대표적인 균형 트리 종류
    • AVL 트리
    • 레드-블랙 트리
• 실습:
  • 간단한 균형 트리 예제 설명

### 균형 트리의 필요성
- 이진 탐색 트리에서 최악의 경우 시간 복잡도를 줄이기 위해 사용
- 노드의 균형을 유지하여 탐색, 삽입, 삭제 연산의 효율성을 높임

### 대표적인 균형 트리
1. **AVL 트리**
   - 각 노드의 왼쪽 서브트리와 오른쪽 서브트리 높이 차이가 1 이하인 이진 탐색 트리
2. **레드-블랙 트리**
   - 각 노드가 빨간색 또는 검은색을 가지며, 특정 규칙을 만족하는 이진 탐색 트리

 

Day 4: AVL 트리 (AVL Tree)

• 강의 내용:
  • AVL 트리의 개념과 특징
    • AVL 트리의 정의 및 특징
    • AVL 트리의 균형 조건 (각 노드의 왼쪽 서브트리와 오른쪽 서브트리 높이 차이가 1 이하)
  • AVL 트리의 주요 연산
    • 회전 연산 (단순 회전: LL, RR / 이중 회전: LR, RL)
• 실습:
  • AVL 트리의 삽입 및 회전 연산 구현

# AVL 트리 노드 클래스 정의
class AVLTreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1

# AVL 트리 높이 계산 함수
def height(node):
    if not node:
        return 0
    return node.height

# AVL 트리 회전 함수 정의
def right_rotate(y):
    x = y.left
    T2 = x.right

    x.right = y
    y.left = T2

    y.height = max(height(y.left), height(y.right)) + 1
    x.height = max(height(x.left), height(x.right)) + 1

    return x

def left_rotate(x):
    y = x.right
    T2 = y.left

    y.left = x
    x.right = T2

    x.height = max(height(x.left), height(x.right)) + 1
    y.height = max(height(y.left), height(y.right)) + 1

    return y

# AVL 트리 균형 인수 계산 함수
def get_balance(node):
    if not node:
        return 0
    return height(node.left) - height(node.right)

# AVL 트리 삽입 함수 정의
def insert(node, key):
    if not node:
        return AVLTreeNode(key)
    elif key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)

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

    balance = get_balance(node)

    # LL 회전
    if balance > 1 and key < node.left.key:
        return right_rotate(node)

    # RR 회전
    if balance < -1 and key > node.right.key:
        return left_rotate(node)

    # LR 회전
    if balance > 1 and key > node.left.key:
        node.left = left_rotate(node.left)
        return right_rotate(node)

    # RL 회전
    if balance < -1 and key < node.right.key:
        node.right = right_rotate(node.right)
        return left_rotate(node)

    return node

# AVL 트리 사용 예제
root = None
keys = [10, 20, 30, 40, 50, 25]

for key in keys:
    root = insert(root, key)

# AVL 트리 출력 함수
def preorder(root):
    if root:
        print(root.key, end=' ')
        preorder(root.left)
        preorder(root.right)

print("AVL 트리 전위 순회 결과:")
preorder(root)  # 30 20 10 25 40 50

 

Day 5: 레드-블랙 트리 (Red-Black Tree)

• 강의 내용:
  • 레드-블랙 트리의 개념과 특징
    • 레드-블랙 트리의 정의 및 특징
    • 레드-블랙 트리의 속성 (노드 색상, 루트 및 리프 노드 속성, 균형 유지)
  • 레드-블랙 트리의 주요 연산
    • 삽입, 삭제, 탐색
• 실습:
  • 레드-블랙 트리의 삽입 연산 구현

# 레드-블랙 트리 노드 클래스 정의
class RBTreeNode:
    def __init__(self, key, color="RED"):
        self.key = key
        self.color = color
        self.left = None
        self.right = None
        self.parent = None

# 레드-블랙 트리 클래스 정의
class RBTree:
    def __init__(self):
        self.TNULL = RBTreeNode(0, "BLACK")
        self.root = self.TNULL

    # 좌회전
    def left_rotate(self, x):
        y = x.right
        x.right = y.left
        if y.left != self.TNULL:
            y.left.parent = x
        y.parent = x.parent
        if x.parent == None:
            self.root = y
        elif x == x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y
        y.left = x
        x.parent = y

    # 우회전
    def right_rotate(self, x):
        y = x.left
        x.left = y.right
        if y.right != self.TNULL:
            y.right.parent = x
        y.parent = x.parent
        if x.parent == None:
            self.root = y
        elif x == x.parent.right:
            x.parent.right = y
        else:
            x.parent.left = y
        y.right = x
        x.parent = y

    # 삽입 함수 정의
    def insert(self, key):
        node = RBTreeNode(key)
        node.parent = None
        node.left = self.TNULL
        node.right = self.TNULL
        node.color = "RED"

        y = None
        x = self.root

        while x != self.TNULL:
            y = x
            if node.key < x.key:
                x = x.left
            else:
                x = x.right

        node.parent = y
        if y == None:
            self.root = node
        elif node.key < y.key:
            y.left = node
        else:
            y.right = node

        if node.parent == None:
            node.color = "BLACK"
            return

        if node.parent.parent == None:
            return

        self.fix_insert(node)

    # 삽입 후 색상 조정 및 회전
    def fix_insert(self, k):
        while k.parent.color == "RED":
            if k.parent == k.parent.parent.right:
                u = k.parent.parent.left
                if u.color == "RED":
                    u.color = "BLACK"
                    k.parent.color = "BLACK"
                    k.parent.parent.color = "RED"
                    k = k.parent.parent
                else:
                    if k == k.parent.left:
                        k = k.parent
                        self.right_rotate(k)
                    k.parent.color = "BLACK"
                    k.parent.parent.color = "RED"
                    self.left_rotate(k.parent.parent)
            else:
                u = k.parent.parent.right
                if u.color == "RED":
                    u.color = "BLACK"
                    k.parent.color = "BLACK"
                    k.parent.parent.color = "RED"
                    k = k.parent.parent
                else:
                    if k == k.parent.right:
                        k = k.parent
                        self.left_rotate(k)
                    k.parent.color = "BLACK"
                    k.parent.parent.color = "RED"
                    self.right_rotate(k.parent.parent)
            if k == self.root:
                break
        self.root.color = "BLACK"

    # 레드-블랙 트리 전위 순회
    def preorder_helper(self, node):
        if node != self.TNULL:
            print(node.key, node.color, end=' | ')
            self.preorder_helper(node.left)
            self.preorder_helper(node.right)

# 레드-블랙 트리 사용 예제
rbt = RBTree()
rbt.insert(10)
rbt.insert(20)
rbt.insert(30)
rbt.insert(40)
rbt.insert(50)
rbt.insert(25)

print("레드-블랙 트리 전위 순회 결과:")
rbt.preorder_helper(rbt.root)  # 예: 30 BLACK | 20 RED | 10 BLACK | 25 BLACK | 40 RED | 50 BLACK |

 

Day 6: 균형 트리의 삭제 연산

• 강의 내용:
  • AVL 트리의 삭제 연산
    • 삭제 연산 후의 균형 유지
    • 필요한 회전 연산
  • 레드-블랙 트리의 삭제 연산
    • 삭제 연산 후의 색상 조정 및 회전
• 실습:
  • AVL 트리와 레드-블랙 트리의 삭제 연산 구현

# AVL 트리 삭제 함수 정의
def delete_node(root, key):
    if not root:
        return root

    elif key < root.key:
        root.left = delete_node(root.left, key)
    elif key > root.key:
        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.key = temp.key
        root.right = delete_node(root.right, temp.key)

    if root is None:
        return root

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

    balance = get_balance(root)

    # LL 회전
    if balance > 1 and get_balance(root.left) >= 0:
        return right_rotate(root)

    # LR 회전
    if balance > 1 and get_balance(root.left) < 0:
        root.left = left_rotate(root.left)
        return right_rotate(root)

    # RR 회전
    if balance < -1 and get_balance(root.right) <= 0:
        return left_rotate(root)

    # RL 회전
    if balance < -1 and get_balance(root.right) > 0:
        root.right = right_rotate(root.right)
        return left_rotate(root)

    return root

# AVL 트리 삭제 연산 예제
root = delete_node(root, 10)
print("노드 10 삭제 후 AVL 트리 전위 순회 결과:")
preorder(root)  # 30 20 25 40 50

 

Day 7: 종합 연습 및 프로젝트 준비

• 강의 내용:
  • 탐색 알고리즘 종합 연습
    • 다양한 탐색 알고리즘 문제 풀이
    • 알고리즘 성능 분석 및 최적화
  • 프로젝트 준비
    • 프로젝트 주제 선정 및 요구사항 분석
    • 프로젝트 구현 계획 수립
• 실습:
  • 탐색 알고리즘 종합 연습 문제 풀기
  • 프로젝트 주제 및 계획 수립

### 종합 연습 문제 예시
1. 주어진 데이터셋에서 다양한 탐색 알고리즘을 사용하여 요소 찾기
2. 이진 탐색 트리와 균형 트리를 활용한 데이터 삽입, 삭제, 탐색 연습
3. 레드-블랙 트리와 AVL 트리의 성능 비교

### 프로젝트 주제 예시
1. 대규모 데이터셋 검색 시스템
2. 실시간 데이터 스트림 처리 도구
3. 동적 데이터 관리 시스템

### 프로젝트 요구사항 예시
1. 대규모 데이터셋 검색 시스템:
   - 대규모 데이터셋 입력 및 저장
   - 다양한 탐색 알고리즘을 통한 데이터 검색
   - 검색된 데이터 출력 및 성능 분석

### 프로젝트 계획 예시
1. 데이터 입력 모듈 구현
2. 탐색 알고리즘 구현 (이진 탐색 트리, AVL 트리, 레드-블랙 트리 등)
3. 데이터 출력 및 성능 분석 모듈 구현

 

이 강의는 파이썬의 탐색 알고리즘, 특히 이진 탐색 트리와 균형 트리의 기본 개념과 구현을 익히는 것을 목표로 하며, 각 강의는 이론과 실습을 포함합니다. 다음 주차에 대한 상세 강의를 원하시면 말씀해 주세요!