[DataStructure] Trie-1 : The Basis of The Trie Data Structure

Hello, this is Dev_dog.

 

In this post, I'm gonna explain the basis of the TRIE data structure.
If you find any errors or have any questions, feel free.

 

 한글 포스트는 아래 링크에서 보실 수 있습니다 : 
[KR/자료구조] - [자료구조] Trie(트라이)-1 : 기초 개념

 

 

 

 

---

 

 Let's suppose you want to implement autocomplete, which data structure would you consider using?
 Trie data structure which is pronounced as  /ˈtraɪ/ (or /ˈtriː/) can be a good option.
 Let's look briefly at the TRIE.

 

what is the Trie?

 The Trie is a kind of hierarchical Tree, which is also called a digital tree, radix tree or prefix tree.
 This data structure is very useful to store and search strings such as text-autocompletion. 

 

Figure 1. Tree data structure map

 

What is the form of the Trie?

 Each nodes has <Key, Value> maps. Here, the key is an Alphabet and the value is the child node corresponding to the key.

 

 The following figure illustates the Trie data structure with the words 'DEV', 'DEAR', 'PIE', 'POP', and 'POW'.
 It is the same as searching in dictionary.
 For exampe, to find the string 'DEV' in the figure below, navigate [D] → [E] → [V]  sequentially from the root node.

 

Figure 2-1. Trie data structure diagram

 

As you can see, the root node does not refer to a specific character but has only child nodes.
 Note that the nodes do not have 'parent node' and they what alphabetical node it is.

 That is, the root node has child nodes with the alphabet [D] and [P] as Keys,
[D] is a child node with [E] as a key, and [P] has child nodes with [I] and [O] as keys.

 In addition, the child nodes(which means all nodes except the root node) have a common prefix.
 That is, 'DEAR' and 'DEV' which are the child nodes of 'DE' has 'DE-', and 'POW' and 'PIE' which are the child nodes of 'P' has 'P-' as a common prefix.

 

Figure 2-2. Example of the Common prefix

 

---

 

In Summary :

• It is an ordered tree structure.
  (Sometimes it seems like a binary tree depending on the data)
• Trie has child nodes in the form <key, value> maps.
• The child nodes (except the root one) have a common prefix with siblings.
• The root node is associated with an empty character.
  (No specific character is assigned)

 

 

---

 

 

The following post will be about Implementation Trie using Java.

[EN/DATA STRUCTURE] - [DataStructure] Trie-2 : Implementation Trie using Java

 

 

---

 

This post was written with the following references.

 

https://en.wikipedia.org/wiki/Trie

Trie - Wikipedia

https://brunch.co.kr/@springboot/75

트라이(Trie) 자료구조