datastructure3 [자료구조] 트리 트리란? 트리는 1개 이상의 노드를 갖는 노드의 집합으로 각 항목들을 계층적으로 연관되도록 구조화 시키고자 할 때 사용하는 비선형 자료구조입니다. 트리는 디렉터리 구조등 계층적인 구조를 갖는 데이터일때 사용됩니다. 트리는 다음과 같은 조건을 만족합니다. 트리에 최상위에 루트노트라는 노드가 존재합니다. 한 노드는 하나의 노드만 가르키고 있습니다. (1 : n 관계) 트리는 사이클을 그리지 않으며, 계층적인 구조를 가집니다. 다음과 같은 구조는 트리가 아닙니다. 위의 경우는 C 노드를 A와 F가 가르키고 있기 때문에 트리가 아닙니다. 위의 경우에는 노드들이 사이클을 그리고 있기 때문에 트리가 아닙니다. 트리 용어 트리는 다음과 같은 용어를 사용합니다. 루트 노드(root node) : 부모가 없는 노드를 의.. 2021. 12. 13. [자료구조] Deque Deque? Deque(덱)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조 입니다. 두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생시킬 수 있으며, 큐와 스택을 합친 형태로 생각할 수 있습니다. deque는 양방향으로 삽입삭제를 할 수 있기 때문에 단방향으로만 삽입 삭제가 이루어지는 queue와 stack에 비해 삽입 삭제를 좀 더 간편하게 할 수 있습니다. 삽입과 삭제시 O(1)로 굉장히 빠르지만 deque 중간에 있는 데이터에는 접근하기 어렵다는 단점이 있습니다. Deque의 구현 Deque는 최소한 다음과 기능을 수행할 수 있도록 구현했습니다. create : deque를 생성 insertFront : deque의 맨앞에 원소를 추가 deleteFront : deque의 맨앞의 원소를 .. 2021. 12. 11. [자료구조] Queue Queue란? Queue는 선형구조를 가진 자료구조로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말합니다. 나중에 집어 넣은 데이터가 먼저 나오는 stack과는 반대되는 개념입니다. 보통 프린터의 출력 처리나, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야할 필요가 있는 상황에 사용됩니다. Queue의 구현 Queue의 구현해야할 기능은 다음과 같습니다. create : Queue를 생성하는 함수입니다. front로 가장 앞의 인덱스를 가르키고 rear로 가장 끝의 인덱스를 가르킵니다. enQueue : 큐에 Element(요소)를 추가합니다. deQueue : 큐에서 맨앞의 요소를 빼냅니다. peek : 큐에서 맨앞의 요소를 가져.. 2021. 12. 11. 이전 1 다음
