[자료구조] Week 7: 트리 II - 이진 탐색 트리와 균형 트리

Day 1: 이진 탐색 트리 (BST)의 개념

• 강의 내용:
  • 이진 탐색 트리의 정의와 특징
    • 이진 탐색 트리의 개념
    • BST의 구조적 특징 (모든 노드의 왼쪽 자식은 현재 노드보다 작고, 오른쪽 자식은 현재 노드보다 큼)
  • BST의 주요 연산
    • 삽입, 삭제, 탐색
• 실습:
  • 이진 탐색 트리의 개념 설명 및 주요 연산 구현

# 이진 탐색 트리 노드 클래스 정의
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)

# 탐색 예제
print("노드 15 탐색 결과:", search(root, 15))  # 노드 15 탐색 결과: <__main__.TreeNode object at 0x...>

 

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

• 강의 내용:
  • BST의 삭제 연산
    • 삭제 연산의 경우의 수 (자식 노드가 없는 경우, 하나인 경우, 두 개인 경우)
  • 삭제 연산의 구현
• 실습:
  • BST의 삭제 연산 구현

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

• 강의 내용:
  • 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 4: AVL 트리의 삭제 연산

• 강의 내용:
  • AVL 트리의 삭제 연산
    • 삭제 연산 후의 균형 유지
    • 필요한 회전 연산
• 실습:
  • AVL 트리의 삭제 연산 구현

# AVL 트리에서 최소값 노드 찾기 함수
def min_value_node(node):
    current = node
    while current.left is not None:
        current = current.left
    return current

# 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 5: 레드-블랙 트리의 개념과 특징

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

# 레드-블랙 트리의 기본 개념 설명
# - 레드-블랙 트리: 자가 균형 이진 탐색 트리
# - 노드 색상: 각 노드는 빨간색 또는 검은색
# - 루트 및 리프 노드: 루트는 검은색, 모든 리프(NIL)는 검은색
# - 속성: 빨간색 노드의 자식은 모두 검은색, 모든 경로에서 검은색 노드의 수는 동일

# 레드-블랙 트리의 예시를 시각적으로 설명
# 예:
#         10B
#       /    \
#     5R     15B
#            /  \
#          12R  20R

 

Day 6: 레드-블랙 트리의 구현

• 강의 내용:
  • 레드-블랙 트리의 삽입 연산
    • 삽입 후 색상 조정과 회전 연산
  • 레드-블랙 트리의 삭제 연산
    • 삭제 후 색상 조정과 회전 연산
• 실습:
  • 레드-블랙 트리의 삽입 및 삭제 연산 구현

# 레드-블랙 트리 노드 클래스 정의
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 7: 종합 연습 및 프로젝트

• 강의 내용:
  • 이진 탐색 트리, AVL 트리, 레드-블랙 트리를 사용한 종합 연습 문제 풀이
    • 다양한 트리 관련 문제
    • Q&A 세션
  • 미니 프로젝트
    • 트리를 활용한 간단한 프로그램 구현
    • 예: 데이터베이스 인덱싱 시스템
• 실습:
  • 종합 연습 문제 풀기
  • 미니 프로젝트 작성 및 발표

# 연습 문제 1: 이진 탐색 트리에서 k번째 최소값 찾기
def kth_smallest(root, k):
    stack = []
    while True:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        k -= 1
        if k == 0:
            return root.val
        root = root.right

# k번째 최소값 찾기 예제
root = TreeNode(20)
root = insert(root, 10)
root = insert(root, 30)
root = insert(root, 5)
root = insert(root, 15)
root = insert(root, 25)
root = insert(root, 35)

print("2번째 최소값:", kth_smallest(root, 2))  # 10

# 미니 프로젝트 예제: 데이터베이스 인덱싱 시스템
class DatabaseIndex:
    def __init__(self):
        self.index = RBTree()

    def add_record(self, key):
        self.index.insert(key)

    def search_record(self, key):
        return self.index.search(self.index.root, key)

# 데이터베이스 인덱싱 시스템 사용 예제
db_index = DatabaseIndex()
db_index.add_record(10)
db_index.add_record(20)
db_index.add_record(5)
db_index.add_record(15)

print("데이터베이스 인덱스 전위 순회 결과:")
db_index.index.preorder_helper(db_index.index.root)  # 예: 10 BLACK | 5 RED | 20 RED | 15 BLACK |

 

이 강의는 파이썬의 자료구조 중 이진 탐색 트리, AVL 트리, 레드-블랙 트리를 익히는 것을 목표로 하며, 각 강의는 이론과 실습을 포함합니다. 다음 주차에 대한 상세 강의를 원하시면 말씀해 주세요!