Jeff's Inovation Lab Jeff's Inovation Lab

목차 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

목차 Tree 구조 Tree의 종류 1.Tree 구조 트리: Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 실제로 어디에 많이 사용되나? 트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨 2.Tree의 종류 이진 트리: 노드의 최대 Branch가 2인 트리 이진 탐색 트리 (Binary Search Tree, BST): 이진 트리에 다음과 같은 추가적인 조건이 있는 트리 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음 3.장점과 용도 주요 용도: 데이터 검색(탐색) 장점: 탐색 속도를 개선할 수 있음 https://bit.ly/37BpXiC