Extended Grid of Tries에 관해....

어떻게 보면 같은 해석이 될지도 모르겠지만, 제가 배운걸로 말씀드리자면..

TRIE 를 TREE 와 비교해 보면, 노드로 구성되고, 특정한 key 의 순서에
따라 데이터를 정리해 놓은 구조라는 면에서는 비슷하지만,
TREE 는 모든 노드들이 데이터로만 구성되어 있는데 반해서,
TRIE 는 모든 데이터들은 Leaf 에만 저장되고 그외의 모든 parents 들은
자식들의 catagory의 특성만을 저장할뿐, 실제 데이터는 없는거죠.
( 제가 이해할때는 Leaf 노드는 데이터를 저장하고, Parents 노드들을
guide 라고 불렀는데, 쉽게 이해하는데 도움이 되었습니다. )

간단한 예로, Binary Search Tree 를 그냥 Tree 로 그리게 되면
일반적으로 친숙한 BST 모양이 됩니다만, Trie 형태로 그리게 되면
제일 밑에있는 자식들만 데이터가 되기때문에, 데이터의 갯수를 n
이라고 하면 최대 n-1 개의 parents 가 생기게 됩니다.
BST 만 놓고 보면, 오히려 space 를 낭비하고 별로 효율이 없지만,
TRIE 의 대표적인 자료구조인 B+ Tree 를 보면 공간을 추가로 할당함으로써
검색이 훨씬 빨라지는것을 알수 있습니다.
B+ tree 는 Leaf 노드가 항상 1/2 이상 차 있어야 한다는 조건인 반면,
B* tree 는 더 엄격히 2/3 이상 차 있어야 한다는 조건이 붙어서,
더욱 공간을 효율적으로 사용합니다.
도움이 되셨길..

ps 저의 학교 숙제였던 B+ tree 의 악몽이 떠오르는군요.. 하하..
아울러, 그때 자료구조 교수님은 B+ tree 의 이름이 B+ trie 가 되어야
한다고 주장했던 기억도...