학습목표
- 이진 트리 개념 파악
- 파이썬으로 이진 트리 구현 코드 작성
- 이진 트리 중 활용도가 높은 이진 탐색 트리 이해하고 활용
- 이진 탐색 트리를 활용하여 다양한 응용 프로그램 작성
Section00. 생활 속 자료구조와 알고리즘
회사 조직도-->트리 구조
컴퓨터의 폴더
Section01. 이진 트리의 기본
1. 이진 트리의 개념
-트리(Tree) 자료구조: 나무를 거꾸로 뒤집은 형태
-뿌리(Root, 루트): 트리의 맨 위
루트를 레벨 0으로 두고 나뭇잎에 해당하는 아래로 내려올수록 레벨이 1씩 증가함
-노드: 각 위치
각 노드는 선, 엣지(edge)로 연결되어 있음
-부모, 자식 관계: 위 노드와 바로 아래 노드의 관계
-차수(degree): 자식 노드 개수
-리프(leaf): 차수가 0인 노드
트리의 차수는 가장 높은 노드를 기준으로 정함
컴퓨터는 데이터를 0과 1로 표현하므로 트리 자료구조를 구현하려고 최대 차수가 2인 이진 트리(binary tree)를 사용
2. 이진 트리의 종류
🌴포화 이진 트리(full binary tree)
모든 노드가 꽉 차 있는 상태의 트리
노드 개수: 2^(높이+1) -1
루트 노드부터 왼쪽에서 오른쪽으로 번호를 부여
🌴완전 이진 트리(complete binary tree)
번호를 부여한 순서로 노드가 배치됨
노드가 일부 비어 있어도 되지만 끝 번호의 노드는 비어 있어야 함
🌴편향 이진 트리(skewed binary tree)
모든 노드가 왼쪽이나 오른쪽으로 연결된 트리
3. 이진 트리의 노드 구조
트리는 왼쪽 자식과 오른쪽 자식으로 구성됨
왼쪽과 오른쪽 링크가 있는 이중 연결 리스트 구조로 만들 수 있음
가리킬 곳이 없는 링크는 그냥 비워두면 됨
Section02. 이진 트리의 간단 구현
1. 이진 트리의 생성
높이가 2고 데이터가 6개인 완전 이진 트리 구현
①루트 노드를 생성
②두 번째 노드를 생성하고 루트 노드의 왼쪽 노드로 지정
③세 번째 노드를 생성하고 루트 노드의 오른쪽 노드로 지정
④네 번째부터 여섯 번째까지 노드를 생성하고 부모 노드와 연결
class TreeNode(): #이진 트리 노드 생성
def __init__ (self):
self.left=None
self.data=None
self.right=None
node1=TreeNode()
node1.data='화사'
node2=TreeNode()
node2.data='솔라'
node1.left=node2
node3=TreeNode()
node3.data='문별'
node1.right=node3
node4=TreeNode()
node4.data='휘인'
node2.left=node4
node5=TreeNode()
node5.data='쯔위'
node2.right=node5
node6=TreeNode()
node6.data='선미'
node3.left=node6
print(node1.data, end=' ')
print()
print(node1.left.data, node1.right.data, end=' ')
print()
print(node1.left.left.data, node1.left.right.data, node1.right.left.data, end=' ')
2. 이진 트리의 순회
🤎순회 종류
-순회(traversal): 이진 트리의 노드 전체를 한 번씩 방문하는 것
-자료구조로 데이터를 효율적으로 활용하는 대표적인 방법: 필요한 데이터를 효과적으로 검색하는 것
🌴전위 순회(preorder traversal)
노드의 데이터를 먼저 처리
①현재 노드 데이터 처리
②왼쪽 서브 트리로 이동
③오른쪽 서브 트리로 이동
🌴중위 순회(inorder traversal)
노드의 데이터를 중간에 처리
①왼쪽 서브 트리로 이동
②현재 노드 데이터 처리
③오른쪽 서브 트리로 이동
🌴후위 순회(postorder traversal)
노드의 데이터를 마지막에 처리
①왼쪽 서브 트리로 이동
②오른쪽 서브트리로 이동
③현재 노드 데이터 처리
🤎이진 트리 순회 구현
1) 스택 이용 방식
2) 재귀 함수 이용 방식 ✅
# 생략
def preorder(node):
if node==None:
return
print(node.data, end='->')
preorder(node.left)
preorder(node.right)
def inorder(node):
if node==None:
return
inorder(node.left)
print(node.data, end='->')
inorder(node.right)
def postorder(node):
if node==None:
return
postorder(node.left_
postorder(node.right)
print(node.data, end='->')
print('전위 순회: ', end=' ')
preorder(node1)
print('끝')
print('중위 순회: ', end=' ')
inorder(node1)
print('끝')
print('후위 순회: ', end=' ')
postorder(node1)
print('끝')
Section03. 이진 탐색 트리의 일반 구현
1. 이진 탐색 트리의 특징
데이터 크기를 기준으로 일정 형태로 구성함
①왼쪽 서브 트리는 루트 노드보다 모두 작은 값을 가짐
②오른쪽 서브 트리는 루트 노드보다 모두 큰 값을 가짐
③각 서브트리도 1, 2의 특징을 가짐
④모든 노드 값은 중복되지 않음. 중복된 값은 이진 탐색 트리에 저장할 수 없음
*이진 탐색 트리는 이진 트리의 일종이지만, 완전 이진 탐색 트리는 아님
2. 이진 탐색 트리의 완성
실제로 데이터 개수가 제한적이지 않을 수 있음
루트 노드만 root 변수로 사용하고, 나머지 노드는 별도의 변수 없이 무한대 메모리에 넣는 형태로 생성
그림에는 노드가 트리 구조로 가지런히 들어 있지만, 실제로는 노드의 위치나 순서는 상관없이 서로 링크로만 연결됨
먼저 메모리를 준비하고 root는 None으로 초기화
memory=[]
root=None배열에 있는 데이터를 차례대로 이진 탐색 트리에 삽입
nameAry=['블랙핑크', '레드벨벳', '에이핑크', '걸스데이', '트와이스', '마마무']먼저 배열의 첫 번째 데이터를 최상위 노드로 지정한 후 생성한 노드를 메모리에 저장한다.
node=TreeNode()
node.data=nameAry[0]
root=node
memory.append(node)두 번째 이후 데이터를 삽입할 때는 이진 탐색 트리의 특징을 고려해야 함
루트 노드보다 입력할 데이터가 작으면 왼쪽에 삽입하고, 크면 오른쪽에 삽입하도록 코드 작성
name='레드벨벳' #두 번째 데이터
node=TreeNode() #새 노드 생성
node.data=name #새 노드에 데이터 입력
current=root #현재 작업 노드를 루트 노드로 지정
if name<current.data: #입력할 값을 현재 작업 노드의 값과 비교
current.left=node #작으면 새 노드를 왼쪽 링크로 연결
else:
current.right=node #크면 새 노드를 오른쪽 링크로 연결
memory.append(node) #새 노드를 메모리에 저장이진 탐색 트리에서 데이터를 삽입하는 일반적인 형태:
삽입할 위치를 찾고자 루트부터 시작하여 왼쪽 및 오른쪽 링크가 비어 있지 않는 경우를 찾아야 함
반복적으로 자리를 찾아가는 과정
name=6 #위치를 찾을 새 데이터
node=TreeNode() #새 노드 생성
node.data=name
current=root #루트부터 시작
while True: #무한반복
if name<current.data:
if current.left==None:
current.left=node
break
current=current.left
else:
if current.right==None:
current.right=node
break
current=current.right
이진 탐색 트리의 삽입 작동
#함수 선언 부분
class treeNode():
def __init__ (self):
self.left=None
self.data=None
self.right=None
#전역변수 선언 부분
memory=[]
root=None
nameAry=['블랙핑크', '레드벨벳', '마마무', '에이핑크', '걸스데이', '트와이스']
#메인코드
node=TreeNode()
node.data=nameAry[0]
root=node
memory.append(node)
for name in nameAry[1:]:
node=TreeNode()
node.data=name
current=root
while True:
if name<current.data:
if current.left==None:
current.left=node
break
current=current.left
else:
if current.right==None:
current.right=node
break
current=current.right
memory.append(node)
print("이진 탐색 트리 구성 완료!")
3. 이진 탐색 트리에서 데이터 검색
#①
if 현재 작업 노드의 데이터==찾을 데이터:
탐색 종료
#②
elif 현재 작업 노드의 데이터<찾을 데이터:
왼쪽 서브 트리 탐색
#③
else:
오른쪽 서브 트리 탐색①찾고자 하는 데이터를 루트 노드의 데이터와 비교
작으면 왼쪽으로 이동, 크면 오른쪽으로 이동, 같으면 종료
②왼쪽 서브 트리에서도 동일하게 처리
③오른ㅉ고 서브 트리에서도 동일하게 처리
이진 탐색 트리의 검색 작동
#함수 선언 부분
#생략
findName='마마무'
current=root
while True:
if findName==current.data:
print(findName, '을(를) 찾음.')
break
elif findName<current.data:
if current.left==None:
print(findName, '이(가) 트리에 없음')
break
current=current.left
else:
if current.right==None:
print(findName, '이(가) 트리에 없음')
break
current=current.right
4. 이진 탐색 트리에서 데이터 삭제
🤎리프 노드(맨 아래쪽 노드)를 삭제하는 경우
부모 노드의 링크를 None으로 변경하고, 현재 작업 노드를 삭제하면 됨
(한 마디로 연결 끊고 현재 작업 노드 삭제)
현재 노드가 부모 노드의 왼쪽 링크인지, 오른쪽 링크인지 구분하고자 코드 형태로 구분하는 법↓
if parent.left==current: #부모 노드 왼쪽 링크와 삭제할 노드가 같으면
parent.left=None #부모 노드의 왼쪽에 None 대입
else: #부모 노드 오른쪽 링크와 삭제할 노드가 같으면
parent.right=None #부모 노드의 오른쪽에 None 대입
del(current) #노드 삭제
🤎자식 노드가 하나인 노드를 삭제하는 경우
삭제할 노드를 가리키는 부모 노드의 링크를 자식 노드로 먼저 변경한 후 해당 노드를 삭제
왼쪽 자식 노드가 있는 경우와 오른쪽 자식 노드가 있는 경우로 나누어서 생각하기
🌴왼쪽 자식 노드가 있는 경우
if parent.left==current: #부모 노드 왼쪽 링크와 삭제할 노드가 같으면
parent.left=current.left #부모 노드의 왼쪽 링크에 왼쪽 자식 노드 대입
else: #부모 노드 오른쪽 링크와 삭제할 노드가 같으면
parent.right=current.left #부모 노드의 오른쪽 링크에 왼쪽 자식 노드 대입
del(current)🌴오른쪽 자식 노드가 있는 경우
if parent.left==current: #부모 노드 왼쪽 링크와 삭제할 노드가 같으면
parent.left==current.right #부모 노드의 왼쪽 링크에 오른쪽 자식 노드 대입
else: #부모 노드 오른쪽 링크와 삭제할 노드가 같으면
parent.right=current.right #부모 노드의 오른쪽 링크에 오른쪽 자식 노드 대입
del(current)
🤎자식 노드가 둘 있는 노드를 삭제하는 경우
재귀를 사용해야 편리함
🤎이진 탐색 트리에서 데이터 삭제 완성
#함수 선언 부분
#생략
deleteName='마마무'
current=root
parent=None
while True:
if deleteName==current.data:
if current.left==None and current.right==None:
if parent.left==current:
parent.left=None
else:
parent.right=None
del(current)
elif current.left!=None and current.right==None:
if parent.left==current:
parent.left=current.left
else:
parent.right=current.left
del(current)
elif current.left==None and current.right!=None:
if parent.left==current:
parent.left=current.right
else:
parent.right=current.right
del(current)
print(deleteName, '이(가) 삭제됨.')
break
elif deleteName<current.data:
if current.left==None:
print(deleteName, '이(가) 트리에 없음')
break
parent=current
current=current.left
else:
if current.right==None:
print(deleteName, '이(가) 트리에 없음')
break
parent=current
current=current.right
Section04. 이진 탐색 트리의 응용
이진 탐색 트리는 데이터를 보관하고 검색할 때 효율적
순서대로 보관하기 때문에 검색에서도 효율성이 큼
<책 이름 이진 탐색 트리>
<작가 이름 이진 탐색 트리>
random.shuffle(배열): 배열 내용을 랜덤하게 섞음
import random
bookAry=[['어린왕자', '생택쥐베리'],['이방인','까뮈'],['부활','톨스토이'],['신곡','단테'],['돈키호테','세르반테스'],['동물농장','조지오웰'],['데미안','헤르만헤세'],['파우스트','괴테'],['대지','펄벅']]
bookAry=random.shuffle(bookAry)트리가 2개이므로 루트 노드를 저자알 변수도 2개 준비
rootBook, rootAuth, None, None책 이름 트리와 작가 이름 트리를 따로 구현
improt random
#함수 선언 부분
class TreeNode():
def __init__ (self):
self.left=None
self.data=None
self.right=None
#전역 변수 선언 부분
memory=[]
rootBook, rootAuth=None, None
bookAry=[['어린왕자', '생택쥐베리'],['이방인','까뮈'],['부활','톨스토이'],['신곡','단테'],['돈키호테','세르반테스'],['동물농장','조지오웰'],['데미안','헤르만헤세'],['파우스트','괴테'],['대지','펄벅']]
bookAry=random.shuffle(bookAry)
random.shuffle(bookAry)
#메인코드 부분
#책이름 트리
node=TreeNode()
node.data=bookAry[0][0]
rootBook=node
memory.append(node)
for book in bookAry[1:]:
name=book[0]
node=TreeNode()
node.data=name
current=rootBook
while True:
if name<current.data:
if current.left==None:
current.left=node
break
current=current.left
else:
if current.right==None:
current.right=node
break
current=current.right
memory.append(node)
print("책 이름 트리 구성 완료!")
#작가 이름 트리
node=TreeNode()
node.data=bookAry[0][1]
rootAuth=node
memory.append(node)
for book in bookAry[1:]:
name=book[1]
node=TreeNode()
node.data=name
current=rootAuth
while True:
if name<current.data:
if current.left==None:
current.left=node
break
current=current.left
else:
if current.right==None:
current.right=node
break
current=current.right
memory.append(node)
print("작가 이름 트리 구성 완료!")
#책 이름 및 작가 이름 검색
bookOrAuth=int(input('책검색(1), 작가검색(2)-->'))
findName=input('검색할 책 또ㅡㄴ 작가-->')
if bookOrAuth==1:
root=rootBook
else:
root=rootAuth
current=root
while True:
if findName==current.data:
print(findName, '을(를) 찾음')
findYN=True
break
elif findName<current.data:
if current.left==None:
print(findName, '이(가) 목록에 없음')
break
current=current.left
else:
if current.right==None:
print(findName, '이(가) 목록에 없음')
break
current=current.right
<연습문제>
1. 정답) 루트, 레벨, 노드, 에지
2. 정답)1, 2, 3
3. 정답)
편향 이진 트리 - 모든 노드가 오른쪽이나 왼쪽으로 연결된 트리
포화 이진 트리 - 모든 노드가 꽉 차 있는 상태의 트리
완전 이진 트리 - 번호 부여 순서로 노드가 배치됨. 노드가 일부 비어 있어도 됨
4. 정답)3
바른 말
-데이터와 링크 2개로 구성되어 있다
-링크는 왼쪽 링크와 오른쪽 링크 두 가지다
-보통 왼쪽 링크, 데이터, 오른쪽 링크의 순서로 구성함
틀린 말
-필요한 경우 링크를 3개 이상 구성할 수도 있다
5. 정답)
전위: 현재 노드 데이터 처리
중위: 왼쪽 서브 트리로 이동
후위: 오른쪽 서브 트리로 이동
6. 정답)
전위 순회 결과: 화사-솔라-휘인-쯔위-문별-선미
중위 순회: 휘인-솔라-쯔위-선미-문별-화사
후위 순회: 휘인-쯔위-솔라-선미-문별-화사
8. 정답)4
이진 탐색 트리의 삭제 동작 중에서 재귀 함수를 사용해야 하는 경우: 자식 노드가 둘 있는 노드를 삭제하는 경우
9. 정답)
name<current.data
current=current.left
current=current.right
10. 정답)
nameAry[1:]
'프로그래밍 > 자료구조' 카테고리의 다른 글
| [파이썬 자료구조와 알고리즘] Chapter 10. 재귀호출 (0) | 2022.08.19 |
|---|---|
| [파이썬 자료구조와 알고리즘] Chapter 09. 그래프 (0) | 2022.08.19 |
| [파이썬 자료구조와 알고리즘] Chapter 07. 큐 (0) | 2022.08.14 |
| [파이썬 자료구조와 알고리즘] Chapter 05. 원형 연결 리스트 (0) | 2022.08.05 |
| [파이썬 자료구조와 알고리즘] Chapter 04. 단순 연결 리스트 (0) | 2022.08.05 |