트리 :
그래프 : 자식 노드에 여러 개의 부모 노드가 있는 구조
한 노드에서 시작해서 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결 그래프 (순환하는 길이 없는 그래프)이다.
"나무"라는 뜻이며, 정점 node 과 간선 edge 을 이용하여 데이터의 배치 형태를 추상화한 2차원 자료 구조이다. 데이터 검색과 탐색에 널리 이용된다.
- 노드는 키-값 유형의 구조로 이루어져 있다.
- 트리는 하나의 루트 노드를 갖는다.
- 루트 노드는 0개 이상의 자식 노드를 갖고 있다.
- 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다.
루트 (root) 노드 : 부모가 없는 노드, 맨 위의 노드로, 단 하나만 존재
리프 (leaf) 노드 : 자식이 없는 노드 (= 말단 노드, 잎 노드)
내부 (internal) 노드 : root나 leaf가 아닌 노드
간선 (edge) : 노드를 연결하는 선 (= link, branch)
부분/하위 트리 (subtree) : 노드 하나와 그 자식 노드들로 구성된 트리
형제 (sibling) : 같은 부모를 가지는 노드
부모 (parant) 의 부모~ : 조상 (ancestor)
자식 (child) 의 자식~ : 후손 (descendant)
노드의 크기 (size) : 자신을 포함한 모든 자손 노드의 개수
노드의 깊이 (depth) : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
노드의 레벨 (level) : 트리의 특정 깊이를 가지는 노드의 집합
노드의 차수 (degree) : 하위 트리 개수 = 간선 수 (degree) : 각 노드가 지닌 가지의 수
트리의 차수 (degree of tree) : 트리의 최대 차수
트리의 높이 (height) : 루트 노드에서 가장 깊숙히 있는 노드의 깊이
🖐️ 아래 내용들은 이진 트리를 참고하여 이해하면 쉽다.
트리 추상적 자료구조
연산 :
size()- 현재 트리에 포함되어 있는 노드의 수를 구함depth()- 현재 트리의 깊이(또는 높이; height)를 구함- 순회 (traversal)
구현 :
노드: data, left child, right child트리: rootsize(),depth(): 재귀적인 방법으로 쉽게 구할 수 있다.
class Node :
def __init__(self, item) :
self.data = item
self.left = None
self.right = None
def size(self) :
l = self.left.size() if self.left else 0
r = self.right.size() if self.right else 0
return l + r + 1 # 자기 자신 하나도 더해야 한다.
def depth(self) :
class BinaryTree :
def __init__(self, r) :
self.root = r
def size(self) :
if self.root :
return self.root.size()
else :
return 0
def depth(self) :
if
순회 traversal
정해진 순서대로 노드를 방문해서 처리하는 연산 (트리를 탐색하는 과정)
깊이 우선 순회 (중위, 전위, 후위)와 넓이 우선 순회가 있다.
깊이 우선 순회 Depth first traversal (DFS)
중위 순회 in-order traversal: 왼쪽 서브트리 (하위) → 자기 자신 → 오른쪽 서브트리 순회전위 순회 pre-order traversal: 자기 자신 → 왼쪽 서브트리 → 오른쪽 서브트리 순회후위 순회 post-order traversal: 왼쪽 서브트리 (하위) → 오른쪽 서브트리 순회 → 자기 자신
class Node :
def inorder(self) :
traversal = []
if self.left :
traversal += self.left.inorder()
traversal.append(self.data)
if self.right :
traversal += self.right.inorder()
return traversal
class BinaryTree :
def inorder(self) :
if self.root :
return self.noot.inorder()
else :
return []
넓이 우선 순회 Breadth first traversal (BFS)
- 수준
level이 낮은 노드 우선 방문 - 같은 수준의 노드들 사이에는
- 부모 노드의 방문 순서에 따라 방문
- 왼쪽 자식 노드 → 오른쪽 자식 노드 순서로 방문
넓이 우선 순회 알고리즘 구현하기 :
- traversal에 빈 리스트, q에 빈 큐
초기화 - not empty tree : root node를 q에 추가 (enqueue)
- q가 비어있지 않는 동안
➀ q에서 추출한 (dequeue) 원소를 node에 저장
➁ node 방문 처리(traversal.append)
➂ node의 왼쪽, 오른쪽 자식 노드가 있으면 q에 추가 q == empty: 모든 노드 방문 완료!return traversal
class Binary Tree :
def bft(self) :
부분 트리 (서브 트리, Subtree)
노드 하나와 그 자식 노드들로 구성된 트리
이진 트리 Binary Tree
모든 노드의 차수가 2 이하인 트리
- 재귀적으로 정의 가능 :
빈 트리 (Empty tree)이거나루트 노드 + 왼쪽 서브트리 (이진) + 오른쪽 서브트리 (이진)
1. 이진 탐색 트리 (Binary Search Tree, BST)
왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 큰 이진 트리
- 노드의 키를 기준으로 정렬한 상태
- 모든 원소는 유일한 키를 갖는다.
- 데이터 탐색 시에 유용하다.
정렬된 배열을 이용한 이진 탐색과 비교하여,
장점 : 데이터 원소의 추가, 삭제가 용이하다.
단점 : 공간 소요가 크다.
복잡도 : 항상 O(logn)의 탐색 복잡도를 갖지는 않는다.
추상적 자료구조 알고리즘 구현
이진 탐색 트리의 데이터 표현은 각 노드는 (key, value) 쌍으로 한다. 키를 통해서 데이터 탐색이 가능해진다.
insert(key, value): 트리에 주어진 데이터 원소를 추가remove(key): 특정 원소를 트리로부터 삭제lookup(key): 특정 원소를 검색 (탐색)inorder(): 키의 순서대로 데이터 원소들을 나열min(),max(): 최소 키, 최대 키를 가지는 원소를 각각 탐색
초기화
class Node :
def __init__(self, key, data) :
self.key = key
self.data = data
self.left = None
self.right = None
class BinSearchTree :
def __init__(self) :
self.root = Noneinorder() - 키의 순서대로 데이터 원소들 나열
class Node :
def inorder(self) :
traversal = []
if self.left :
traversal += self.left.inorder()
traversal.append(self)
if self.right :
traversal += self.right.inorder
return traversal
class BinSearchTree :
def inorder(self) :
if self.root :
return self.root.inorder()
else :
return []min(), max() - 최소 키, 최대 키 원소 탐색
class BinSearchTree :
def min(self) :
if self.left :
return.self.root.min()
else :
return self
def min(self) :
if self.root is None :
return None
p = self.root
while p.left is not None :
p = p.left
return p.key
def max(self) :
if self.right :
return.self.root.max()
else :
return self
def max(self) :
if self.root is None :
return None
p = self.root
while p.right is not None :
p = p.right
return p.key트리에 주어진 데이터 원소 추가 - insert()
- 입력 인자 : 키, 데이터 원소
- 리턴 : 없음
class Node :
def insert(self, key, data) :
if key < self.key :
elif key > self.key :
else :
raise KeyError('...')
class BinSearchTree :
def insert(self, key, value) :
if self.root :
self.root.insert(key, data)
else :
self.root = Node(key, data)특정 원소 탐색
- 입력 인자 : 찾으려는 대상 키
- 리턴 : 찾은 노드와 그것의 부모 노드 (각각 없으면 None)
- lookup()
- search()
class Node :
def lookup(self, key, parant=None) :
if key < self.key :
if self.left :
return self.left.lookup(key, self)
else :
return None, None
elif key > self.key :
if self.right :
return self.right.lookup(key, self)
else :
return None, None
else :
return self, parant
class BinSearchTree :
def lookup(self, key) : # 방법 1
if self.root :
return self.root.lookup(key)
else :
return None, None
def search(self, key) : # 방법 2
p = self.root # 루트에 주목
while True :
if p is None :
return None
if key == p.key:
return p.value
elif key < p.key :
p.left
else :
p = p.rightremove()
- key를 이용해서 노드를 찾는다.
➀ 해당 key의 node가 없으면 삭제할 것 없으므로 False
➁ 찾은 node 제거한 경우 True
⦸ 트리 구조 정리를 위해, 찾은 node의 부모 node도 알아내기
- 이진탐색트리 성질을 만족하도록 트리의 구조를 정리한다.
삭제되는 노드 X 가 leaf node인 경우 (leaf 노드 삭제)
⇨ 해당 node 삭제
⇨ 부모 node의 링크 조정
삭제되는 노드 X 가 자식을 하나 가지고 있는 경우 (자식이 하나인 노드 삭제)
⇨ 해당 node 삭제
⇨ X 자리에 그 자식을 대신 배치
⦸ X가 root일 경우, 새로 들어오는 자식이 새 root가 됨
⇨ 부모 node의 링크 조정
삭제되는 노드 X 가 자식을 둘 가지고 있는 경우 (자식이 둘인 노드 삭제)
⇨ X보다 바로 다음 (큰) 키를 가지는 노드 S 찾기
⇨ S의 부모 노드 P 찾기
⇨ X 자리에 S를 대신 배치
⇨ 원래 S를 대신 삭제 후 원래 S의 자식 및 부모 node의 링크 조정
⦸ X 다음으로 큰 키를 가지는 노드 S가 마지막 노드라면 다르게 조정
class BinSearchTree :
def remove(self, key) :
p = self.root # 스캔 중인 노드
parent = None
is_left_child = True # p는 parent의 왼쪽 자식 노드인지 확인
while True :
if p is None : return False # 키 존재하지 않음
if key == p.key : break # 검색 성공
else :
parent = p
if key < p.key :
is_left_child = True
p = p.left
else :
is_left_child = False
p = p.right
if p.left is None: # p에 왼쪽 자식이 없으면
if p is self.root:
self.root = p.right
elif is_left_child:
parent.left = p.right # 부모의 왼쪽 포인터가 오른쪽 자식을 가리킴
else:
parent.right = p.right # 부모의 오른쪽 포인터가 오른쪽 자식을 가리킴
elif p.right is None: # p에 오른쪽 자식이 없으면
if p is self.root:
self.root = p.left
elif is_left_child:
parent.left = p.left # 부모의 왼쪽 포인터가 왼쪽 자식을 가리킴
else:
parent.right = p.left # 부모의 오른쪽 포인터가 왼쪽 자식을 가리킴
else:
parent = p
left = p.left # 서브 트리 안에서 가장 큰 노드
is_left_child = True
while left.right is not None: # 가장 큰 노드 left를 검색
parent = left
left = left.right
is_left_child = False
p.key = left.key # left의 키를 p로 이동
p.value = left.value # left의 데이터를 p로 이동
if is_left_child:
parent.left = left.left # left를 삭제
else:
parent.right = left.left # left를 삭제
return True추상적 자료구조 알고리즘 구현 (최종)
class Node :
def __init__(self, key, data) :
self.key = key
self.data = data
self.left = None
self.right = None
def inorder(self) :
traversal = []
if self.left :
traversal += self.left.inorder()
traversal.append(self)
if self.right :
traversal += self.right.inorder
return traversal
def lookup(self, key, parant=None) :
if key < self.key :
if self.left :
return self.left.lookup(key, self)
else :
return None, None
elif key > self.key :
if self.right :
return self.right.lookup(key, self)
else :
return None, None
else :
return self, parant
def insert(self, key, data) :
if key < self.key :
elif key > self.key :
else :
raise KeyError('...')
def countChildren(self) :
# remove()를 위한 자식 노드 갯수 세는 코드
count = 0
if self.left :
count += 1
if self.right :
count += 1
return count
def remove(self, key) :
class BinSearchTree :
def __init__(self) :
self.root = None
def inorder(self) :
if self.root :
return self.root.inorder()
else :
return []
def min(self) :
if self.left :
return.self.root.min()
else :
return self
def max(self) :
if self.right :
return.self.root.max()
else :
return self
def lookup(self, key) :
if self.root :
return self.root.lookup(key)
else :
return None, None
def insert(self, key, value) :
if self.root :
self.root.insert(key, data)
else :
self.root = Node(key, data)
def remove(self, key) :
node, parent = self.lookup(key)
if node :
return True
else :
return False효율적이지 못한 이진 탐색 트리
한쪽으로 치우친 경우, 이진 탐색 트리의 장점을 발휘하지 못하고, 선형 탐색과 같은 효율을 갖게 된다.
보다 나은 성능의 이진 탐색 트리
비효율적인 단점을 해결하기 위해 높이의 균형을 유지함으로써 O(logn)의 탐색 복잡도를 보장할 수 있다.
하지만 그렇게 트리의 구조를 유지하려다 보면 기초 이진 트리에 비해 삽입, 삭제 연산이 보다 복잡하다.
AVL tree, Red-black tree가 이에 해당된다.
2. 포화 이진 트리 - Full
모든 레벨에서 노드들이 모두 채워져 있는 이진 트리
- 높이가
k이고 노드의 개수가2^k - 1인 이진 트리
3. 완전 이진 트리 - Complete
높이가 k인 완전 이진 트리
- 레벨
k-2까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리 - 레벨
k-1에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진 트리
4. 균형 트리 - Balancing
1) AVL 트리
불균형 이진 트리는 많은 노드가 단 하나의 자식 노드를 갖는 구조이다.
- 메모리 관리를 위해 트리의 균형 조정 필요
- 트리의 역할은 유지하되 가능한 한 최소 높이(자식 노드의 계층이 최소)로 만드는 것
높이 균형 이진 탐색 트리 (Adelson-Velsky and Landis)
불균형 이진 트리에서 서브트리 2개 사이에서 높이 차이를 감지하여 트리 회전 (tree rotation, 균형 조정 과정) 수행한 후의 트리
- 트리 회전으로 인해 노드 하나는 위로 이동, 다른 노드 하나는 아래로 이동
- 시간 복잡도 O(logn)
- 일부 데이터베이스 검색 시스템에서 사용
2) RB 트리
Red-Black 이진 탐색 트리
자체적으로 균형을 조정한다는 점에서 AVL 이진 탐색 트리와 비슷하지만, 트리의 구조 때문에 균형을 조정하는 과정에서 트리 회전수가 적어 AVL 트리보다 효율적이다.
- 시간 복잡도 O(logn)
- 노드마다 빨강 또는 검정으로 해석되는 비트를 포함
- 루트 노드 : 검정
- 빨강 노드의 자식 노드 : 검정
(이진이 아닌) 균형 검색 트리
1) B 트리
컴퓨터 과학자들이 데이터베이스 시스템을 설계할 때 사용하는 데이터 구조
- 자체적인 균형 조정 기능을 갖춘 트리 유형
- 자식 노드 3개 이상을 갖는 부모 노드가 존재
- 많은 파일 시스템의 데이터 계층 구조
2) 2-3 트리
힙
관련 포스트
자료구조 힙 (heaps)에 대해 더 알아보기
자료구조 스택 (Stacks)에 대해 더 알아보기
자료구조 큐 (Queues)에 대해 더 알아보기
자료구조 그래프 (Graph)에 대해 더 알아보기
출처
programmers, gmlwjd9405.github.io, velog.io/@dlgosla, dream-and-develop.tistory.com, velog.io/@vagabondms
planning design development with data