{"id":2941,"date":"2016-11-15T13:05:53","date_gmt":"2016-11-15T07:35:53","guid":{"rendered":"http:\/\/theoryofprogramming.azurewebsites.net\/?p=2941"},"modified":"2023-11-20T09:08:15","modified_gmt":"2023-11-20T09:08:15","slug":"compressed-trie-tree","status":"publish","type":"post","link":"https:\/\/theoryofcoding.com\/index.php\/2016\/11\/15\/compressed-trie-tree\/","title":{"rendered":"Compressed Trie Tree"},"content":{"rendered":"\n

Hello, people! In this post, we will discuss a commonly used data structure to store strings, the Compress Trie Tree, also known as Radix Tree or Patricia (Practical Algorithm to Retrieve Information Coded in Alphanumeric<\/em>) Tree. If you remember, the problem with a Trie Tree<\/a> is that it consumes a lot\u00a0of memory. So, due to its memory consumption, developers prefer using a compressed trie tree to get the same functionality at the same runtime complexity in memory-critical situations such as in android apps.<\/p>\n\n\n\n

“Compress”-ing the tree<\/h2>\n\n\n\n

Now, the idea of the compressed trie tree is to convert long chains of single-child edges to one single edge. Example, suppose we have two words “facebook” and “facepalm” in our regular trie tree, it would look like –<\/p>\n\n\n\n

\"Trie<\/figure>\n\n\n\n

It’s a pretty long one, isn’t it? Now, how about this one below?<\/p>\n\n\n\n

\"compressed<\/figure>\n\n\n\n

This one surely looks a lot compact! This is the compressed trie tree. As you can see what we do here is to make long chains of single-child edges into one edge. Unlike a regular trie tree, in a compressed trie tree, the edge labels are strings.<\/p>\n\n\n\n

Node in Compressed Trie Tree<\/h2>\n\n\n\n

For a regular trie tree, our tree\u00a0node looked something like this –<\/p>\n\n\n\n