In this assignment, you are expected to design a Login System with Character Tree. The primary goal of this experiment is to get you to practice on the tree data structure.
Strings can essentially be viewed as the most important and common topics for a variety of programming problems. String processing has a variety of real-world applications too, such as:
All the content presented to us in textual form can be visualized as nothing but just strings.
A Character tree is a special form of tree data structure that is based on the prefix of a string. The prefix of a string is nothing but any n letters, n <=|S| that can be considered beginning strictly from the starting of a string.
A character tree is a special data structure used to store strings that can be visualized like a graph. It consists of nodes and edges. Each node consists of at max 26 children and edges connect each parent node to its children. These 26 pointers are pointers for each of the 26 letters of the English alphabet. A separate edge is maintained for every node.
Strings are stored in a top to bottom manner on the basis of their prefix in a character tree. All prefixes of length 1 are stored at until level 1, all prefixes of length 2 are sorted at until level 2 and so on.
For example, consider the following diagram : see image.
Now, one would be wondering why to use a data structure such as a character tree for processing a single string? Actually, Character trees are generally used on groups of strings, rather than a single string. When given multiple strings, we can solve a variety of problems based on them. For example, consider an English dictionary and a single string s, find the prefix of maximum length from the dictionary strings matching the string s. Solving this problem using a naive approach would require us to match the prefix of the given string with the prefix of every other word in the dictionary and note the maximum. This is an expensive process considering the amount of time it would take. Character trees can solve this problem in a much more efficient way. Before processing each Query of the type where we need to search the length of the longest prefix, we first need to add all the existing words into the dictionary. A Character tree consists of a special node called the root node. This node doesn't have any incoming edges. It only contains max 26 outgoing edges for each letter in the alphabet and is the root of the character tree.
So, the insertion of any string into a character tree starts from the root node. All prefixes of length one are direct children of the root node. In addition, all prefixes of length 2 become children of the nodes existing at level one.
In this experiment, you are expected to write an application that constructs a Login System with Character Tree. The application will take the input.txt file in the current directory and read its contents. In order to create the Character tree, there are some commands for adding, deleting and refreshing.
Structure of Commands:
-a username password #add username to the tree with the given password
-s username #search with the given username and return the password if it is
-q username password #send query for the password with the given username
-d username #delete username and its password
-l #list the tree
With -a command; The application will read the given username character by character and add them to the tree. With the last character of the username store the password.
See example: see image.
With -s command; The application will read the given username and according to the questioned username it will return an information.
See example: see image.
With -q command; The application will read the username and its password. According to the matching, it will return an information.
See example: see image.
With -d command; With the given username the application will delete the username and its password from the tree.
See example: see image.
With -l command; The application will list the all username by preorder traversal.
See example: see image.