1. 트리
트리는 그림으로 보는 것이 이해가 빠르다.
보시다시피 가장 위에서 시작해 마치 뒤집어놓은 나무처럼 뻗어나는 것이 트리 구조다.
가장 위를 루트, 특정 노드의 기준으로 자신과 연결된 위쪽 노드를 부모노드, 아래를 자식노드라고 한다.
아래로 내려갈 수록 레벨이 0에서 시작해 1씩 증가한다.
가장 끝에 위치하여 자식이 없는 노드를 리프노드라고 한다.
2. 이진트리
이진 트리란 자식이 2개 이하만 존재하는 트리를 이진트리라 한다.
이 중 리프를 제외한 모든 노드가 자식이 2개씩 존재할 경우, 포화 이진트리라고 한다.
노드의 번호는 최상단이 1로 시작해 왼쪽부터 순차적으로, 위 사진의 오른쪽 처럼 번호를 부여한다.
일반 이진트리는 위 사진의 6번 처럼 빈 공간이 있을 수도 있다.
3. 트리의 순회
트리내의 정보를 찾을 때는 트리를 순회해야 한다.
트리의 정보를 순회할 때는 전위순회(preorder), 중위순회(inorder), 후위순회(postorder) 방법이 있다.
위와 같은 트리가 있다고 가정해보자
전위 순회(preorder)를 하면 루트인 화사부터 시작해 루트기준으로 왼쪽부터 다 훑어보는 방법이다.
순서는 아래와 같다.
화사 -> 솔라 -> 휘인 -> 쯔위 -> 문별 -> 선미
중위 순회(inorder)는 트리를 기준으로 왼쪽부터 시작해서 오른쪽으로 차근차근 순회하는 방법이다.
순서는 아래와 같다.
휘인 -> 솔라 -> 쯔위 -> 화사 -> 선미 -> 문별
후위 순회(postorder)은 왼쪽 자식 끝부분부터 시작해 같은 래밸의 같은 부모를 둔 노드를 순회한 다음 그 부모를 순회하는 방법이다.
순서는 아래와 같다.
휘인 -> 쯔위 -> 솔라 -> 선미 -> 문별 -> 화사
4. 이진탐색
이진탐색은 이진 트리에서 가장 활용도가 높은 것으로 데이터 크기를 기준으로 일정 형태로 구성한다.
이진 탐색은 탐색 시간을 크게 줄일 수 있는 장점이 있다.
예를 들어, 10억개의 데이터가 있고 여기서 하나의 데이터를 찾는다고 가정해보자
그럼 일단 5억번째 데이터를 확인하고 찾고자 하는 데이터와 크기를 비교한다.
5억번째 데이터보다 크기가 작다면 2억5천만번째 데이터를 확인한다.
역시 작다면 1억 2천5백만번째 데이터를 확인한다.
역시 작다면 6천2백5십만번째 데이터를 확인한다.
역시 작다면 3천125만번째 데이터를 확인한다.
이런식으로 계속 반으로 줄여나간다.
때문에 이진 탐색방법을 사용하면 10억개의 데이터 기준 약 30번의 탐색만으로도 찾아낼 수 있다.
참고로 1000경의 데이터가 있을 경우 약 63번의 탐색만으로도 찾아낼 수 있다.
5. 구현
5-1. 트리
위에 예시로 나온 이진트리를 구현해보자
class TreeNode: # 트리노드
def __init__(self) -> None:
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이제 각 노드를 정의해주자
node1이 루트이며 그 밑으로는 각각의 노드가 어디의 노드인지를 나타낸다.
print(' ',node1.data)
print(' ┌──────┴──────┐ ')
print(' ',node1.left.data, ' ', node1.right.data)
print('┌───┴───┐ ┌───┴───┐')
print(node1.left.left.data, '', node1.left.right.data, ' ',
node1.right.left.data, '')자료구조가 완성되었다면 보기좋게 출력해보자
출력결과는 아래와 같다.
(주석처리하면 모양이 기울어져서 따로 작성)
화사
┌──────┴──────┐
솔라 문별
┌───┴───┐ ┌───┴───┐
휘인 쯔위 선미
5-2. 트리 순회
선술한 전위순회, 중위순회, 후위순회를 해보자
트리는 바로 위에서 구현한 것을 사용한다.
def preorder(node):
if node == None: return
print(node.data, end = ' -> ')
preorder(node.left)
preorder(node.right)
preorder(node1)
# 실행결과
# 화사 -> 솔라 -> 휘인 -> 쯔위 -> 문별 -> 선미 ->재귀호출을 사용하면 쉽게 구현할 수 있다.
나머지 중위순회나 후위순회는 위 코드의 순서를 바꿔주는 형태로 구현해 줄 수 있다.
def inorder(node):
if node == None: return
inorder(node.left) # 재귀호출(Recursive Call)
print(node.data, end = ' -> ')
inorder(node.right) # 재귀호출(Recursive Call)
inorder(node1)
# 실행결과
# 휘인 -> 솔라 -> 쯔위 -> 화사 -> 선미 -> 문별 ->중위 순회 코드
def postorder(node):
if node == None: return
postorder(node.left)
postorder(node.right)
print(node.data, end =' -> ')
postorder(node1)
# 실행 결과
# 휘인 -> 쯔위 -> 솔라 -> 선미 -> 문별 -> 화사 ->후위순회 코드다.
5-3. 이진탐색
이번엔 새로운 트리를 만들고 이진탐색을 구현해보자
트리는 이렇게 구성한다.
루트에서 시작하여 주어진 값을 비교하여 왼쪽으로 갈지, 오른쪽으로 갈지를 정한다.
이 과정을 계속 반복하여, 원하는 값을 찾아나간다.
if __name__ == '__main__':
search = input('찾을 걸그룹을 입력 > ')
current = root
while True:
if search == current.data:
print(search, '찾음 끝!')
break
elif search < current.data: # 왼쪽 노드로
if current.left == None:
print(search, '못찹음 끝!')
break
else:
current = current.left
else: # 오른쪽 노드로
if current.right == None:
print(search, '못찹음 끝!')
break
else:
current = current.right
트리구현을 포함한 전체코드는 아래와 같다.
# 이진 탐색 트리
# 전역변수 선언
memory = []
root = None
nameAry = ['블랙핑크', '레드벨벳', '마마무', '에이핑크', '걸스데이', '트와이스']
class TreeNode:
def __init__(self) -> None:
self.left = None
self.data = None
self.right = None
if __name__ == '__main__':
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(current)
print('이진 탐색 트리 구성 완료')
print(' ',root.data)
print(' ┌──────────┴──────────┐ ')
print(' ',root.left.data, ' ', root.right.data)
print(' ┌─────┴─────┐ ┌─────┴─────┐')
print(root.left.left.data, ' ', root.left.right.data, ' ',
root.right.right.data, '')
#print(root.left.left.left.data)
search = input('찾을 걸그룹을 입력 > ')
current = root
while True:
if search == current.data:
print(search, '찾음 끝!')
break
elif search < current.data: # 왼쪽 노드로
if current.left == None:
print(search, '못찹음 끝!')
break
else:
current = current.left
else: # 오른쪽 노드로
if current.right == None:
print(search, '못찹음 끝!')
break
else:
current = current.right
'Algorithm > 자료구조' 카테고리의 다른 글
| 자료구조 - 선형자료구조 - 큐 (0) | 2023.02.24 |
|---|---|
| 자료구조 - 선형자료구조 - 스택 (0) | 2023.02.15 |
| 자료구조 - 선형자료구조 - 단순연결리스트 (0) | 2023.02.15 |
| 자료구조 - 선형자료구조 - 선형리스트 (0) | 2023.02.15 |
| 자료구조 (0) | 2023.02.15 |
