1:다 관계: 원소들 간의 계층이 존재한다. 하위 원소로 내려가면서 확장되는 구조
1. 트리 기본개념
가계도를 생각하면 된다. : 자식 부모 관계, 자손, 손자, 레벨, 단말 노드
루트노드
자손 노드
조상 노드: 간선으로 연결되어 있지 않으면 조상이 아니다. K, C의 관계
단말 노드
형제 노드
부모 노드
자식 노드
노드들은 간선으로 연결되어 있다.
서브 트리: 노드 하나만 있어도 트리라고 한다.
차수
차수: 노드에 연결된 간선의 개수 = 나랑 연결된 선
트리의 차수: 트리에 있는 노드의 차수들 중에서 가장 큰 값
높이
노드의 높이: 루트에서부터 노드까지 이어진 간선의 개수
트리의 높이: 트리에 있는 노드의 높이들 중에서 가장 큰 값
포리스트(forest) : 서브트리들의 집합
2. 이진 트리
이진트리: 1대2 관계, 왼쪽 자식 노드 / 오른쪽 자식 노드 / 공백 노드 를 자식으로 여긴다.
둘 다 공백 노드 = 단말 노드
계속 잘라도 트리이므로 순환적 구성을 가진다.
1. 특성
n개의 노드 + (n-1)개의 간선 , 왜냐하면 루트는 간선이 없으니까
노드의 최소 개수는 (h+1)
노드의 최대 개수는 2^(h+1) -1 = ∑2^i 개
2. 종류
1) 포화 이진 트리 : 공백 노드 없이 가득 찬 이진 트리, 완전 이진 트리를 포함한다.
위에서 아래로, 왼에서 오른쪽으로 순서를 매긴다.
높이에 맞게 모든 노드가 가득찬 트리(최대 개수)
2) 완전 이진 트리 : 특정 노드까지 번호대로 갔을 때 공백 노드가 없는 이진 트리
3) 편향 이진 트리 : 한 쪽 방향으로만 자식 노드를 갖는 이진 트리로 왼쪽/오른쪽 편향 이진 트리가 존재한다.
3. 표현
1차원 배열의 순차 자료구조를 이용한다.
높이가 h인 포화 이진 트리의 노드 번호를 배열의 인덱스를 사용한다.
인덱스 0번은 비워두고 인덱스 1번부터 시작한다.
완전 이진트리를 리스트로 표현하기
0 인덱스를 비워놨다.
편향 이진트리를 리스트로 표현하게 되면 공백 노드가 많아 즉, 안 쓰는 빈공간이 많아서 비효율적이다.
따라서 이러한 한계를 극복하고자
링크 필드를 두 개를 갖는 노드로 구현한다.
계층적 연결구조라는 점에서 이중 연결리스트와는 다르다.
class Node:
def __init__(self,item,left=None, right=None):
self.item = item
self.left = left
self.right = right
class BinaryTree:
def __init__(self):
self.root =None
def preorder(self,n):
if n!=None:
print(str(n.item),'',end='')
if n.left:
self.preorder(n.left)
if n.right:
self.preorder(n.right)
def inorder(self,n):
if n!=None:
if n.left:
self.inorder(n.left)
print(str(n.item),'',end='')
if n.right:
self.inorder(n.right)
def postorder(self,n):
if n!=None:
if n.left:
self.postorder(n.left)
if n.right:
self.postorder(n.right)
print(str(n.item),'',end='')
def levelorder(self, root):
queue = []
queue.append(root)
while queue:
node = queue.pop(0)
print(str(node.item),'',end="")
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
def height(self,root):
if root == None:
return 0
return max(self.height(root.left),self.height(root.right)) +1
t = BinaryTree()
n1 = Node(100)
n2 = Node(200)
n3 = Node(300)
n4 = Node(400)
n5 = Node(500)
n6 = Node(600)
#n7 = Node(700)
#n8 = Node(800)
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
n3.left = n6
#n3.right = n7
#n4.left = n8
t.root = n1
print('\n전위순회:\t', end ="")
t.preorder(t.root)
print('\n중위순회:\t', end ="")
t.inorder(t.root)
print('\n후위순회:\t', end ="")
t.postorder(t.root)
print('\n레벨순회:\t', end ="")
t.levelorder(t.root)
print('트리높이=', t.height(t.root))
메모리가 중요하다면 연결 리스트로 구현하는 것이 더 좋다.
메모리 상관없다면 순차 자료 구조가 더 효율이 좋다.
4. 트리 순회
1) D: 데이터를 읽는다.
2) L: 왼쪽 서브트리로 이동
3) R: 오른쪽 서브트리로 이동
세 가지 모두 노드 기준으로 진행한다.
반드시 왼쪽 서브 트리에서 오른쪽 서브 트리 순회로 이어진다.
노드 기준으로 서칭/ 왼쪽 / 오른쪽 순서를 고려하여 순회한다. 루
순회의 시작은 루트에서부터 한다.
전위 순회: 서칭 - 왼쪽 - 오른쪽
중위 순회: 왼쪽 - 서칭 - 오른쪽
A(중간에 있음)를 기준으로 왼쪽 서브 트리가 먼저 나온다.
가장 왼쪽 끝단에 있는 노드를 가장 먼저, 가장 오른쪽 끝단에 있는 노드를 가장 나중에 서칭한다.
따라서 서브 트리를 정렬하는 데 쓰는 중요한 순회이다.
후위 순회: 왼쪽 - 오른쪽 - 서칭
가장 높은 레벨의 노드부터 서칭한다. 하위단부터 서칭한다.
cf) 각 순회법 따라 컴퓨터의 연산의 순서가 달라진다.
순회법을 이용하여 스택 큐를 구현한다?
3. 이진탐색트리
1. 이진 탐색일 조건
1) 모든 원소는 유일하다. 같은 키 값이 존재하지 않는다.
2) 왼쪽 서브트리에 있는 원소들의 키는 그 루트의 키보다 작고
오른쪽 서브트리에 있는 원소들의 키는 그 루트의 키보다 크다.
즉, 왼쪽 끝단에는 최솟값이 오른쪽 끝단에는 최댓값을 갖는다. 루트는 중간값을 갖는다.
따라서 중위 순회 하는 것만으로도 오른차순 정렬이 된다.
이진탐색 만들고 중위 순회를 하면 만들어진다.
2. 연산
루트 노드의 값과 비교해서 루트 노드의 키값보다 크면 오른쪽, 작으면 왼쪽으로 간다.
이렇게 내려간 하단 트리들도 마찬가지로 대소비교하여 내려간다.
1) 삽입 연산
넣으려는 삽입 데이터가 탐색 노드가 그 자리에 있는지 확인
탐색에 실패하면(같은 노드가 없다면) 해당 노드 자리에 삽입하려는 노드를 삽입한다.
2) 삭제 연산
삭제할 노드의 차수에 따라 3가지로 나뉘어진다.
해당 노드와 가장 가까운 노드로 결정한다.
(1) 0차수
(2) 1차수
(3) 2차수 : 즉 자식이 둘 일 때, 다음 두 가지 경우로 후계자를 선택한다.
(1) 왼쪽 서브트리에서 가장 큰 자손 노드를 선택한다. 가장 오른쪽 끝단
(2) 오른쪽 서브트리에서 가장 작은 자손 노드를 선택한다. 가장 왼쪽 끝단
또한 후계자가 자식이 있는 경우(자식은 무조건 하나밖에 없다) 자식에게 후계자자리를 물려주고 간다.
이진 탐색 트리 예제1
class Node:
def __init__(self,key,value, left=None, right=None):
self.key = key
self.value = value
self.left = left
self.right = right
class BST:
def __init__(self): # 트리 생성자
self.root = None
def get(self,k): # 탐색 연산
result = self.get_item(self.root,k)
return result
def get_item(self,n,k):
if n== None:
return
if n.key == k:
return n.value
elif n.key > k:
value = self.get_item(n.left,k)
elif n.key < k:
value = self.get_item(n.right,k)
return value
def put(self, key, value): # 삽입 연산)
self.root = self.put_item(self.root,key,value)
def put_item(self,n,key, value):
if n == None:
n = Node(key,value,left=None,right=None)
elif n.key > key:
n.left = self.put_item(n.left,key,value)
elif n.key < key:
n.right = self.put_item(n.right,key,value)
elif n.key == key:
n.value = value
return n
# 책의 내용 따라가 보면
def minn(self): # 최솟값 가진 노드 찾기.
if self.root == None:
return None
return self.minimum(self.root)
def minimum(self,n):
if n.left == None:
return n
return self.minimum(n.left)
# 책보고 다시 해봄.
def delete_min(self): # 최솟값 삭제
if self.root == None:
return None
self.root = self.del_min(self.root)
def del_min(self, n):
if n.left == None:
return n.right
else:
n.left = self.del_min(n.left)
return n
# 책보고 다시 해봄.
def delete(self,k): # 삭제 연산
self.root = self.del_node(self.root,k)
def del_node(self,n,k):
if n == None:
return None
if n.key == k:
if n.left == None:
return n.right
if n.right == None:
return n.left
target = n
n = self.minimum(target.right) #중위순회 다음타자.
n.right = self.del_min(target.right)
n.left = target.left
elif n.key > k:
n.left = self.del_node(n.left,k)
elif n.key < k:
n.right = self.del_node(n.right,k)
return n
# 전위순회
def pre_order(self,n):
if n == None:
return
print(n.key," ", end="")
self.pre_order(n.left)
self.pre_order(n.right)
# 중위순회
def inorder(self,n):
if n == None:
return
self.inorder(n.left)
print(n.key," ",end="")
self.inorder(n.right)
bts = BST()
bts.put(500,'apple')
bts.put(600,'banana')
bts.put(200,'melon')
bts.put(100,'orange')
bts.put(400,'lime')
bts.put(250,'kiwi')
bts.put(150,'grape')
bts.put(800,'peach')
bts.put(700,'cherry')
bts.put(50,'pear')
print(bts.get(700))
bts.put(350,'lemon')
bts.put(10,'plum')
print('전위순회 \t',"", end="")
bts.pre_order(bts.root)
print(' ')
print('중위순회 \t',"", end="")
bts.inorder(bts.root)
result = bts.get(400)
print('\n', '탐색연산 key: 400, result: ', result)
result2 = bts.minn()
print('\n 최솟값: ', result2.key)
bts.delete_min()
print('\n 최솟값 삭제연산 ', end ="")
bts.inorder(bts.root)
bts.delete(200)
print('\n삭제 연산 1 : ', end ="")
bts.inorder(bts.root)
bts.delete(700)
print('\n삭제 연산 2 : ', end ="")
bts.inorder(bts.root)
bts.delete(50)
print('\n삭제 연산 3 : ', end ="")
bts.inorder(bts.root)
이진 탐색 트리 예제2
class Node(object):
def __init__(self, data):
self.data = data
self.left = self.right = None
class BinarySearchTree(object):
def __init__(self):
self.root = None
def insert(self, data):
self.root = self._insert_value(self.root, data)
return self.root is not None
def _insert_value(self, node, data):
if node is None:
node = Node(data)
else:
if data <= node.data:
node.left = self._insert_value(node.left, data)
else:
node.right = self._insert_value(node.right, data)
return node
def find(self, key):
return self._find_value(self.root, key)
def _find_value(self, root, key):
if root is None or root.data == key:
return root is not None
elif key < root.data:
return self._find_value(root.left, key)
else:
return self._find_value(root.right, key)
def delete(self, key):
self.root, deleted = self._delete_value(self.root, key)
return deleted
def _delete_value(self, node, key):
if node is None:
return node, False
deleted = False
if key == node.data:
deleted = True
if node.left and node.right:
parent, child = node, node.right
while child.left is not None:
parent, child = child, child.left
child.left = node.left
if parent != node:
parent.left = child.right
child.right = node.right
node = child
elif node.left or node.right:
node = node.left or node.right
else:
node = None
elif key < node.data:
node.left, deleted = self._delete_value(node.left, key)
else:
node.right,dleted = self._delete_value(node.right, key)
return node, deleted
array = [40, 4, 34, 45, 14, 55, 48, 13, 15, 49, 47,40]
bst = BinarySearchTree()
for x in array:
bst.insert(x)
print(bst)
# Find
print(bst.find(15)) # True
print(bst.find(17)) # False
# Delete
print(bst.delete(55)) # True
print(bst.delete(14)) # True
print(bst.delete(11)) # False
print(bst.delete(55))힙(heap)
1. 힙에는 아래 두 가지만 존재한다.
최대 힙: 부모 ≥ 자식, 루트가 최댓값
최소 힙: 부모 ≤ 자식, 루트가 최솟값
2. 힙과 이진 트리와 차이
힙은 넣어다가 빼는 도구이기 때문에 구조를 계속 유지할 필요가 없다. 따라서 바로 쓰고 버릴 수 있기 때문에 순차 자료구조로 만든다.
하지만 순차 자료구조는 공백이 생기면 메모리 공간이 생기므로 힙에서는 완전 이진 트리라는 규칙을 더한다.
3. 연산
1) 삽입 연산
완전 이진 트리를 유지하기 위해 맨 마지막 순서의 다음 순서 노드에 추가한다.
부모와 대소비교하여 자리를 이동한다. (형제관계는 신경 쓸 필요 없다.)
2) 삭제 연산
반드시 루트에서만 삭제가 진행된다.
내림차순이나 오림차순으로 제거된다.
'Computer Science > Algorithm' 카테고리의 다른 글
| [파이썬] DAY11 트리 코드 리뷰 (0) | 2022.01.28 |
|---|---|
| [파이썬] DAY11 그래프 복습 & 정렬 (0) | 2022.01.28 |
| [파이썬] DAY10 그래프 (0) | 2022.01.27 |
| [파이썬] DAY10 스택&큐 (0) | 2022.01.27 |
| [파이썬] DAY10 리스트 복습 (0) | 2022.01.27 |