muntari Log muntari Log

데이터의 계층 관계를 저장하는 자료구조이다. 여기서 계층은 상 - 하 관계에 해당 하는 데이터이다. 트리는 앞선 배열, 링크드리스트와 같은 선형 자료구조가 아닌 비선형 자료구조이다. (트리를 순회하는 과정에서 선형 자료구조와 같이 데이터를 출력할 수 도 있다.) 링크드리스트와 같이 노드 라는 객체 단위의 데이터를 사용하여 관계를 저장한다. 트리에서의 노드는 하위 관계가 있는 노드들을 가르키는 레퍼런스를 갖는다. class Node: """트리 노드를 나타내는 클래스""" def __init__(self, data): """트리 노드는 데이터와 두 자식 노드에 대한 레퍼런스를 갖는다""" self.data = data self.left_child = None self.right_child = None 트리..

Direct Access Table 배열의 인덱스 접근의 시간복잡도는 O(1)이었다. 인덱스는 데이터의 순서에 해당하는 색인, 데이터이다. 이 인덱스를 순서가 아닌 Key라 생각하고 데이터를 저장할 수 있는데 이러한 방식으로 데이터를 저장하고 관리하는 테이블을 Direct Access Table 이라 한다. Key (= 인덱스)라고 생각하고 value에 접근하는 방식이다. 특징 효율적으로 Key - value 쌍을 저장하고 가져올 수 있다. (O(1)) 하지만, 아래와 같이 Key에 해당하는 값이 커질 수 록 낭비하는 공간이 많다. (메모리 낭비가 심하다) 이 문제를 보완하기 위해 해시 테이블이 등장하게 된다. 해시 함수 하나의 Key와 그 Key에 해당하는 value를 합쳐서 Key-value 쌍이라 ..