미처 완성되지 못한 알고리즘

테이블의 시간 복잡도는 O(1)이다. 테이블에 저장되는 데이터는 키와 값이 하나의 쌍을 이룬다. 키가 존재하지 않는 값은 저장할 수 없으며, 모든 키는 중복되지 않는다.

이진 탐색 트리의 탐색 연산은 O(log2n)의 시간 복잡도를 가진다. 이러한 이진 탐색 트리는 균형이 맞지 않을수록 O(n)에 가까운 시간 복잡도를 보인다. 이것이 이진 탐색 트리의 단점이며, 이 단점을 해결한 트리를 가리켜 '균형 잡힌 이진 트리'라 불리운다. 그 종류는 다음과 같이 5가지가 된다. 1.AVL 트리2.2-3 트리3.2-3-4 트리4.Red-Black 트리5.B트리 AVL트리는 노드가 추가될 때, 그리고 삭제될 때 트리의 균형상태를 파악해서 스스로 그 구조를 변경하여 균형을 잡는 멋진 트리다. AVL트리에서는 균형의 정도를 표현하기 위해서 균형 인수라는 것을 사용하며 이 균형 인수는 다음과 같이 계산된다. 균형 인수 = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이 AVL 트리는 ..

일반적으로 큐는 FIFO 구조로, 먼저 입력된 데이터가 먼저 출력되지만 우선순위 큐는 각 데이터의 우선순위에 따라 나중에 입력된 데이터가 더 먼저 출력될 수도 있다. 우선순위 큐의 구현 방법에는 3가지가 있다. 1.배열2.연결 리스트3.힙 여기서 1,2방식은 각 각 문제점이 있다. 1. 데이터를 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 수반해야 한다.2.삽입의 위치를 찾기 위해서 최악의 경우 저장된 모든 데이터와 우선순위의 비교를 진행해야 될 수도 있다. 2의 경우는 1,2방식 모두에게 해당하며 1의 경우는 1의 방식에 해당된다. 그래서 우선순위 큐는 힙이라는 자료구조를 이용해서 구현하는 것이 일반적이다. 힙이란? 이진트리이되 완전 이진 트리이며, 모든 노드..