This tutorial outlines and explains the Greedy Algorithm, complete with codes and infographics that are easy to follow along. You’ll be a pro in no time!
Join the DZone community and get the full member experience. The prefix tree is related to the greedy algorithm; let’s not talk about the relationship first. Prefix tree is also called Trie, word search tree, etc. It is a tree structure used to store a large number of strings. Its characteristic is that space is changed for time, and the common prefix of the string is used to reduce the overhead of query time in order to achieve the purpose of improving efficiency. The characters of the classic prefix tree are stored on the path, and each node has no data. In order to implement certain functions with Trie, some data items are actually added to the node. Note: In the prefix tree, the downward path of each node is realized by mounting subordinate nodes. In the implementation of the code, the subscripts of the array are used to number the subordinate nodes that can be mounted, so that the one-to-one correspondence between subscripts and characters can be used to realize that each side “carries” different character information. If you need to store a string containing many types of characters, it is not appropriate to use an array to store the mounted node. For example, Java supports more than 60,000 characters, so you can’t open an array with a capacity of 60,000 from the beginning. Therefore, when there are many types of characters, the array can be replaced by a hash table to store the mounted node, and the key of the hash table can also be a one-to-one correspondence with the character. After replacing the hash table with the array, the algorithm as a whole will not change, and the details of Coding will change. However, after using hash table storage, the paths are disordered. If you want to make the paths organized like array storage, you can use an ordered table instead of hash table storage. Use the node to which the data item has been added to store the above string again: By adding nodes with data items, we can easily solve many problems, such as: How do I know if the string “bck” is stored in Trie? Answer: Starting from the root node, check if there is a way to’b’? Yes; is there a way to’c’ then? Yes; is there another way to’k’? Yes; then check the end of the node at the end of the’k’ path, if end!= 0, then “bck” is stored, if end = 0, no “bck” is stored. How do I know how many strings are prefixed with “ab” among all the strings stored in Trie? Answer: Starting from the root node, check if there is a way to’a’? Yes; is there a way to’b’ then? Yes; then check the pass of the node at the end of the’b’ path. The value of pass is the number of strings prefixed with “ab”. How do you know how many strings are stored in Trie? Answer: Just check the pass of the root node. How do you know how many empty strings are stored in Trie? Answer: Just check the end of the root node. Through the above problems, we can find that using the data item information of the node type, we can easily query each string stored in the Trie, and the cost of querying the string is very low, only need to traverse the number of characters in the string to be queried The number of times is sufficient. Idea: Starting from the root node, the pass of the nodes along the way increases by 1, and the end of the node at the end of the string increases by 1. Code: Note: Adding every string must start from the root, which means that every string is prefixed with an empty string. Idea: If the string exists, starting from the root node, the pass of the nodes along the way is decremented by 1, and the end of the node at the end of the string is decremented by 1. Code: Note: If only one target string is stored in the Trie, after modifying the node data, you need to release all the redundant nodes. Because of the automatic garbage collection in Java, when the pass of a node is 0 when we traverse for the first time, we can directly set it to null, and then all the subordinate nodes of the node will be automatically recycled. If it is implemented in C++, then it is necessary to traverse to the end, and when backtracking along the way, call the destructor to manually release the node. Idea: If the string exists, query the end of the node at the end of the string. Code: Idea: If the string exists, query the pass of the node at the end of the prefix string. Code: Under a certain standard, the algorithm that gives priority to the samples that most meet the criteria, and finally considers the samples that do not meet the criteria and finally gets an answer is called the greedy algorithm. In other words, without considering the overall optimality, what is made is a locally optimal solution in a certain sense.
