Finn의 개발블로그
7. 트리 본문
1. 트리
- 비선형 자료구조
- 계층적 관계를 나타내기 위한 자료구조
2. 트리의 구성 요소
- Node
- 트리를 구성하는 각각의 요소
- Edge
- 노드와 노드를 연결하는 선
- Root Node
- 트리의 최상위 노드
- Leaf Node
- 하위에 다른 노드가 연결되어 있지 않은 노드
- Internal Node
- leaf node를 제외한 모든 노드
3. 이진 트리
- 루트 노드를 중심으로 두 개의 서브 트리로 나누어 진다
- 서브 트리도 모두 이진 트리여야 한다
- 각 층별로 레벨을 정하고, root node의 레벨은 0 또는 1, 최고 레벨을 height(높이) 라고 한다
- Full Binary Tree(포화 이진 트리)
- 단말 노드를 제외한 모든 노드가 2개의 자식을 갖는 트리
- 노드의 개수는 2^n - 1
- Complete Binary Tree(완전 이진 트리)
- 위쪽 에서 아래로, 왼쪽에서 오른쪽으로 차곡차곡 채워진 이진트리
3. 이진 탐색 트리
- 이진탐색과 연결리스트를 결한한 자료구조
- 이진탐색의 효율적인 탐색 능력을 유지하면서, 빈번한 자료 입력과 삭제를 가능하게끔 고안
- 이진 탐색 트리의 규칙
- 이진 탐색 트리의 노드에 저장되는 키는 유일하다
- 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다
- 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다.
- 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.
- 탐색 연산은 Big-O(log n)
- 이진 탐색 트리는 저장 순서에 따라 계속 한 쪽으로만 노드가 추가되는 경우가 발생
- 배열보다 많은 메모리를 사용하며 데이터를 저장했지만 시간 복잡도가 같아짐
- 이러한 문제를 해결하기 위한 트리로는 AVL, Red Black, 2-3, 2-4, 트리가 있다.
3-1. 이진 탐색 트리 ADT
- init(self)
- 트리를 초기화 한다
- insert(self, data)
- 트리에 데이터를 저장한다
- insert_node(self, node, data)
- 트리에 데이터를 저장하기 위한 재귀 함수이다
- delete(self, data)
- 트리에서 데이터를 삭제한다
- delete_node(self, node, data)
- 트리에서 데이터를 삭제하기 위한 재귀 함수이다
- find(self, data)
- 트리에서 데이터를 탐색
- find_node(self, node, data)
- 트리에서 데이터를 탐색하기 위한 재귀 함수이다.
- pre_order(self, node, data)
- 전위 순회 함수
-
- 부모노드 방문 -> 왼쪽 서버트리 -> 오른쪽 서브트리
- 전위 순회 결과 : E -> B -> A -> D -> C -> G -> F -> H
- pre_order_recursion(self, node, data)
- 전위 순회 재귀함수
- in_order(self, node, data)
- 중위 순회 함수
-
- 왼쪽 서브트리에서 왼쪽 에서 오른쪽 노드로 방문 ->루트 노드 방문->오른쪽 서브트리 제일 왼쪽 에서 오른쪽 노드로 방문
- 중위 순회 결과: A -> B -> C -> D -> E -> F -> G -> H
- in_order_recursion(self, node, data)
- 중위 순회 재귀 함수이다.
- post_order(self, node, data)
- 후위 순회 함수
-
- 왼쪽노드 -> 오른쪽 노드 -> 부모노드
- 후위 순회 결과 -> A -> C -> D -> B -> F -> H -> G -> E
- post_order_recursion(self, node, data)
- 후위 순회 재귀 함수
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root_node = None
self.is_root = False
self.total = 0
def insert(self, data):
if not self.root_node:
self.root_node = Node(data)
return self.root_node.data
else:
node = self.insert_node(self.root_node, data)
return node.data
def insert_node(self, node, data):
if not node:
return Node(data)
if node.data > data:
node.left = self.insert_node(node.left, data)
else:
node.right = self.insert_node(node.right, data)
return node
def delete(self, data):
delete_node, is_delete = self.delete_node(self.root_node, data)
return is_delete
def delete_node(self, node, data):
if not node:
return node, False
is_delete = False
if node.data == data:
is_delete = True
if node == self.root_node:
self.is_root = True
if node.left and node.right:
parent, child = node, node.right
while child.left:
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.righ
else:
node = None
elif node.data > data:
node.left, is_delete = self.delete_node(node.left, data)
else:
node.right, is_delete = self.delete_node(node.right, data)
if self.is_root:
self.root_node = node
return node, is_delete
def find(self, data):
search_result = self.find_node(self.root_node, data)
return search_result
def find_node(self, node, data):
if not self.root_node or not node:
return False
if node.data == data:
return True
elif node.data > data:
result = self.find_node(node.left, data)
else:
result = self.find_node(node.right, data)
return result
def pre_order(self):
self.pre_order_recursion(self.root_node)
def pre_order_recursion(self, node):
if not node:
return
print(node.data)
self.pre_order_recursion(node.left)
self.pre_order_recursion(node.right)
def in_order(self):
self.in_order_recursion(self.root_node)
def in_order_recursion(self, node):
if not node:
return
self.in_order_recursion(node.left)
print(node.data)
self.in_order_recursion(node.right)
def post_order(self):
self.post_order_recursion(self.root_node)
def post_order_recursion(self, node):
if not node:
return
self.post_order_recursion(node.left)
self.post_order_recursion(node.right)
print(node.data)
bst = BinarySearchTree()
bst.insert(5)
bst.insert(2)
bst.insert(1)
bst.insert(4)
bst.insert(3)
bst.insert(7)
bst.insert(6)
bst.insert(8)
print(f'pre_order')
bst.pre_order()
print(f'in_order')
bst.in_order()
print(f'post_order')
bst.post_order()
print(f'find 8 : {bst.find(8)}')
print(f'delete 8 : {bst.delete(8)}')
print(f'find 8 : {bst.find(8)}')
---------------------------------------------------
pre_order
5
2
1
4
3
7
6
8
in_order
1
2
3
4
5
6
7
8
post_order
1
3
4
2
6
8
7
5
find 8 : True
delete 8 : True
find 8 : False
'자료구조' 카테고리의 다른 글
9. 레드 블랙 트리 (0) | 2018.11.25 |
---|---|
8. 힙 (0) | 2018.11.13 |
6. 큐 (0) | 2018.11.07 |
5. 스택 (0) | 2018.11.06 |
4.리스트(연결 리스트) (0) | 2018.11.04 |