트리 Tree
노드(Node)와간선(Edge)으로 이루어진 자료구조위의 그림에서는 1을 가진 노드가
루트(Root)노드모든 노드들은 0개 이상의 자식 노드를 가지고 있으며, 이를 부모-자식 관계로 부른다.
특징
트리에는 사이클이 존재할 수 없다.
사이클이 만들어지는 것은 그래프이다.
모든 노드는 자료형으로 표현이 가능하다.
루트에서 한 노드로 가는 경로는 유일한 경로 뿐이다.
노드의 개수가 N개면, 간선은 N-1개를 가진다.
트리 순회 방식
1. 전위 순회 (Pre-order)
각 루트를 순차적으로 먼저 방문하는 방식
Root -> 왼쪽 자식 -> 오른쪽 자식
1 → 2 → 4 → 8 → 9 → 5 → 10 → 11 → 3 → 6 → 13 → 7 → 14
def preorder(a):
if a <= N:
print(tree[a], end=' ')
preorder(a * 2)
preorder(a * 2 + 1)
N = 9
tree = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
preorder(1)2. 중위 순회 (In-order)
왼쪽 하위 트리를 방문 후, 루트를 방문하는 방식
왼쪽 자식 -> Root -> 오른쪽 자식
8 → 4 → 9 → 2 → 10 → 5 → 11 → 1 → 6 → 13 → 3 →14 → 7
def inorder(a):
if a <= N:
inorder(a * 2)
print(tree[a], end=' ')
inorder(a * 2 + 1)
N = 9
tree = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
preorder(1)3. 후위 순회 (Post-order)
왼쪽 하위 트리부터 하위를 모두 방문 후 루트를 방문하는 방식
왼쪽 자식 -> 오른쪽 자식 -> Root
8 → 9 → 4 → 10 → 11 → 5 → 2 → 13 → 6 → 14 → 7 → 3 → 1
def postorder(a):
if a <= N:
postorder(a * 2)
postorder(a * 2 + 1)
print(tree[a], end=' ')
N = 9
tree = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
preorder(1)4. 레벨 순회 (Level-order)
루트부터 계층별로 방문하는 방식
1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → 11 → 13 → 14
이진 탐색 트리 Binary Search Tree
이진 트리
각 노드가 최대 2개의 자식 노드를 갖는 트리
이진 탐색 트리 (BST)
이진 트리에서 아래와 같은 조건이 있는 트리
모든 노드는 왼쪽 가지에 포함되는 어떤 숫자보다도 큰 값을 가진다.
모든 노드는 오른쪽 가지에 포함되는 어떤 숫자보다도 작은 값을 가진다.
탐색 동작과정
찾는 숫자가 현재 노드 값과 같다면 탐색 성공
찾는 숫자가 현재 노드 값보다 작다면 왼쪽으로 이동
찾는 숫자가 현재 노드 값보다 크다면 오른쪽으로 이동
삽입 동작과정
삽입할 숫자가 현재 노드 값보다 작다면 왼쪽으로 이동
삽입할 숫자가 현재 노드 값보다 크다면 오른쪽으로 이동
자식 노드가 없을 때까지 1번~2번 과정을 반복하고, 자식 노드가 없을 때 만들어서 연결시킨다.
class Node:
def __init__(self, value):
# double linked list
self.value = value
self.left = None
self.right = None
class NodeMgmt:
def __init__(self, head):
self.head = head # 루트노드
# 삽입
def insert(self, value):
self.current_node = self.head
while True:
if value < self.current_node.value:
if self.current_node.left != None: # 이미 가지고 있다면
self.current_node = self.current_node.left # 비교대상 바꿈
else:
self.current_node.left = Node(value) # 없다면 새로 만들어 연결
break
else:
if self.current_node.right != None: # 이미 가지고 있다면
self.current_node = self.current_node.right # 비교대상 바꿈
else:
self.current_node.right = Node(value)
break
# 이진 탐색 트리 출력
def search(self, value):
self.current_node = self.head
while self.current_node:
if self.current_node.value == value: # 찾았을 때
return True
elif value < self.current_node.value:
self.current_node = self.current_node.left
else:
self.current_node = self.current_node.right
return False # 탐색 실패했을 때
# 실행
head = Node(1)
BST = NodeMgmt(head)
BST.insert(2)
BST.insert(3)
print(BST.search(2))
print(BST.search(5))삭제 동작과정
이진 탐색 트리의 삭제는 아래의 경우로 나눠서 볼 수 있다.
1. Leaf Node 삭제
부모 노드가 삭제할 노드를 가리키지 않도록 한다.
2. 자식 노드가 한 개인 노드 삭제
삭제할 노드의 부모 노드가 삭제할 노드의 자식 노드를 가리키도록 한다.
3. 자식 노드가 두 개인 노드 삭제
삭제할 노드의 오른쪽 자식 중 가장 작은 값을 부모 노드가 가리키도록 하거나
삭제할 노드의 왼쪽 자식 중 가장 큰 값을 부모 노드가 가리키도록 한다.
전제
삭제할 노드가 자식이 두 개 있으면, 대체 노드가 필요하다.
보통 오른쪽 서브트리에서 가장 왼쪽에 있는 노드 (최솟값 노드)를 찾아서 삭제할 노드를 대체한다.
단계
삭제할 노드(4)의 오른쪽 자식(8) 선택
오른쪽 서브트리에서 가장 작은 노드를 찾아야 한다.
오른쪽 자식에서 가장 왼쪽에 있는 노드(6) 선택
6이 대체할 노드가 된다.
6을 4의 부모(10)의 왼쪽 자식으로 연결
10.left = 6
6의 왼쪽 브랜치를 4의 왼쪽 자식(3)으로 연결
6.left = 3
6의 오른쪽 브랜치를 4의 오른쪽쪽 자식(8)으로 연결
6.right = 8
8의 원래 자식이 있었는지 확인
8.left = 7
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def find_min(node):
""" 오른쪽 서브트리에서 가장 작은 노드 찾기 (왼쪽으로 이동) """
while node.left:
node = node.left
return node
def delete_node(root, key):
""" BST에서 key 값을 가진 노드를 삭제하는 함수 """
if not root:
return None
# 1️⃣ 삭제할 노드를 찾기
if key < root.val:
root.left = delete_node(root.left, key)
elif key > root.val:
root.right = delete_node(root.right, key)
else:
# 2️⃣ 자식이 하나도 없거나 하나만 있는 경우
if not root.left:
return root.right # 오른쪽 자식이 있거나 None 반환
elif not root.right:
return root.left # 왼쪽 자식이 있거나 None 반환
# 3️⃣ 자식이 두 개 있는 경우: 오른쪽 서브트리에서 최솟값 찾기
min_node = find_min(root.right)
root.val = min_node.val # 최솟값을 현재 노드로 이동
root.right = delete_node(root.right, min_node.val) # 원래 최솟값 노드 삭제
return root
def inorder_traversal(root):
""" 중위 순회 (Inorder Traversal) - BST 구조 확인용 """
return inorder_traversal(root.left) + [root.val] + inorder_traversal(root.right) if root else []
# ✅ 예제 트리 생성
root = TreeNode(10)
root.left = TreeNode(4)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(8)
root.left.right.left = TreeNode(6)
root.left.right.right = TreeNode(9)
root.left.right.left.right = TreeNode(7)
root.right.right = TreeNode(19)
print("삭제 전:", inorder_traversal(root))
# 🔥 노드 4 삭제
root = delete_node(root, 4)
print("삭제 후:", inorder_traversal(root))
시간복잡도
노드가 n개 일때 트리의 높이
h = logn이다.즉, 이진 탐색트리의 시간복잡도는
O(logn)으로 리스트에서 탐색할시에는 O(n)이 걸리는 것에 비해 빠르게 처리가능하다.