Trie

트리(Trie) 자료구조 이 글에서는 Tree와의 구분을 위해 Trie라는 영문 표기를 사용합니다. 이 둘은 똑같이 트리1라 발음하며, 오타가 아닌 서로 다른 자료 구조입니다. Trie는 특히 영단어들을 저장하는데 유용한 자료구조로 다음과 같은 장점을 가진다. 값을 찾는 것은 최악의 경우에서 더 나은 시간 복잡도를 보인다. 해시테이블과는 달리 키 충돌을 염려하지 않아도 된다. 특정한 요소에 다다르는 경로를 찾기위한 부가적인

이진탐색트리 (Binary Search Tree) 구현하기 – python

Binary Search Tree 이진 탐색 트리는 이진 트리 구조 속에 이진 탐색 알고리듬을 이용하여 키-값 쌍을 저장하는, 어찌보면 맵(혹은 사전이라고도 하는) 구조와 유사한 형태이다. 이진 탐색 자체가 데이터가 정렬된 상태를 전제하기 때문에, 구조 내에 자료를 삽입/삭제하는 과정이 단순하지는 않지만, 어떤 정렬된 상태의 키를 기준으로 데이터를 찾는데는 매우 유리한 구조이다. 이진 탐색 트리는 특정 노드가 어디에

Parse Tree

이진트리 애플리케이션 파스 트리 트리 데이터 구조를 구현하는 방법을 알게 되면 이제 이 자료구조를 사용하여 실제 문제를 풀 수 있는 사용처에 대해서 살펴보자. 트리는 부분 요소로 나눠지는 데이터를 표현하기에 좋으므로 파싱과 관련된 작업에 많이 사용된다. 이럴 때 사용되는 트리를 파스 트리(Parse Tree)라 하는데, 파스 트리는 실제 문장이나 수학식을 표현하는데 사용될 수 있다. http://interactivepython.org/runestone/static/pythonds/_images/nlParse.png 다음은 간단한

Binary Heap

priority queue는 큐와 동일하게 동작하는 듯 보이는 비슷한 자료 구조이다. 뒤쪽으로 원소를 삽입하고 앞쪽으로 꺼낸다. 하지만 각 원소는 내부적으로 논리적인 우선순위 값을 가지고 있어서 큐 내부에서는 높은 우선순위를 갖는 원소가 앞쪽으로 오게 된다. 즉, 큐에서 꺼낼 때는 앞에서부터 꺼내게 되는데, 이 순서가 큐 내부에서의 우선순위 순과 일치하게 되는 것이다. 따라서 priority queue에 새 원소를 추가하면