개발머해니

1. root 노드부터 노드의 데이터와 탐색하려는 데이터를 비교합니다. 2. 탐색하려는 데이터가 더 크면 노드의 오른쪽 자식으로, 작으면 왼쪽 자식으로 갑니다. 3. 데이터를 찾을 때까지 위 단계들을 반복합니다. class Node: """이진 탐색 트리 노드 클래스""" def __init__(self, data): self.data = data self.parent = None self.right_child = None self.left_child = None def print_inorder(node): """주어진 노드를 in-order로 출력해주는 함수""" if node is not None: print_inorder(node.left_child) print(node.data) print_ino..

1. 노드 클래스를 정의하고 2. 그 인스턴스들을 생성한 후 3. 만들어놓은 인스턴스들을 트리 모양에 맞게 연결한다. class Node: """이진 트리 노드 클래스""" def __init__(self, data): self.data = data self.left_child = None self.right_child = None # root 노드 생성 root_node = Node("A") # 다른 노드들 생성 node_B = Node("B") node_C = Node("C") node_D = Node("D") node_E = Node("E") node_F = Node("F") node_G = Node("G") node_H = Node("H") # 노드 인스턴스들 연결 root_node.left_ch..

1. root 노드와 마지막 노드의 위치를 바꿉니다. 2. 마지막 위치로 간 원래 root 노드의 데이터를 별도 변수에 저장하고, 노드는 힙에서 지웁니다. 3. 새로운 root 노드를 대상으로 heapify해서 망가진 힙 속성을 복원합니다. 4. 2단계에서 따로 저장해 둔 최우선순위 데이터를 리턴합니다. main.py from heapify_code import * class PriorityQueue: """힙으로 구현한 우선순위 큐""" def __init__(self): self.heap = [None] # 파이썬 리스트로 구현한 힙 def insert(self, data): """삽입 메소드""" self.heap.append(data) # 힙의 마지막에 데이터 추가 reverse_heapify(s..

1. priority_queue를 사용하고 2. 마지막 노드에 값을 넣고 3. 끝에서부터 역순으로 heapify! def swap(tree, index_1, index_2): """완전 이진 트리의 노드 index_1과 노드 index_2의 위치를 바꿔준다""" temp = tree[index_1] tree[index_1] = tree[index_2] tree[index_2] = temp def reverse_heapify(tree, index): """삽입된 노드를 힙 속성을 지키는 위치로 이동시키는 함수""" parent_index = index // 2 # 삽입된 노드의 부모 노드의 인덱스 계산 # 부모 노드가 존재하고, 부모 노드의 값이 삽입된 노드의 값보다 작을 때 if 0 < parent_in..

def swap(tree, index_1, index_2): """완전 이진 트리의 노드 index_1과 노드 index_2의 위치를 바꿔준다""" temp = tree[index_1] tree[index_1] = tree[index_2] tree[index_2] = temp def heapify(tree, index, tree_size): """heapify 함수""" # 왼쪽 자식 노드의 인덱스와 오른쪽 자식 노드의 인덱스를 계산 left_child_index = 2 * index right_child_index = 2 * index + 1 largest = index # 일단 부모 노드의 값이 가장 크다고 설정 # 왼쪽 자식 노드의 값과 비교 if 0 < left_child_index < tree_..

def swap(tree, index_1, index_2): """완전 이진 트리의 노드 index_1과 노드 index_2의 위치를 바꿔준다""" temp = tree[index_1] tree[index_1] = tree[index_2] tree[index_2] = temp def heapify(tree, index, tree_size): """heapify 함수""" # 왼쪽 자식 노드의 인덱스와 오른쪽 자식 노드의 인덱스를 계산 left_child_index = 2 * index right_child_index = 2 * index + 1 largest = index # 일단 부모 노드의 값이 가장 크다고 설정 # 왼쪽 자식 노드의 값과 비교 if 0 < left_child_index < tree_..

class Node: """이진 트리 노드를 나타내는 클래스""" def __init__(self, data): """이진 트리 노드는 데이터와 두 자식 노드에 대한 레퍼런스를 갖는다""" self.data = data self.left_child = None self.right_child = None def traverse_inorder(node): """in-order 순회 함수""" if node is not None: traverse_inorder(node.left_child) print(node.data) traverse_inorder(node.right_child) # 여러 노드 인스턴스 생성 node_A = Node("A") node_B = Node("B") node_C = Node("C")..

def get_parent_index(complete_binary_tree, index): """배열로 구현한 완전 이진 트리에서 index번째 노드의 부모 노드의 인덱스를 리턴하는 함수""" parent_index = index // 2 # 부모 노드가 있으면 인덱스를 리턴한다 if 0 < parent_index < len(complete_binary_tree): return parent_index return None def get_left_child_index(complete_binary_tree, index): """배열로 구현한 완전 이진 트리에서 index번째 노드의 왼쪽 자식 노드의 인덱스를 리턴하는 함수""" left_child_index = 2 * index # 왼쪽 자식 노드가 있으면 ..

1. 새로운 노드를 생성합니다. 2. root 노드부터 데이터를 비교하면서 새로운 노드를 저장할 위치를 찾습니다. 3. 새로운 노드의 데이터가 더 크면, root 노드의 오른쪽 부분 트리에 저장돼야 하고더 작으면, root 노드의 왼쪽 부분 트리에 저장돼야 합니다. 4. 찾은 위치에 새로운 노드를 저장합니다 class Node: """이진 탐색 트리 노드 클래스""" def __init__(self, data): self.data = data self.parent = None self.right_child = None self.left_child = None def print_inorder(node): """주어진 노드를 in-order로 출력해주는 함수""" if node is not None: pri..

class Node: """링크드 리스트의 노드 클래스""" def __init__(self, data): self.data = data # 실제 노드가 저장하는 데이터 self.next = None # 다음 노드에 대한 레퍼런스 self.prev = None # 전 노드에 대한 레퍼런스 class LinkedList: """링크드 리스트 클래스""" def __init__(self): self.head = None # 링크드 리스트 가장 앞 노드 self.tail = None # 링크드 리스 가장 뒤 노드 def prepend(self, data): """링크드 리스트 가장 앞에 데이터를 추가시켜주는 메소드""" new_node = Node(data) if self.head is None: self.h..