Binary tree 기초개념 및 구현실습
.
그림, 실습코드 등 학습자료 출처 : https://github.com/ythwork
트리의 정의
-
connected acyclic graph : 연결된 그리고 사이클이 없는 그래프
-
트리는 1개 이상의 노드로 이루어진 집합
-
트리는 그래프의 일종이다.
-
‘연결된’ : 인접해있거나 노드간에 연결이 되어 있다는 의미
-
‘사이클’ : 노드의 방향을 타고 가다가 결국에는 나 자신에게 돌아오는 경로가 있는 것, 또는 루프라고 부르기도 한다.
아래 그림이 사이클의 예시라고 할 수 있다.
-
참고로 트리라는 범주가 있으면 이진트리는 트리가 아니다.
-
별개의 트리가 여러개 있는 경우 : forest라고 부른다.
-
루트노드를 반드시 가진다.
-
트리를 구성하는 노드간 끊어진 부분이 없어야 한다. (노드간에 단순 경로가 존재)
-
나머지 노드들은 분리집합 T1, T2, … , Tn으로 분할 가능하다.
-
T1, …, T2 등은 각각 하나의 트리(서브트리) 로 구성된다.(재귀적 정의)
트리의 용어
-
차수(degree) : 어떤 노드의 자식 노드의 개수
-
트리의 차수(degree of a tree) : 전체 트리에 있는 노드중 최대 차수
-
leaf node : 차수가 0인 노드, 즉 자식이 없다.
말노드(terminal node)라고도 부름
- level : 루트의 레벨을 1로 하고 자식으로 내려가면서 하나씩 더한다.
(루트의 레벨을 0으로 하는 경우도 많다.)
- 트리의 높이(height) or 깊이(depth) : 트리가 가지는 최대 레벨
- 노드와 에지의 관계는 다음과 같다.
노드의 개수 : n이고, 에지의 개수가 e라면 ‘e = n-1’가 성립한다.
- forest : 루트 노드를 제거한 나머지 서브 트리의 집합
아래 그림은 포레스트 예시
- 트리에서 레벨이란
기준으로 하는 노드를 기준으로 자식으로 뻗어나가는 높이의 정도.
아래의 그림은 루트노드를 기준으로 레벨을 표시한 것이다.
이진트리(binary tree)
-
이진트리는 자식노드가 최대 2개인 트리를 말한다.
-
degree는 자식노드의 수를 말한다.
-
정의 : 공집합 혹은 루트와 왼쪽 서브트리, 오른쪽 서브트리로 이루어진 유한집합, 각각의 서브트리는 모두 이진트리이다.
-
공집합은 아무것도 안들어 있는 공노드라고 보면 된다.
-
아래의 그림이 이진트리의 전형적인 예시이다.
- 이진트리의 특징
1) 레벨 l에서 최대 노드수 : 2의 l-1승개
2) 높이가 h인 이진트리의 최대 노드 수 : 2의 h승 -1개
3) 높이가 h인 이진트리의 최소 노드 수 : h개
- 이진트리의 특성 적용예시
트리의 높이 : 3
최대 노드의 수 : 2의 3승 -1 = 7
최소 노드의 수 : 3
포화 이진트리 (full binary tree)
이진트리의 일종이다.
높이가 h이면 노드수가 2의 h승 -1 개인 트리
아래의 그림처럼 모든 레벨이 꽉 차 있다.
그래서 포화 이진트리는 모든 레벨이 꽉차 있는 이진트리라고 보면 된다.
완전 이진트리 (complete binary tree)
높이가 h이면 레벨 h-1까지 노드 수는 2의 h-1승 -1개이고, 레벨 h에서는 왼쪽부터 오른쪽으로 노드가 채워져 있는 트리를 말한다.
바로 아래레벨(전레벨)까지는 꽉차 있는 것이고, 가장 아래 레벨은 왼쪽부터 오른쪽으로 노드가 채워져 있는 구조이다.
다시말해 위에서 아래로 좌에서 우로 노드가 채워져 있는 트리
완전이진트리는 포화이진트리를 포함하는 개념이다
-> 아래의 그림에서 4번과 5번 노드가 없어도 완전이진트리이다
- 포화이진트리와 완전이진트리
이런 트리를 완전이진트리라고 한다. 포화 이진트리랑 헷갈리면 안된다.
완전 이진트리는 위에서 아래로 그리고 좌에서 우로 노드가 채워지는 트리를 말한다.
편향 이진트리 (skewed binary tree)
왼쪽이나 오른쪽 서브트리만 가지는 트리
트리에서 순회란 중복되지 않고 어떤 자료구조의 모든 노드(또는 데이터)를 방문하는 것
데이터를 저장하는 것도 중요하지만 탐색을 할 수 있어야 하고 탐색한다는 것은 순회가 가능한가와 맞물린다.
[트리에서 순회]
1) 전위순회
2) 중위순회
3) 후위순회
4) 레벨순서순회
[그래프에서의 순회]
1) DFS : 깊이우선 탐색
2) BFS : 너비우선 탐색
참고로 전위, 중위, 후위순회가 깊이우선 탐색의 응용버전이고 레벨순서순회는 너비우선 탐색의 응용버전이다.
왜냐하면 트리는 그래프의 일종이기 때문에 탐색방법도 결국에는 그래프에서 쓰는 방법의 일종이다.
파이썬 코드로 구현해보기
- 전,중,후위 순회 구현시 반복문 활용을 위한 스텍 구현
재귀로 전위, 중위 , 후위를 구현하는 경우에는 스텍 자료구조를 이용한다.
class Node:
def __init__(self, data=None):
self.__data=data
self.__next=None
@property
def data(self):
return self.__data
@data.setter
def data(self, data):
self.__data=data
@property
def next(self):
return self.__next
@next.setter
def next(self, n):
self.__next=n
class Stack:
def __init__(self):
self.top=None
def empty(self):
if self.top is None:
return True
else:
return False
def push(self, data):
new_node = Node(data)
if self.empty():
self.top = new_node
return
new_node.next = self.top
self.top=new_node
def pop(self):
if self.empty():
return None
cur = self.top
self.top = self.top.next
return cur.data
def peek(self):
if self.empty():
return None
return self.top.data
if __name__ =="__main__":
s = Stack()
s.push(1)
s.push(2)
s.push(3)
s.push(4)
s.push(5)
while not s.empty():
print(s.pop(), end=" ")
5 4 3 2 1
- 레벨순서 순회 구현시 활용을 위한 큐 구현
class Node:
def __init__(self, data=None):
self.__data=data
self.__next=None
@property
def data(self):
return self.__data
@data.setter
def data(self, data):
self.__data=data
@property
def next(self):
return self.__next
@next.setter
def next(self, n):
self.__next=n
class Queue:
def __init__(self):
self.front = None
self.rear = None
def empty(self):
if not self.front:
return True
return False
def enqueue(self, data):
new_node = Node(data)
if self.empty():
self.front = new_node
self.rear = new_node
return
self.rear.next = new_node
self.rear = new_node
def dequeue(self):
if self.empty():
return None
if self.front is self.rear:
self.rear = self.rear.next
cur = self.front
self.front = self.front.next
return cur.data
def peek(self):
if self.empty():
return None
return self.front.data
if __name__ == "__main__":
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
q.enqueue(5)
while not q.empty():
print(q.dequeue(), end=' ')
1 2 3 4 5
- 순회구현을 위한 트리구현
우리는 아래와 같은 그림의 트리를 구현할 것이다.
class TreeNode:
def __init__(self, data=None):
## 데이터 저장하는 부분
self.__data=data
## 왼쪽 자식
self.__left=None
## 오른쪽 자식
self.__right=None
def __del__(self):
print('data {} is deleted'.format(self.__data))
@property
def data(self):
return self.__data
@data.setter
def data(self, data):
self.__data=data
@property
def left(self):
return self.__left
@left.setter
def left(self, left):
self.__left=left
@property
def right(self):
return self.__right
@right.setter
def right(self, right):
self.__right=right
n1=TreeNode(1)
n2=TreeNode(2)
n3=TreeNode(3)
n4=TreeNode(4)
n5=TreeNode(5)
n6=TreeNode(6)
n7=TreeNode(7)
n1.left=n2; n1.right=n3
n2.left=n4; n2.right=n5
n3.left=n6; n3.right=n7 # 세미콜론을 붙여도 에러는 나지 않는다. 여러 구문을 이어쓸때는 세미콜론을 쓰기도 하기 때문이다.
전위순회(preorder)
루트노드 -> 왼쪽자식 -> 오른쪽자식
cur -> cur.left -> cur.right
나이키 로고 모양으로 순회가 돈다.
노드가 자식이 있는 경우 재귀적으로 또 전위순회를 한다.
현재노드를 방문 -> 현재노드의 왼쪽 서브트리(여기서도 재귀적으로 전위순회) -> 노드의 오른쪽 서브트리(여기서도 재귀적으로 전위순회)
- 전위순회(preorder) 파이썬 코드 구현
재귀함수를 이용한 구현
[ 재귀함수 구현 시 주의사항 ]
재귀함수의 구현조건에 대해 항상 생각해야 한다.
1) 기저조건
2) 점화식
def preorder(cur):
if not cur: ## cur가 empty node라면
return ## 나가버린다 <- 이부분이 base case(기저조건)
print(cur.data, end=' ') ## 방문해서 데이터를 출력하는 코드
## 자기 내부적으로 또 전위순회를 하는 코드
## cur의 left -> cur의 right
preorder(cur.left)
preorder(cur.right)
preorder(n1)
1 2 4 5 3 6 7
스텍을 이용한 구현
-
반복문 : 가독성은 떨어지지만 성능이 재귀보다 좋다.
-
재귀 : 가독성이 좋지만 성능이 반복문으로 구현하는 것보다 퍼포먼스가 상당히 떨어진다.
def iter_preorder(cur):
s = Stack()
while True:
while cur:
print(cur.data, end=' ')
s.push(cur)
cur= cur.left
cur = s.pop()
if not cur:
break
cur = cur.right
iter_preorder(n1)
1 2 4 5 3 6 7
중위순회(inorder)
재귀함수를 이용한 구현
def inorder(cur):
if not cur:
return
inorder(cur.left)
print(cur.data, end=' ')
inorder(cur.right)
inorder(n1)
4 2 5 1 6 3 7
스텍을 이용한 구현
def iter_inorder(cur):
s = Stack()
while True:
while cur:
s.push(cur)
cur = cur.left
cur = s.pop()
if not cur:
break
print(cur.data, end = ' ')
cur = cur.right
iter_inorder(n1)
4 2 5 1 6 3 7
후위순회(postorder)
파이썬 코드 구현
def postorder(cur):
if not cur:
return
postorder(cur.left)
postorder(cur.right)
print(cur.data, end=' ')
postorder(n1)
4 5 2 6 7 3 1
스텍을 이용한 구현
def iter_postorder(cur):
s1 = Stack()
s2 = Stack()
s1.push(cur)
while not s1.empty():
cur = s1.pop()
s2.push(cur)
if cur.left: ## 만약에 왼쪽 자식이 있다면 왼쪽 스텍(s1)에 넣는다.
s1.push(cur.left)
if cur.right: ## 만약에 오른쪽 자식이 있다면 왼쪽 스텍(s1)에 넣는다.
s1.push(cur.right)
while not s2.empty():
cur = s2.pop()
print(cur.data, end=' ')
iter_postorder(n1)
4 5 2 6 7 3 1
레벨순서순회(levelorder)
def levelorder(cur):
q=Queue()
q.enqueue(cur)
while not q.empty():
cur = q.dequeue()
print(cur.data, end=' ')
if cur.left:
q.enqueue(cur.left)
if cur.right:
q.enqueue(cur.right)
levelorder(n1)
1 2 3 4 5 6 7