Jeff's Inovation Lab Jeff's Inovation Lab

목차 Heap의 삽입 Heap의 삭제 1.Heap의 삽입 힙은 완전 이진 트리이므로, 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워지는 형태로 삽입 삽입할 데이터가 힙의 데이터보다 클 경우 (Max Heap의 예) 먼저 삽입된 데이터는 완전 이진 트리 구조에 맞추어, 최하단부 왼쪽 노드부터 채워짐 채워진 노드 위치에서, 부모 노드보다 값이 클 경우, 부모 노드와 위치를 바꿔주는 작업을 반복함 (swap) 2.Heap의 삭제(Max Heap) 보통 삭제는 최상단 노드 (root 노드)를 삭제하는 것이 일반적임 힙의 용도는 최대값 또는 최소값을 root 노드에 놓아서, 최대값과 최소값을 바로 꺼내 쓸 수 있도록 하는 것임 상단의 데이터 삭제시, 가장 최하단부 왼쪽에 위치한 노드 (일반적으로 가장 마지..

목차 Heap 구조 BST와 공통점 및 차이점 1.Heap 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 힙을 사용하는 이유 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n) 이 걸림 이에 반해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으면, O(logn) 이 걸림 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨 2.Heap의 구조 힙은 최대값을 구하기 위한 구조 (최대 힙, Max Heap) 와, 최소값을 구하기 위한 구조 (최소 힙, Min Heap) 로 분류할 수 있음 힙은 다음과 같이 두 가지 ..

목차 BST 시간 복잡도(최악의 경우 1.BST의 시간복잡도(최악의 경우) 평균 시간 복잡도는 O(logn) 이지만, 이는 트리가 균형잡혀 있을 때의 평균 시간복잡도이며, 다음 예와 같이 구성되어 있을 경우, 최악의 경우는 링크드 리스트등과 동일한 성능을 보여줌 ( O(n) ) 이때 이런 구성을 피하기 위해 재정렬 하는 알고리즘들도 존재한다. https://bit.ly/37BpXiC

목차 BST 시간 복잡도 1.BST의 시간복잡도 depth (트리의 높이) 를 h라고 표기한다면, O(h) n개의 노드를 가진다면, h=log2n 에 가까우므로, 시간 복잡도는 O(logn) 참고: 빅오 표기법에서 logn 에서의 log의 밑은 10이 아니라, 2입니다. 한번 실행시마다, 50%의 실행할 수도 있는 명령을 제거한다는 의미. 즉 50%의 실행시간을 단축시킬 수 있다는 것을 의미함 https://bit.ly/37BpXiC

목차 BST의 삭제(2-Child Node) 구현 1.BST의 삭제 코드 Child가 1개인 Node 삭제 self.change_node = self.current_node.right self.change_node_parent = self.current_node.right while self.change_node.left != None: self.change_node_parent = self.change_node self.change_node = self.change_node.left if self.change_node.right != None: self.change_node_parent.left = self.change_node.right else: self.change_node_parent.left ..

목차 BST의 삭제(Leaf Node,1-Child Node) 구현 1.BST의 삭제 코드 Search # def delete(self, value): searched = False self.current_node = 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_node.left else: self.parent = self.current_node self.cu..

목차 BST의 삭제 1.BST의 삭제 Leaf Node 삭제 Leaf Node: Child Node 가 없는 Node 삭제할 Node의 Parent Node가 삭제할 Node를 가리키지 않도록 한다. Child가 1개인 Node 삭제 삭제할 Node의 Parent Node가 삭제할 Node의 Child Node를 가리키도록 한다. Child가 2개인 Node 삭제 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다. 삭제할 Node의 오른쪽 자식 선택 오른쪽 자식의 가장 왼쪽에 있는 Node를 선택 해당 Node를 삭제할 Node의 Parent Node의 왼쪽 Branch가 가리키게 함 해당 Node의 왼쪽 Branch가 삭제할 Node의 왼쪽 C..

목차 BST와 정렬된 배열간의 탐색 비교 간단한 구현(Node,Insert) 1.BST와 정렬된 배열간의 탐색비교 2.간단한 구현(Node,Insert) class Node: def __init__(self, value): self.value = value self.left = None self.right = None class Simple_BST: def __init__(self,head): self.head=head def insert(self,value): self.current_node=self.head while True: if value