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 다음은 간단한 수학식을 트리로 표현한 것이다. * / \ + – / \ / \ 7 3 5 2 > ( 7 + 3) * ( 5

Binary Heap

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