개발머해니

main.py from HDLL import LinkedList # 해시 테이블에서 사용할 링크드 리스트 임포트 class HashTable: def __init__(self, capacity): self._capacity = capacity # 파이썬 리스트 수용 크기 저장 self._table = [LinkedList() for _ in range(self._capacity)] # 파이썬 리스트 인덱스에 반 링크드 리스트 저장 def _hash_function(self, key): """ 주어진 key에 나누기 방법을 사용해서 해시된 값을 리턴하는 메소드 주의: key는 파이썬 불변 타입이여야 한다. """ return hash(key) % self._capacity def _get_linked_li..

main.py from HDLL import LinkedList class HashTable: def __init__(self, capacity): self._capacity = capacity # 파이썬 리스트 수용 크기 저장 self._table = [LinkedList() for _ in range(self._capacity)] # 파이썬 리스트 인덱스에 반 링크드 리스트 저장 def _hash_function(self, key): """ 주어진 key에 나누기 방법을 사용해서 해시된 값을 리턴하는 메소드 주의 사항: key는 파이썬 불변 타입이어야 한다. """ return hash(key) % self._capacity def _get_linked_list_for_key(self, key): "..

1. 지우려는 노드의 successor를 받아옵니다. (find_min() 메소드 활용) 2. 삭제하려는 노드 데이터에 successor의 데이터를 저장합니다. 3. successor 노드를 삭제합니다. 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_inorder(..

삭제하는 노드의 위치를 자식 노드가 대신 차지해야 한다 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_inorder(node.right_child) class BinarySearchTree: """이진 탐색 트리 클래스""" def __init__(self): se..

1. 먼저 search() 메소드를 사용해서 삭제하려는 데이터의 노드를 받아 옵니다. 2. 삭제하려는 노드가 부모 노드의 왼쪽 자식이면부모의 왼쪽 자식을 None으로 바꿔 줍니다 3. 삭제하려는 노드가 부모 노드의 오른쪽 자식이면부모의 오른쪽 자식을 None으로 바꿔 줍니다 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.lef..

1. find_min()메소드의 파라미터로 root 노드를 리턴해 주면 트리 전체에서 가장 작은 노드가 리턴됩니다. 여기서는 1이 저장된 노드겠죠? 2. 5가 저장된 노드를find_min()메소드의 파라미터로 넘기면 이 노란색 박스 안에 있는 부분 트리 안에서 가장 작은 노드, 그러니까 이번에도 1이 저장된 노드가 리턴됩니다. 3. 하나만 더 볼게요. 14가 저장된 노드를 find_min() 메소드의 파라미터로 넘기면 이 빨간색 박스 안에 있는 부분 트리 안에서 가장 작은 노드 12가 리턴됩니다. class Node: """이진 탐색 트리 노드 클래스""" def __init__(self, data): self.data = data self.parent = None self.right_child = No..

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..