트리(tree)
이진트리 용어
| 용어 | 설명 | 예 |
|---|
| 노드 (Node) | 트리의 각 요소 | A, B, C 등 |
| 간선 (Edge) | 노드끼리 연결하는 선 | A–B, A–C |
| 깊이 (Depth) | 루트에서 해당 노드까지의 간선 수 | A의 깊이: 0B의 깊이: 1 |
| 레벨 (Level) | 깊이 + 1 | A: 1레벨, B: 2레벨 |
| 노드의 차수 (Degree) | 자식 노드의 수 | A의 차수: 2 (B, C) |
| 트리의 차수 | 모든 노드의 차수 중 최대값 | A(2), B(2), G(2) → 2 |
| 높이 (Height) | 루트에서 가장 깊은 노드까지의 정점 수 | 루트 A → G → I → 총 4개 노드⇒ 트리 높이: 4 |
| 루트 노드 (Root Node) | 트리의 시작점 | A |
| 단말 노드 (Leaf Node) | 자식이 없는 노드 | E, F, C, H, I |
| 내부 노드 (Internal Node) | 자식이 있는 노드 (루트 포함) | A, B, D, G |
| 부모 노드 (Parent Node) | 자식을 가진 상위 노드 | B는 E와 F의 부모 |
| 자식 노드 (Child Node) | 부모에 연결된 하위 노드 | E는 B의 자식 |
| 형제 노드 (Sibling Node) | 같은 부모를 가진 노드들 | E와 F는 형제 |
| 조상 노드 (Ancestor) | 해당 노드부터 루트까지의 상위 노드 | I의 조상: G, D, A |
| 후손 노드 (Descendant) | 해당 노드의 하위 모든 노드 | D의 후손: G, H, I |
code
class Node:
def __init__(self, item):
self.item = item
self.left = None
self.right = None
class BinaryTree():
def __init__(self):
self.root = None
전위 순회 (Preorder)
- 자기 자신을 먼저 출력하고 자식 노드를 호출한다.
- 자기 자신 출력 -> 왼쪽 서브 트리 호출 -> 오른쪽 서브 트리 호출
def preorder(self, n):
if n!= None:
print(n.item, '', end='')
if n.left:
self.preodrer(n.left)
if n.right:
self.preodrer(n.right)
후위 순회 (Postorder)
- 자기 자신 출력을 가장 나중에 한다.
- 왼쪽 서브 트리 호출 -> 오른쪽 서브 트리 호출 -> 자기 자신 출력
def postorder(self, n):
if n!= None:
if n.left:
self.postorder(n.left)
if n.right:
self.postorder(n.right)
print(n.item, '', end='')
중위 순회 (Inorder)
- 자기 자신 출력이 중간에 있다
- 왼쪽 서브 트리 호출 -> 자기 자신 출력 -> 오른쪽 서브 트리 호출
def inorder(self, n):
if n!= None:
if n.left:
self.inorder(n.left)
print(n.item, '', end='')
if n.right:
self.inorder(n.right)
레벨 순회 (Levelorder)
def levelorder(self, n):
q = []
q.append(n)
while q:
t = q.pop(0)
print(t.item, '', end='')
if t.left != None:
q.append(t.left)
if t.right != None:
q.append(t.right)
hash 테이블
- 정의: 키를 해시 함수로 변환하여 데이터를 저장하는 구조
- 특징:
- 평균 시간 복잡도: 삽입, 삭제, 탐색 모두
O(1)
- 해시 충돌이 발생할 수 있어 처리 방식 필요 (체이닝, 오픈 어드레싱 등)
- 활용 예시: 딕셔너리, 캐시, 데이터베이스 인덱싱
hash_table = {}
hash_table["apple"] = 10
print(hash_table["apple"])
충돌(Collision)
서로 다른 키가 같은 해시값을 가질 경우를 충돌(Collision)이라고 합니다.
해결 방법:
- 체이닝(Chaining)
- 같은 인덱스에 여러 데이터를 리스트(Linked List) 형태로 저장
table[3] = [(103, 'apple'), (203, 'banana')]
- 개방 주소법(Open Addressing)
- 충돌이 발생하면 다음 인덱스를 선형/제곱 방식 등으로 탐색
- 종류: 선형 탐사(Linear Probing), 제곱 탐사(Quadratic Probing), 이중 해싱(Double Hashing)
해시 테이블의 장점
| 장점 | 설명 |
|---|
| 빠른 접근 속도 | 평균적으로 O(1)의 시간 복잡도 |
| 효율적인 검색 | 키만 있으면 빠르게 데이터 검색 가능 |
| 유연한 키 사용 | 문자열, 정수 등 다양한 타입의 키 사용 가능 |
해시 테이블의 단점
| 단점 | 설명 |
|---|
| 충돌 처리 필요 | 해시 충돌이 성능 저하 원인이 될 수 있음 |
| 메모리 낭비 가능성 | 해시 테이블 크기를 넉넉하게 설정해야 함 |
| 순차 접근 불가 | 인덱스 순으로 정렬된 상태를 보장하지 않음 |
