탐색, 자료구조, 알고리즘
트리, 이진탐색 트리 실습
데이터왕
2023. 12. 23. 15:34
In [ ]:
#17강 트리
'''정점(node)과 간선(edge)을 이용하여 데이터의 배치 형태를 추상화
A 루트노드 LEVEL0
B C 내부노드 LEVEL1
D E F 내부노드 LEVEL2
G H J K 리프모드 LEVEL3
노드 D는 G H J의 부모
G H J는 D의 자식노드, G H J는 형제간
A는 G H J 의 조상/ G H J는 A의 후손
트리의 높이=최대레벨+1 = (위의경우) 4
서브트리 :
D
G H J
노드의 차수 = 자식(서브트리)의 수=degree
A의 경우 degree:2 (짝대기 갯수)
B의 경우 degree:1
G H J E K degree:0 =(자식이 없어 0)리프노드
이진트리: 모든 노드의 차수가 2이하인트리(짝대기 2이하,빈 트리포함)
루트노드+왼쪽 서브트리+오른쪽 서브트리
(단, 이 때 왼쪽과 오른쪽 서브트리 또한 이진트리)
A
B C
D E F G
H J
A
B
C
포화 이진 트리(Full Binary Tree)
모든 레벨에서 노드들이 채워져 있는 이진트리
A
B C
D E F G
높이가 K라면 노드의 개수가 2^k-1 인 이진트리
완전 이진트리
높이 k인 완전 이진트리
레벨 k-2까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리
레벨 k-1에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진트리
A
B C ->여기까지 포화
D E ->순서대로
A
B C
D E F G ->여기까지 포화
H ->순서대로
'''
In [ ]:
#18강 이진트리
'''연산의 정의
size() - 현재 트리에 포함되어 있는 노드의 수를 구함
depth()- 현재 트리의 깊이 (또는 높이; height)를 구함
순회(traversal)'''
class Node:
#왼쪽 오른쪽 가지 None으로 초기화
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):
#왼쪽 값이 존재하면 왼쪽의 깊이를 재귀적으로 구해나감
l = self.left.depth() if self.left else 0
r = self.right.depth() if self.right else 0
#왼쪽 오른쪽중 큰수+1
return max(l,r)+1
class BinaryTree:
#특정노드 r을 root로 삼는다.
def __init__(self, r):
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 solution(x):
return 0
In [ ]:
'''이진 트리의 순회
깊이 우선 순회(중위순회, 전위순회, 후위순회)
중위순회(왼쪽순회->자기자신->오른쪽 순회)
A
B C
D E F G
H J(오른쪽)
순서 : A B D H D B E A F J C G
'''
class Node:
def __init__(self, item):
self.data = item
self.left = None
self.right = None
def inorder(self):
traversal=[]
#만약 왼쪽이 있다면
if self.left:
traversal+=self.left.inorder()
#자기자신
traversal.append(self.data)
#오른쪽이 있다면
if self.right:
traversal+=self.right.inorder()
return traversal
#전위 순회 (자기자신->왼쪽->오른쪽)
#A B D H E C F J G
def preorder(self):
traversal = []
traversal.append(self.data)
if self.left:
traversal += self.left.preorder()
if self.right:
traversal += self.right.preorder()
return traversal
#후위 순회 (왼쪽->오른쪽->자기자신)
#H D E B J F G C A
def postorder(self):
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):
self.root = r
# 루트 노드에서 중위 순회 시작
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 solution(x):
return 0
In [ ]:
#넓이 우선 순회
'''원칙
수준 낮은 노드를 우선으로 방문
같은 수준에서는
부모 노드의 방문 순서에 따라 방문
왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문
재귀적 방법이 적합한가?
-> 적합하지 않다. 앞과 다른 방식 알고리즘 필요
A LEVEL0
B C LEVEL1
D E F G LEVEL2
H J LEVEL3
같은 레벨에서는 왼쪽 자식노드 먼저
한노드를 방문했을 때, 나중에 방문할 노드들을 순서대로 기록
(큐를 이용)
1 A
2 A 큐 B
3 A 큐 BC
A처리가 끝나 큐에서 꺼낸다.
4 AB 큐 C
5 AB 큐 CD
6 AB 큐 CDE
7 ABC 큐 DE
8 ABC 큐 DEFG
9 ABCD 큐 EFG
10 ABCD 큐 EFGH
D의 처리가 끝나 큐에서 꺼낸다.
11 ABCDE 큐 FGH
E의 처리가 끝나 큐에서 꺼낸다.
12 ABCDEF 큐 GH
13 ABCDEF 큐 GHJ
F의 처리가 끝나 큐에서 꺼낸다.
14 ABCDEF 큐 HJ
G의 처리가 끝나 큐에서 꺼낸다.
15 ABCDEFH 큐 J
H의 처리가 끝나 큐에서 꺼낸다.
16 ABCDEFHJ 큐
큐가 비어 끝났다.
class BinaryTree:
def bft(self):
1(초기화) traversal<-빈리스트, q<- 빈 큐
2 빈 트리가 아니면, root node를 큐에 추가 (enqueue)
3 q가 비어 있지 않은 동안
3.1 node <-q에서 원소를 추출(dequeue)
3.2 node를 방문
3.3 node의 왼쪽, 오른쪽 자식(있으면) q에 추가
4 q 가 빈큐가 되면 모든 방문 완료
'''
#19강 실습: 이진 트리의 넓이 우선 순회
class ArrayQueue:
def __init__(self):
self.data = []
def size(self):
return len(self.data)
def isEmpty(self):
return self.size() == 0
def enqueue(self, item):
self.data.append(item)
def dequeue(self):
return self.data.pop(0)
def peek(self):
return self.data[0]
class Node:
def __init__(self, item):
self.data = item
self.left = None
self.right = None
class BinaryTree:
def __init__(self, r):
self.root = r
def bft(self):
queue = ArrayQueue()
queue.enqueue(self.root)
traversal=[]
while True:
try:
curr=queue.dequeue()
traversal.append(curr.data)
except:
break
if curr.left:
queue.enqueue(curr.left)
if curr.right:
queue.enqueue(curr.right)
return traversal
def solution(x):
return 0
In [ ]:
#이진 탐색 트리
'''모든 노드에 대해서
왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고
오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰
성질을 만족하는 이진트리
(중복되는 데이터 원소는 없는 것으로 가정)
5
2 8
1 4 6 9
7
예) 6을 찾아라!
5 보다 크니까 오른쪽
8보다 작으니 왼쪽
6발견
크기순 정렬된 배열을 이용한 이진 탐색과 비교 장단점
1 3 7 8 12 15 17 21 24 30 32 34 39 45 51 62
장점 : 데이터 원소의 추가, 삭제가 용이, O(logn)->항상은 아님
단점 : 공간 소요가 큼
이진 탐색 트리의 추상적 자료구조
데이터 표현 - 각 노드는(key,value)의 쌍으로지정,
key를 이용해 검색 및 복잡한 데이터 레코드로 확장가능
5 john
2 8 david mary
1 4 6 9
7
연산의 정의
insert(key,data) - 트리에 주어진 데이터 원소를 추가
remove(key) -특정 원소를 트리로부터 삭제
lookup(key) -특정 원소를 검색
inorder() - 키의 순서대로 데이터 원소를 나열
min(),max() - 최소 키, 최대 키를 가지는 원소를 각각 탐색
5
2 8
1 4 6 9
7
예) 3을 삽입하라!
5 2 4 3(4왼)
'''
#20강 실습: 이진 탐색 트리의 원소 삽입 연산 구현
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:
return self.left.insert(key,data)
#못찾는다면 없는거니 삽입
else:
self.left = Node(key, data)
elif key>self.key:
if self.right:
return self.right.insert(key,data)
#못찾는다면 없는거니 삽입
else:
self.right= Node(key, data)
else:
raise KeyError('...')
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,parent=None):
#만약 찾으려는 키가 작다면
if key<self.key:
#왼쪽을 살펴봄, 재귀로 lookup호출
if self.left:
return self.left.lookup(key,self)
#못찾는다면 없는거니 None
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
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 inorder(self):
if self.root:
return self.root.inorder()
else:
return []
def min(self):
#특성상 계속 왼쪽으로만 가면 가장 작은수
if self.left:
return self.left.min()
else:
return self
def max(self):
#특성상 계속 왼쪽으로만 가면 가장 작은수
if self.right:
return self.right.max()
else:
return self
def lookup():
if self.root:
#루트 노드에서 key를 인자로한 lookup
return self.root.lookup(key)
else:
return None,None
def solution(x):
return 0
In [ ]:
#이진 탐색 트리에서 원소 삭제
'''
1 키를 이용해 노드를 찾는다.
-해당 노드 없으면 삭제할게없음
-찾은 노드의 부모노드도 알고 있어야함(2번때문)
2 찾은 노드를 제거해도 이진탐색트리 성질을 가지도록 구조정리
인터페이스의 설계
입력 : 키
출력 : 삭제한 경우 True, 해당 키의 노드가 없는 경우 False
삭제되는 노드가
1 말단(leaf) 노드인경우
노드를 없애고, 부모노드 링크 조정(좌? 우? -> none)
2 자식이 하나인 경우
삭제되는 노드 자리에 그 자식을 대신 배치
자식이 좌?우?, 부모노드 링크 조정(좌? 우?)
3 자식이 둘인 경우
삭제되는 노드보다 바로 다음 (큰)키를 가지는 노드를 찾아
그 노드를 대신 배치함
리프노드일 경우
5
2 8
1 4 6 9
7
예)4를 삭제하라
p 2 x 4
4를 없애고 p의 오른쪽 링크를 None으로
자식이 하나인 노드일 경우
p
x o
c
예) x를 삭제해라
자식 c를 x자리에
p
c o
자식이 둘인 노드의 삭제
5
2 8
1 4 6 9
7
예) 5를 삭제하라!
5보다 하나 더 큰 애를 찾아 대체한다.
6발견 6을 5에 대체
6을 삭제-왼쪽은 있을리없음, 오른쪽 값 7로 6을 대체
예) 8을 삭제하라
8보다 큰 9를 발견
9를 8자리에 넣고....
이진탐색트리가 효율적이지 못한 경우(치우친 경우)
T=BinSearchTree()
T.insert(4,'John')
T.insert(3,'Mary')
T.insert(2,'Anne')
T.insert(1,'Peter')
1
2
3
4
보다 나은 성능을 보이는 이진 탐색트리
높이의 균형을 유지함으로써 O(logn)의 탐색 복잡도 보장 삽입,
삭제 연산이 보다 복잡
참조 AVL trees, Red-black trees
'''
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:
# 만약 parent 가 있으면
if parent:
# node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
if parent.left==node:
# leaf node 였던 자식을 트리에서 끊어내어 없앱니다.
parent.left=None
else:
parent.right=None
# 만약 parent 가 없으면 (node 는 root 인 경우)
else:
# self.root 를 None 으로 하여 빈 트리로 만듭니다.
self.root=None
# 자식 한명일때
elif nChildren == 1:
# 하나 있는 자식이 왼쪽인지 오른쪽인지를 판단
if node.left:
child=node.left
else:
child=node.right
# 만약 parent 가 있으면
if parent:
# 위에서 가리킨 자식을 대신 node 의 자리에 넣습니다.
if parent.left==node:
parent.left=child
else:
parent.right=child
# 만약 parent 가 없으면 (node 는 root 인 경우)
# self.root 에 위에서 가리킨 자식을 대신 넣습니다.
else:
self.root=child
# 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 가 가지고 있던 (없을 수도 있지만) 자식을 가리키도록 합니다.
# successor 보다 작은건 이미 삭제됐으니 무조건 큰값(right)이다.
if parent.left==successor:
parent.left = successor.right
else:
parent.right = successor.right
return True
else:
return False
def inorder(self):
if self.root:
return self.root.inorder()
else:
return []
def solution(x):
return 0