대표적인 데이터 구조8: 힙 1.힙이란 -->데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 1.1 완전 이진 트리 -노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 -힙을 사용하는 이유 배열에 데이터를 넣고 최대값과 최소값을 찾으려면 O(n)이 걸림 이에 반해 힙에 데이터를 넣고 최대값과 최소값을 찾으면 O(logn)이 걸림 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용 2.힙 구조 -->힙은 최대값을 구하기 위한 구조(=최대 힙) 와 최소값을 구하기 위한 구조(=최소힙) -->힙은 두가지 조건을 갖고 있는 자료구조 - 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다(최대 힙 경우) 최소 힙의 경우..

5.5.5 파이썬 전체 코드 구현 class Node: def __init__(self, value): self.value = value self.left = None self.right = None class NodeMgmt: def __init__(self, head): self.head = head def insert(self, value): self.current_node = self.head while True: if value < self.current_node.value: if self.current_node.left != None: self.current_node = self.current_node.left else: self.current_node.left = Node(value) bre..

5.5 이진 탐색 트리 삭제 코드 구현과 분석 5.5.1 삭제할 Node 탐색 삭제할 Node가 없는 경우도 처리해야함 - 이를 위해 삭제할 Node가 없는 경우는 False를 리턴하고 함수를 종료 시킴 #def delete(self, value): searched = False self.current_mode = self.head self.parent =self.head while self.current_node: if self.current_node.value == value: searched = True break elif value < self.current_node.value: self.parent = self.current_node self.current_node = self.current_n..

5.3 이진트리 탐색 class NodeMgmt: def __init__(self, head): self.head = head def insert(self, value): self.current_node = self.head while True: if value < self.current_node.value: if self.current_node.left != None: self.current_node = self.current_node.left else: self.current_node.left = Node(value) break else: if self.current_node.right != None: self.current_node = self.current_node.right else: self...

대표적인 데이터 구조7 : 트리 1. 트리 구조 A. 트리: NODE와 BRANCH를 이용해 사이클을 이루지 않도록 구성한 데이터 구조 B. 실제로 어디에 많이 사용되는가 트리 중 이진 트리 형태 구조 & 탐색 알고리즘 구현을 위해 많이 사용됨 2. 알아야 하는 용어 A. NODE: 트리에서 데이터를 저장하는 기본요소 B. ROOT NODE: 트리 맨 위에 있는 노드 C. LEVEL: 최상위 노드를 LEVEL 0으로 했을 때 하위 BRANCH로 연결된 노드의 깊이 D. PARENT NODE: 어떤 노드의 다음 레벨에 연결된 노드 E. CHILD NODE: 어떤 노드의 상위 레벨에 연결된 노드 F. LEAF NODE ( TERMINAL NODE) : CHILD NODE가 하나도 없는 노드 G. SILBLI..

6.2 Linear Probing 기법 -> 폐쇄 해슁 또는 Close Hashing 기법 중 하나: 해쉬 테이블 저장공간 안에서 충돌 문제를 해결 -> 충돌이 일어나면 해당 hash address의 다음 address부터 맨 처음 나오는 빈공간에 저장 - 저장공간 활용도를 높이기 위한 기법 연습3: 연습1의 해쉬 테이블 코드에 Linear Probling 기법으로 충돌해결 코드를 추가 hash_table = list([0 for i in range(8)]) def get_key(data): return hash(data) def hash_function(key): return key % 8 def save_data(data, value): index_key = get_key(data) hash_addr..