ternary search tree-1

공정한 시간 측정을 위해서

우리는 문자열 비교를 위한 strcmp 함수를 해쉬와 트리 검색시 동일한 코딩 스타일을 사용한  inline code로 교체하였다.

우리는 ternary tree와 hashing의  성능 평가를 하기 위해 동일한 사전을 사용한다.

우선 각 단어를 트리에 입력한다.

아래 그림은 3개의 서로 다른 머시에 데이터를 빌드하고 검색시의 시간 측정 결과이다.

 

 

 

ternary search trees는 검색에 실패할때에 항상 눈에 띌만큼   해싱 보다 빠르다.

 Ternary tree 에서 일부의 캐릭터로 검색결과가 없음을 알수 있는데 반해 해싱은 모든 키를 검사한후에야 알수 있다.

길이가 긴 키 데이터군과 앞부분 몇글자가 미스매치된 군에서 ternary tree는 해싱의 1/5정도의 시간이 소요된다.

 

함수 insert3과 search의 결합은  symbol table의 시간 효율을 가져온다

내 웹사이트에 기술된 일반적인 사전에서 ternary search trees는 해싱의 약 1/3정도의 공간만을 사용한다.

ternary search trees의 선택적인 표기는 좀더 공간효율이 좋다.

서브 트리가 싱글 스트링을 포함할때, 문자열 자체의 포인터를 저장한다(그리고 각 노드는 그 노드가 노드 또는 스트링을 가르키고 있는지를 표시하기 위해 3비트를 저장한다

이것은 코드가 덜 효율적임을 의미한다.그러나 해싱에서 사용한 공간에 가깝게 트리의 노드를 줄인다.

 우리는 여러면에서 Ternary Search Tree의 안좋은 성능에 대해서 The Analysis of Hybrid Trie Structures 논문에 분석해 놓았다.

 

 binary search tree의 대부분의 표준기술은 즉시 ternary cousins에 즉시 적용할수 있다.

예를 들면 우리는 재귀적 순회로 소팅된 순서로 트리에 있는 문자열을 보여줄수 있다.

void traverse(Tptr p)

{

if(!p) return;

traverse(p->lokid);

if( p->splitchar)

traverse(p->eqkid);

else

printf("%s\n",(char*)p->eqkid);

traverse(p->hikid);

}

단순한 재귀 검색은  모든 아이템의 주어진 범위내의 주어진 성분 또는 리스트의 전임자 또는 후임자를  발견할수 있다.

만약 모든 노드에 count 필드를 추가한다면 우리는 빠르게 주어진 범위의 선택한 mth번째 가장 긴 요소 또는  주어진 서브트링으로 시작하는 많은 문자열의 수를 알 수 있을 것이다.

ternary tree 에서 이런 대부분의 연산에는 로그 시간이 요구된다.그러나 hash table에서는 linear time이 요구된다.

 

 

 

 

 

 

이 글은 스프링노트에서 작성되었습니다.