for c in currentNode.children.keys.sorted() {트리(trie)자료 구조는 트리(tree)와 발음이 비슷한데, 실제로도 tree와 비슷한 형태로 문자열이나 이와 유사한 형태의 연속열들을 저장할 수 있는 자료 구조이다. 보통 영단어들을 저장할 때 유용한데, 다음과 같은 장점들을 가진다. 특정한 값을 찾을 때, 다른 구조들에 비해서 최악의 경우에서도 대개 더 나은 시간 복잡도를 보인다. 해시테이블과 달리 키 충돌을 고려할 필요가 없다. 특정한 요소에 다다르는 경로를 찾기위한 부가적인 해시 알고리듬을 요구하지 않는다. 알파벳순으로 정렬하기가 매우 쉽다. Trie는 어떤 단어의 첫글자와 그 다음에 올 수 있는 글자, 그리고 그… 더 보기 »Trie 자료구조 – Swift
heap은 일종의 바이너리 트리를 단일 배열을 이용해서 구현한 구조로, 부모 자식 간의 직접적인 참조를 갖지 않고 배열의 인덱스에 의해서 위치 관계를 파악한다. 특히 내부 배열의 상태는 부분적으로 정렬되는 것과 비슷한데, 항상 “맨 앞의 원소를 꺼내었을 때 그 값이 최대 혹은 최소가 된다”는 특성을 가진다. 힙은 흔히 최대힙과 최소힙으로 구분하는데 이는 동일한 것이며 단지 정렬 순서만 다르다. 주로 자료 구조에서는 최대/최소 힙, 바이너리 힙, 힙 큐 혹은 우선순위 큐와 같은 이름으로 불린다.
참고로 이 자료 구조의 파이썬 구현은 [우선순위 큐 혹은 최소/최대힙]에서 한 번 설명한 바 있다.
힙으로 할 수 있는 일은 다음과 같다.
이진 탐색 트리는 이진 트리 구조 속에 이진 탐색 알고리듬을 이용하여 키-값 쌍을 저장하는, 어찌보면 맵(혹은 사전이라고도 하는) 구조와 유사한 형태이다. 이진 탐색 자체가 데이터가 정렬된 상태를 전제하기 때문에, 구조 내에 자료를 삽입/삭제하는 과정이 단순하지는 않지만, 어떤 정렬된 상태의 키를 기준으로 데이터를 찾는데는 매우 유리한 구조이다.
이진 탐색 트리는 특정 노드가 어디에 위치하는데에는 크게 관심이 없다. 단지 이를 사용하여 효율적인 탐색을 할 수 있게 한다. 보면 알겠지만 해시테이블이 메모리 공간을 더 사용하고 반대급부로 성능을 얻는 것과는 달리, 이진 탐색 트리는 트리 구조 자체의 특성을 사용하므로 부가적인 메모리 공간의 낭비는 적다고 볼 수 있다.
더 보기 »이진탐색트리 (Binary Search Tree) 구현하기 – python
트리 데이터 구조를 구현하는 방법을 알게 되면 이제 이 자료구조를 사용하여 실제 문제를 풀 수 있는 사용처에 대해서 살펴보자. 트리는 부분 요소로 나눠지는 데이터를 표현하기에 좋으므로 파싱과 관련된 작업에 많이 사용된다. 이럴 때 사용되는 트리를 파스 트리(Parse Tree)라 하는데, 파스 트리는 실제 문장이나 수학식을 표현하는데 사용될 수 있다.
http://interactivepython.org/runestone/static/pythonds/_images/nlParse.png
다음은 간단한 수학식을 트리로 표현한 것이다.
*
/ \
+ -
/ \ / \
7 3 5 2
> ( 7 + 3) * ( 5 - 2 )
우선순위 큐 (priority queue)는 큐와 비슷하게 뒤쪽으로 원소를 삽입하고 앞쪽으로 꺼낼 수 있는 자료 구조이다. 하지만 각 원소는 내부적으로 논리적인 우선순위 값을 가지고 있고, 따라서 선입선출(FIFO)의 규칙에 의해서 나오는 것이 아니라, 큐 내부에서는 높은 우선순위를 갖는 원소가 앞쪽으로 오게 된다. 즉, 큐와 마찬가지로 원소를 꺼낼 때는 앞에서부터 꺼내게 되는데, 이 순서가 큐 내부에서의 우선순위 순과 일치하게 되는 것이다. 일종의 자동으로 정렬되는 큐라고 생각하면 된다. 언어나 알고리듬 책에 따라서는 이를 최소/최대힙(min/max heap) 혹은 힙큐(heap queue)라고 부르기도 한다.더 보기 »우선순위 큐 혹은 최소/최대힙
이진 트리 탐색에서는 리스트의 값이 순서대로 정렬되어 있다는 점을 활용하여 로가디즘시간(리스트의 크기가 커지면 탐색 시간이 리스트 크기의 로그값만큼 증가하는)에서 탐색이 이루어지도록 탐색 성능을 개선시킬 수 있음을 보았다. 이 장에서는 보다 나아가 고정시간이 걸리는 탐색을 살펴보고자 한다. 이 컨셉은 “해싱”이라는 기법으로 불린다.
이를 사용하기 위해서는 리스트에서 원소가 어디쯤에 위치할 것인지에 대해 좀 더 많은 것을 알아야 한다. 만약 모든 원소가 있어야 할 위치에 있다면 단 한 번의 비교 만으로도 아이템을 찾을 수 있다. 더 보기 »Hash Map 이란 무엇인가
B * C와 같은 수식에서 그 형태는 보는 사람에게 정보를 전달하여 이를 정확하게 해석할 수 있게 한다. 이 식에서 계산 방법은 두 수 B, C 사이에 있는 연산자에 의해서 결정되며 여기서는 두 수를 곱하는 계산을 표현하고 있다.