📌트리
2차원 자료구조다. 정점(node)과 간선 (edge)을 이용하여 데이터의 배치 형태를 추상화한 자료 구조
-
노드 (nodes) : 흔히 A, B, C ~로 표현되는 값
-
간선 (edges) : 노드들을 잇는 선
-
루트 노드 (root node) : 가장 상위의 노드
-
리프 노드 (leaf nodes) : 가장 아래 말단의 노드. 가지가 없다
-
내부 노드 (internal nodes) : 루트도 리프도 아닌 노드
-
부모 (parent) 노드와 자식 (child) 노드 : 간선으로 연결된 노드 중 뿌리에 가까운 노드를 부모노드라 하고 리프에 가까운 노드를 자식 노드라 한다. 모든 노드는 여러 개의 자식 노드를 가질 수 있지만 단 하나의 부모 노드만을 갖는다.
-
노드의 수준 (level) : 루트 노드의 level : 0으로 edge로 이루어진 하층으로 갈 때마다 1씩 증가한다. 루트에서 해당 노드까지의 edge수가 곧 노드의 level
-
노드의 차수 (degree) : 자식(서브트리)의 수. 노드에서 뻗어나온 edge 수. 말단 노드(leaf)의 차수는 0이다.
-
트리의 높이 (height) 또는, 깊이 (depth) : 트리의 높이(height) = 최대 수준(level) + 1이다. 루트노드의 level을 1로 설정한다면 말단 노드의 level과 해당 트리의 높이는 같다.
-
부분 트리 (서브트리; subtrees) : 트리 내에서 어느 한 노드를 기준으로 잡은 트리
-
이진 트리 (binary trees) : 모든 노드의 차수가 2 이하인 트리. 재귀적으로 정의할 수 있다. -> (빈 트리이거나 루트노드 + 왼쪽 서브트리 + 오른쪽 서브트리일 때)
-
포화 이진 트리 (full binary trees) : 모든 레벨에서 노드들이 모두 채워져 있는 이진 트리 (높이가 k이고 노드의 개수가 2k-1인 이진트리)
-
완전 이진 트리 (complete binary trees) : 높이 k인 완전 이진 트리 (레벨 k-2까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리. 레벨 k-1에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진 트리)
✍이진 트리의 추상적 자료구조
- 연산의 정의
size() - 현재 트리에 포함되어 있는 노드의 수를 구함
depth() - 현재 트리의 깊이 (또는 높이) 를 구함
순회(traversal) - 정해진 순서대로 노드를 방문해서 처리한다.
이진 트리의 구현 - 노드(Node)
class Node:
def __init__(self, item): # Node에는 Data와 Left Child, Right Child를 가리키는 정보가 있다.
# (양방향 연결 리스트의 prev, next와 비슷)
self.data = item
self.left = None
self.right = None
def size(self): # 재귀적으로 구할 수 있다.
# 전체 이진 트리 size() : 왼쪽 서브트리 size() + 오른쪽 서브트리 size() + 1(자기 자신)
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): # 재귀적으로 구할 수 있다.
# 전체 이진 트리 depth() : 왼쪽 서브트리 depth()와 오른쪽 서브트리 depth()중 더 큰 것 + 1(자기 자신)
l = self.left.depth() if self.left else 0
r = self.right.depth() if self.right else 0
# if l > r:
# return l + 1
# elif r > l:
# return r + 1
return max(l, r) + 1
def inorder(self): # 중위 순회 - 1. 왼쪽 서브트리 2. 자기자신 3. 오른쪽 서브트리
traversal = []
if self.left:
traversal += self.left.inorder()
traversal.append(self.data)
if self.right:
traversal += self.right.inorder()
return traversal
def preorder(self): # 전위 순회 - 1. 자기자신 2. 왼쪽 서브트리 3. 오른쪽 서브트리
traversal = []
traversal.append(self.data)
if self.left:
traversal += self.left.preorder()
if self.right:
traversal += self.right.preorder()
return traversal
def postorder(self): # 후위 순회 - 1. 왼쪽 서브트리 2. 오른쪽 서브트리 3. 자기자신
traversal = []
if self.left:
traversal += self.left.postorder()
if self.right:
traversal += self.right.postorder()
traversal.append(self.data)
return traversal
class BinaryTree:
def __init__(self, r): # 루트 노드만 알고 있으면 그 자식 노드들의 edge로 나머지 노드들을 가르키고 있다.
self.root = r
def size(self):
if self.root:
return self.root.size()
else: # 빈 트리일 경우
return 0
def depth(self):
if self.root:
return self.root.depth()
else:
return 0
def inorder(self):
if self.root:
return self.root.inorder()
else:
return []
def preorder(self):
if self.root:
return self.root.preorder()
else:
return []
def postorder(self):
if self.root:
return self.root.postorder()
else:
return []
def bft(self): # 넓이 우선 순회
traversal = []
q = ArrayQueue()
if self.root == None:
return traversal
else:
q.enqueue(self.root)
while not q.isEmpty():
node = q.dequeue()
traversal.append(node.data)
if node.left and node.right:
q.enqueue(node.left)
q.enqueue(node.right)
continue
elif node.left:
q.enqueue(node.left)
elif node.right:
q.enqueue(node.right)
return traversal
def solution(x):
return 0✍이진 트리의 순회(Traversal - DFT, BFT)
깊이 우선 순회(depth first traversal)
-
중위 순회 (in-order traverasl): 왼쪽 서브트리를 순회한 뒤 노드 x(자기 자신) 를 방문, 그리고 나서 오른쪽 서브트리를 순회
-
전위 순회 (pre-order traversal): 노드 x 를 방문한 후에 왼쪽 서브트리를 순회, 마지막으로 오른쪽 서브트리를 순회
-
후위 순회 (post-order traversal): 왼쪽 서브트리를 순회, 오른쪽 서브트리를 순회, 그리고 나서 마지막으로 노드 x 를 방문
넓이 우선 순회(breadth first traversal)
- 원칙
- level이 낮은 노드를 우선으로 방문
- 같은 수준의 노드들 사이에는,
부모 노드의 방문 순서에 따라 방문
왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문
한 노드를 방문했을 때, 나중에 방문할 노드들을 순서대로 기록해 두어야한다.
-> 큐(queue)를 이용한다. 재귀적인 방법을 사용하지 않는다.
✨넓이 우선 순회 알고리즘 구현
- (초기화)traversal <- 빈 리스트, q <- 빈 큐
- 빈 트리가 아니면, root node를 q에 추가(enqueue)
- q가 비어 있지 않은 동안
3-1. q에서 원소를 추출(dequeue)하고 node라는 변수로 만듦
3-2. node를 방문(node의 data를 append)
3-3. node의 왼쪽, 오른쪽 자식(있으면) 들을 q에 추가 - q가 빈 큐가 되면 모든 노드 방문 완료. traversal 리턴
✍이진 탐색 트리 (Binary Search Trees)
모든 노드에 대해서,
왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고
오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰
성질을 만족하는 이진트리이다. ! 중복되는 데이터 원소 값은 없다고 가정 !
(정렬된) 배열을 이용한 이진 탐색보다 원소의 추가, 삭제가 용이하나 공간 소요가 크다.
이진 탐색 트리의 추상적 자료구조
데이터 표현 - 각 노드는 (key, value)의 쌍으로
- 연산의 정의
insert(): 트리에 주어진 데이터 원소를 추가
remove(): 특정 원소를 트리로부터 삭제
lookup(): 특정 원소를 검색 (탐색)
inorder(): 키의 순서대로 데이터 원소들을 나열
min(), max(): 최소 키, 최대 키를 가지는 원소를 각각 탐색
min() : 왼쪽만 찾아가다 값이 더이상 없으면 자신을 리턴한다. 그것이 가장 작은 값 (max()와 대칭)
lookup() : 입력 인자 - 찾으려는 대상키. 리턴 - 찾은 노드, 그것의 부모 노드. 각각 없으면 None으로 지정
이진 탐색 트리에서 원소 삭제
- 키(key)를 이용해서 노드를 찾는다. (lookup(key))로 노드, 부모 받아옴
해당 키의 노드가 없으면 삭제할 것도 없음
찾은 노드의 부모 노드도 알고 있어야 한다. - 찾은 노드를 제거하고도 이진 탐색 트리 성질을 만족하도록 트리의 구조를 정리한다.
class Node:
def __init__(self, key, data):
self.key = key
self.data = data
self.left = None
self.right = None
def insert(self, key, data):
if key < self.key:
if self.left:
self.left.insert(key, data)
else: # 왼쪽에 값이 더이상 없으면 말단에 온 것이니 값 추가
self.left = Node(key, data)
elif key > self.key:
if self.right:
self.right.insert(key, data)
else:
self.right = Node(key, data)
else:
raise KeyError('Key %s already exists.' % key)
def lookup(self, key, parent=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, parent
def inorder(self):
traversal = []
if self.left:
traversal += self.left.inorder()
traversal.append(self)
if self.right:
traversal += self.right.inorder()
return traversal
def countChildren(self): # 자식 노드 세기
count = 0
if self.left:
count += 1
if self.right:
count += 1
return count
class BinSearchTree:
def __init__(self):
self.root = None
def insert(self, key, data):
if self.root:
self.root.insert(key, data)
else:
self.root = Node(key, data)
def lookup(self, key):
if self.root:
return self.root.lookup(key)
else:
return None, None
def remove(self, key):
node, parent = self.lookup(key)
if node:
nChildren = node.countChildren()
# The simplest case of no children
if nChildren == 0:
if parent:
if parent.left == node:
parent.left = None
elif parent.right == node:
parent.right = None
# 만약 parent 가 있으면
# node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
# parent.left 또는 parent.right 를 None 으로 하여
# leaf node 였던 자식을 트리에서 끊어내어 없앤다.
# 만약 parent 가 없으면 (node 는 root 인 경우)
# self.root 를 None 으로 하여 빈 트리로 만듦
else:
self.root = None
# When the node has only one child
elif nChildren == 1:
# 하나 있는 자식이 왼쪽인지 오른쪽인지를 판단하여
# 그 자식을 어떤 변수가 가리키도록 합니다.
if node.left:
s = node.left
else:
s = node.right
# 만약 parent 가 있으면
# node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
# 위에서 가리킨 자식을 대신 node 의 자리에 넣습니다.
if parent:
if parent.left == node:
parent.left = s
elif parent.right == node:
parent.right = s
# 만약 parent 가 없으면 (node 는 root 인 경우)
# self.root 에 위에서 가리킨 자식을 대신 넣습니다.
else:
self.root = s
# When the node has both left and right children
else:
parent = node
successor = node.right
# parent 는 node 를 가리키고 있고,
# successor 는 node 의 오른쪽 자식을 가리키고 있으므로
# successor 로부터 왼쪽 자식의 링크를 반복하여 따라감으로써
# 순환문이 종료할 때 successor 는 바로 다음 키를 가진 노드를,
# 그리고 parent 는 그 노드의 부모 노드를 가리키도록 찾아냄
while successor.left:
parent = successor
successor = successor.left
# 삭제하려는 노드인 node 에 successor 의 key 와 data 를 대입
node.key = successor.key
node.data = successor.data
# successor 가 parent 의 왼쪽 자식인지 오른쪽 자식인지를 판단하여
# 그에 따라 parent.left 또는 parent.right 를
# successor 가 가지고 있던 (없을 수도 있지만) 자식을 가리키도록 함
if successor == parent.left:
# if successor.left or successor.right:
# 위의 while문에서 succesor의 왼쪽 자식이 없다는 것이 보장되었으니 필요 없는 코드
if successor.right:
parent.left = successor.right
else:
parent.left = None
elif successor == parent.right:
if successor.right:
parent.right = successor.right
else:
parent.right = None
return True
else:
return False
def inorder(self):
if self.root:
return self.root.inorder()
else:
return []
def solution(x):
return 0이진 탐색 트리가 별로 효율적이지 못한 경우
-> 제 구실을 하려면 높이가 비슷하며 왼,오른쪽이 대칭을 유지해야함. 한쪽으로 치우치면 선형 배열과 비슷한 형태로 시간이 오래걸린다.
보다 나은 성능을 보이는 이진 탐색 트리들
-> 높이의 균형을 유지함으로써 O(longn)의 탐색 복잡도 보장. 삽입, 삭제 연산이 보다 복잡 (AVL tree, Red-black tree 참고 이진 탐색 트리인데 구조 유지를 위한 제약이 있음)
