힙 구현 일반적으로 힙 구현시 배열을 활용 힙 구현의 편의를 위해, 루트 노드 인덱스를 1로 지정함 부모 노드 인덱스 = (자식 노드 인덱스) // 2 왼쪽 자식 노드 인덱스 = (부모 노드 인덱스) * 2 오른쪽 자식 노드 인덱스 = (부모 노드 인덱스) * 2 + 1 힙 데이터 삽입 구현 # 힙 클래스 구현 class Heap: def __init__(self, data): self.heap_array = list() self.heap_array.append(None) self.heap_array.append(data) # 인덱스 1번부터 데이터가 삽입 # 삽입된 노드와 부모 노드 비교해서, 삽입된 노드가 위로 이동해야 하는지 결정 def move_up(self, inserted_idx): if in..

힙은 트리를 기반으로 하지만 변형된 형태의 정책을 채택한다. 힙(Heap) 정의 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리(Complete Binary Tree) 특징 > 힙을 이용해 최대값과 최솟값을 찾는 것은 O(logn)의 시간복잡도를 가짐 (cf. 배열 → O(n)) 활용 > 우선순위 큐와 같이, 최댓값이나 최솟값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현에 활용됨 힙의 구조 분류 최대 힙(Max Heap): 최댓값을 구하기 위한 구조 최소 힙(Min Heap): 최소값을 구하기 위한 구조 조건 각 노드의 값은 해당 노드가 가진 자식 노드의 값보다 크거나 같음(최대 힙의 경우) → 루트 노드가 최댓값을 가짐 완전 이진 트리의 형태(노드를 삽입할 때 왼쪽 노드부터 차례..

** 이진 탐색 트리의 시간복잡도 트리의 높이(Depth)를 h라고 하면, 이진 탐색 트리의 시간복잡도는 O(h) n개의 노드를 가진다면, h = log(n) 에 가깝기 때문에, 시간복잡도는 O(log(n)) 동작을 한번 실행 할 때마다 가능한 선택지가 반으로 줄여지기 때문에, 실행시간 역시 반으로 단축시킬 수 있다는 것을 의미한다. ** 이진 탐색 트리의 단점 트리가 균형 잡혀 있을 경우, 평균 시간복잡도 O(log(n)) 최악의 경우, 링크드 리스트와 동일한 성능을 갖게 되고 시간복잡도는 O(n)

** 트리 노드 삭제 3가지 경우의 수를 나눠서 생각 1) Leaf 노드 삭제 시 - 삭제할 노드의 Parent 노드가 삭제할 노드를 가리키지 않도록 한다 2) Child 노드가 1개인 노드 삭제 시 - 삭제할 노드의 Parent 노드가 삭제할 노드의 Child 노드를 가리키도록 한다 3) Child 노드가 2개인 노드 삭제 시 - 삭제할 노드의 오른쪽 자식 중, 가장 작은 값을 삭제할 노드의 Parent 노드가 가리키도록 한다. or - 삭제할 노드의 왼쪽 자식 중, 가장 큰 값을 삭제할 노드의 Parent 노드가 가리키도록 한다. **파이썬 객체지향 프로그래밍으로 트리 구현 ---> (삽입), (탐색), 삭제 class BinarySearchTree: def __init__(self, head): s..

** 파이썬 객체지향 프로그래밍으로 트리 구현 ---> 삽입, 탐색, (삭제) 1) 노드 클래스 구현 class Node: def __init__(self, value): self.value = value self.left = None self.right = None 2) 이진 탐색 트리 구현 class BinarySearchTree: def __init__(self, head): self.head = head # 삽입 def insert(self, value): self.current_node = self.head # 비교대상으로, 헤드부터 시작 while True: if value value: self.current_node = self.current_node.left # 이동 else: self.c..

트리 구현시 로직이 많이 들어가서 알고리즘 같은 느낌을 준다. 구현하기 복잡하기 때문에 자료구조 중에서 면접에서 자주 질문이 나오는 편이다. ** 트리(Tree) 구조 Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 실사용 예: 이진 트리의 형태로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨 ** 용어 정리 Node: 트리에서 데이터를 저장하는 기본 요소. (데이터 + 연결 노드의 Branch 정보) 루트 노드: 트리 맨 위에 있는 노드 레벨: 어떤 노드가 위치한 트리의 층 Parent Node: 어떤 노드의 상위 레벨에 있는 노드 Child Node: 어떤 노드의 하위 레벨에 있는 노드 Leaf Node: Child 노드를 가지지 않는 노드 Sibling (Brothe..