数据结构和算法 - 尝试

trie 是一种多路搜索树，它基本上用于从一个字符串或一组字符串中检索特定的键。它以有序有效的方式存储数据，因为它使用指向字母表中每个字母的指针。

trie 数据结构基于字符串的公共前缀工作。考虑到集合中存在的字符串数量，根节点可以具有任意数量的节点。除了指向其子节点的指针之外，trie 的根不包含任何值。

trie 数据结构分为三种类型 -

• 标准尝试

• 压缩尝试

• 后缀尝试

trie 的实际应用包括自动更正、文本预测、情感分析和数据科学。

尝试中的基本操作

trie 数据结构还执行与树数据结构相同的操作。他们是 -

• 插入

• 删除

• 搜索

插入

trie 中的插入操作是一种简单的方法。trie 中的根不保存任何值，插入从根的直接子节点开始，这些子节点充当其子节点的键。然而，我们观察到 trie 中的每个节点代表输入字符串中的单个字符。因此，字符被逐个添加到尝试中，而特里中的链接充当指向下一级节点的指针。

例子

//C code for insertion operation of tries algorithm
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ALPHABET_SIZE 26
struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
    bool isEndOfWord;
};
struct TrieNode* createNode() {
    struct TrieNode* node = (struct TrieNode*)malloc(sizeof(struct TrieNode));
    node->isEndOfWord = false;
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        node->children[i] = NULL;
    }
    return node;
}
void insert(struct TrieNode* root, char* word) {
    struct TrieNode* curr = root;
    for (int i = 0; word[i] != '\0'; i++) {
        int index = word[i] - 'a';  
        if (curr->children[index] == NULL) {
            curr->children[index] = createNode();
        }   
        curr = curr->children[index];
    }
    curr->isEndOfWord = true;
}
bool search(struct TrieNode* root, char* word) {
    struct TrieNode* curr = root;
    for (int i = 0; word[i] != '\0'; i++) {
        int index = word[i] - 'a';   
        if (curr->children[index] == NULL) {
            return false;
        }   
        curr = curr->children[index];
    }
    return (curr != NULL && curr->isEndOfWord);
}
bool startsWith(struct TrieNode* root, char* prefix) {
    struct TrieNode* curr = root;
    for (int i = 0; prefix[i] != '\0'; i++) {
        int index = prefix[i] - 'a';
        if (curr->children[index] == NULL) {
            return false;
        } 
        curr = curr->children[index];
    }
    return true;
}
int main() {
    struct TrieNode* root = createNode();
    //inserting the elements
    insert(root, "Lamborghini");
    insert(root, "Mercedes-Benz");
    insert(root, "Land Rover");
    insert(root, "Maruti Suzuki");
    //printing the elements
    printf("Inserted values are: \n");
    printf("Lamborghini\n");    
    printf( "Mercedes-Benz\n");   
    printf( "Land Rover\n");      
    printf( "Maruti Suzuki"); 
    return 0;
}

Inserted values are: 
Lamborghini
Mercedes-Benz
Land Rover
Maruti Suzuki

// C++ code for Insertion operation of tries algorithm
#include <iostream>
#include <unordered_map>
using namespace std;
class TrieNode
{
public:
    unordered_map<char, TrieNode*> children;
    bool isEndOfWord;

    TrieNode()
    {
        isEndOfWord = false;
    }
};

class Trie
{
private:
    TrieNode* root;

public:
    Trie()
    {
        root = new TrieNode();
    }

    void insert(string word)
    {
        TrieNode* curr = root;
        for (char ch : word) {
            if (curr->children.find(ch) == curr->children.end()) {
                curr->children[ch] = new TrieNode();
            }
            curr = curr->children[ch];
        }
        curr->isEndOfWord = true;
    }

    bool search(string word)
    {
        TrieNode* curr = root;
        for (char ch : word) {
            if (curr->children.find(ch) == curr->children.end()) {
                return false;
            }
            curr = curr->children[ch];
        }
        return curr->isEndOfWord;
    }

    bool startsWith(string prefix)
    {
        TrieNode* curr = root;
        for (char ch : prefix) {
            if (curr->children.find(ch) == curr->children.end()) {
                return false;
            }
            curr = curr->children[ch];
        }
        return true;
    }
};

int main()
{
    Trie car;
    //inserting the elements
    car.insert("Lamborghini");
    car.insert("Mercedes-Benz");
    car.insert("Land Rover");
    car.insert("Maruti Suzuki");
    //printing the elmenents
    printf("Inserted values are: \n");
    cout << "Lamborghini" << endl;
    cout <<"Mercedes-Benz"<< endl;
    cout <<"Land Rover" << endl;
    cout << "Maruti Suzuki" << endl;
    return 0;
}

Inserted values are: 
Lamborghini
Mercedes-Benz
Land Rover
Maruti Suzuki

//Java Code for insertion operation of tries Algorithm
import java.util.HashMap;
import java.util.Map;
class TrieNode {
    Map<Character, TrieNode> children;
    boolean isEndOfWord;
    TrieNode() {
        children = new HashMap<>();
        isEndOfWord = false;
    }
}
class Trie {
    private TrieNode root;

    Trie() {
        root = new TrieNode();
    }
    void insert(String word) {
        TrieNode curr = root;
        for (char ch : word.toCharArray()) {
            curr.children.putIfAbsent(ch, new TrieNode());
            curr = curr.children.get(ch);
        }
        curr.isEndOfWord = true;
    }
    boolean search(String word) {
        TrieNode curr = root;
        for (char ch : word.toCharArray()) {
            if (!curr.children.containsKey(ch)) {
                return false;
            }
            curr = curr.children.get(ch);
        }
        return curr.isEndOfWord;
    }
    boolean startsWith(String prefix) {
        TrieNode curr = root;
        for (char ch : prefix.toCharArray()) {
            if (!curr.children.containsKey(ch)) {
                return false;
            }
            curr = curr.children.get(ch);
        }
        return true;
    }
}
public class Main {
    public static void main(String[] args) {
        Trie car = new Trie();
        //Inserting the elements
        car.insert("Lamborghini");
        car.insert("Mercedes-Benz");
        car.insert("Land Rover");
        car.insert("Maruti Suzuki");
        //Printing the elements
        System.out.println("Inserted values are: ");
        System.out.println("Lamborghini");
        System.out.println("Mercedes-Benz");
        System.out.println("Land Rover");
        System.out.println("Maruti Suzuki");
    }
}

Inserted values are: 
Lamborghini
Mercedes-Benz
Land Rover
Maruti Suzuki

#Python Code for insertion operation of tries Algorithm
class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEndOfWord = False
class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        curr = self.root
        for ch in word:
            if ch not in curr.children:
                curr.children[ch] = TrieNode()
            curr = curr.children[ch]
        curr.isEndOfWord = True
    def search(self, word):
        curr = self.root
        for ch in word:
            if ch not in curr.children:
                return False
            curr = curr.children[ch]
        return curr.isEndOfWord
    def startsWith(self, prefix):
        curr = self.root
        for ch in prefix:
            if ch not in curr.children:
                return False
            curr = curr.children[ch]
        return True
if __name__ == '__main__':
    car = Trie()
    #inserting the elements
    car.insert("Lamborghini")
    car.insert("Mercedes-Benz")
    car.insert("Land Rover")
    car.insert("Maruti Suzuki")
    #printing the elements
    print("Inserted values are: ")
    print("Lamborghini")
    print("Mercedes-Benz")
    print("Land Rover")
    print("Maruti Suzuki")

Inserted values are: 
Lamborghini
Mercedes-Benz
Land Rover
Maruti Suzuki

删除

trie 中的删除操作是使用自下而上的方法执行的。在 trie 中搜索该元素，如果找到则将其删除。但是，在执行删除操作时需要记住一些特殊情况。

情况 1 - 密钥是唯一的 - 在这种情况下，整个密钥路径将从节点中删除。（唯一键表明没有其他路径从一条路径分支出来）。

情况 2 - 键不唯一 - 叶节点已更新。例如，如果要删除的键是see但它是另一个键seethe的前缀；我们删除 see 并将 t、h 和 e 的布尔值更改为 false。

情况 3 - 要删除的键已经有一个前缀 - 删除前缀之前的值并且前缀保留在树中。例如，如果要删除的键是heart但存在另一个键he；所以我们删除 a、r 和 t，直到只剩下他。

例子

//C code for Deletion Operation of tries Algorithm
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//Define size 26
#define ALPHABET_SIZE 26
struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
    bool isEndOfWord;
};
struct TrieNode* createNode() {
    struct TrieNode* node = (struct TrieNode*)malloc(sizeof(struct TrieNode));
    node->isEndOfWord = false;
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        node->children[i] = NULL;
    }
    return node;
}
void insert(struct TrieNode* root, char* word) {
    struct TrieNode* curr = root;
    for (int i = 0; word[i] != '\0'; i++) {
        int index = word[i] - 'a';
        if (curr->children[index] == NULL) {
            curr->children[index] = createNode();
        }
        curr = curr->children[index];
    }
    curr->isEndOfWord = true;
}
bool search(struct TrieNode* root, char* word) {
    struct TrieNode* curr = root;
    for (int i = 0; word[i] != '\0'; i++) {
        int index = word[i] - 'a';
        if (curr->children[index] == NULL) {
            return false;
        }
        curr = curr->children[index];
    }
    return (curr != NULL && curr->isEndOfWord);
}
bool startsWith(struct TrieNode* root, char* prefix) {
    struct TrieNode* curr = root;
    for (int i = 0; prefix[i] != '\0'; i++) {
        int index = prefix[i] - 'a';
        if (curr->children[index] == NULL) {
            return false;
        }
        curr = curr->children[index];
    }
    return true;
}
bool deleteWord(struct TrieNode* root, char* word) {
    struct TrieNode* curr = root;
    struct TrieNode* parent = NULL;
    int index;
    for (int i = 0; word[i] != '\0'; i++) {
        index = word[i] - 'a';
        if (curr->children[index] == NULL) {
            return false; // Word does not exist in the Trie
        }
        parent = curr;
        curr = curr->children[index];
    }
    if (!curr->isEndOfWord) {
        return false; // Word does not exist in the Trie
    }
    curr->isEndOfWord = false; // Mark as deleted

    if (parent != NULL) {
        parent->children[index] = NULL; // Remove the child node
    }

    return true;
}
int main() {
    struct TrieNode* root = createNode();
    //Inserting the elements 
    insert(root, "lamborghini");
    insert(root, "mercedes-benz");
    insert(root, "land rover");
    insert(root, "maruti suzuki");
    //Before Deletion
    printf("Before Deletion\n");
    printf("%d\n", search(root, "lamborghini"));      // Output: 1 (true)
    printf("%d\n", search(root, "mercedes-benz"));    // Output: 1 (true)
    printf("%d\n", search(root, "land rover"));       // Output: 1 (true)
    printf("%d\n", search(root, "maruti suzuki"));    // Output: 1 (true)
    //Deleting the elements
    deleteWord(root, "lamborghini");
    deleteWord(root, "land rover");
    //After Deletion
    printf("After Deletion\n");
    printf("%d\n", search(root, "lamborghini"));      // Output: 0 (false)
    printf("%d\n", search(root, "mercedes-benz"));    // Output: 1 (true)
    printf("%d\n", search(root, "land rover"));       // Output: 0 (false)
    printf("%d\n", search(root, "maruti suzuki"));    // Output: 1 (true)
    return 0;
}

Before Deletion
1
1
1
1
After Deletion
0
1
0
1

//C++ code for Deletion operation of tries algorithm
#include <iostream>
#include <unordered_map>
using namespace std;
class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool isEndOfWord;
    TrieNode() {
        isEndOfWord = false;
    }
};
class Trie {
private:
    TrieNode* root;
public:
    Trie() {
        root = new TrieNode();
    }
    void insert(string word) {
        TrieNode* curr = root;
        for (char ch : word) {
            if (curr->children.find(ch) == curr->children.end()) {
                curr->children[ch] = new TrieNode();
            }
            curr = curr->children[ch];
        }
        curr->isEndOfWord = true;
    }
    bool search(string word) {
        TrieNode* curr = root;
        for (char ch : word) {
            if (curr->children.find(ch) == curr->children.end()) {
                return false;
            }
            curr = curr->children[ch];
        }
        return curr->isEndOfWord;
    }
    bool startsWith(string prefix) {
        TrieNode* curr = root;
        for (char ch : prefix) {
            if (curr->children.find(ch) == curr->children.end()) {
                return false;
            }
            curr = curr->children[ch];
        }
        return true;
    }
    bool deleteWord(string word) {
        return deleteHelper(root, word, 0);
    }
private:
    bool deleteHelper(TrieNode* curr, string word, int index) {
        if (index == word.length()) {
            if (!curr->isEndOfWord) {
                return false; // Word does not exist in the Trie
            }
            curr->isEndOfWord = false; // Mark as deleted
            return curr->children.empty(); // Return true if no more children
        }
        char ch = word[index];
        if (curr->children.find(ch) == curr->children.end()) {
            return false; // Word does not exist in the Trie
        }
        TrieNode* child = curr->children[ch];
        bool shouldDeleteChild = deleteHelper(child, word, index + 1);

        if (shouldDeleteChild) {
            curr->children.erase(ch); // Remove the child node if necessary
            return curr->children.empty(); // Return true if no more children
        }
        return false;
    }
};
int main() {
    Trie car;
    //inserting the elemnets
    car.insert("Lamborghini");
    car.insert("Mercedes-Benz");
    car.insert("Land Rover");
    car.insert("Maruti Suzuki");
    //Before Deletion
    cout << "Before Deletion" << endl;
    cout << car.search("Lamborghini") << endl;       // Output: 1 (true)
    cout << car.search("Mercedes-Benz") << endl;     // Output: 1 (true)
    cout << car.search("Land Rover") << endl;        // Output: 1 (true)
    cout << car.search("Maruti Suzuki") << endl;     // Output: 1 (true)
    //Deleting elements using deletion operation
    car.deleteWord("Lamborghini");
    car.deleteWord("Land Rover");
    //After Deletion
    cout << "After Deletion" << endl;
    cout << car.search("Lamborghini") << endl;       // Output: 0 (false)
    cout << car.search("Mercedes-Benz") << endl;     // Output: 1 (true)
    cout << car.search("Land Rover") << endl;        // Output: 0 (false)
    cout << car.search("Maruti Suzuki") << endl;     // Output: 1 (true)
    return 0;
}

Before Deletion
1
1
1
1
After Deletion
0
1
0
1

//Java code for Deletion operator of tries algotrithm
import java.util.HashMap;
import java.util.Map;
class TrieNode {
    Map<Character, TrieNode> children;
    boolean isEndOfWord;

    TrieNode() {
        children = new HashMap<>();
        isEndOfWord = false;
    }
}
class Trie {
    private TrieNode root;

    Trie() {
        root = new TrieNode();
    }
    void insert(String word) {
        TrieNode curr = root;
        for (char ch : word.toCharArray()) {
            curr.children.putIfAbsent(ch, new TrieNode());
            curr = curr.children.get(ch);
        }
        curr.isEndOfWord = true;
    }
    boolean search(String word) {
        TrieNode curr = root;
        for (char ch : word.toCharArray()) {
            if (!curr.children.containsKey(ch)) {
                return false;
            }
            curr = curr.children.get(ch);
        }
        return curr.isEndOfWord;
    }
    boolean startsWith(String prefix) {
        TrieNode curr = root;
        for (char ch : prefix.toCharArray()) {
            if (!curr.children.containsKey(ch)) {
                return false;
            }
            curr = curr.children.get(ch);
        }
        return true;
    }
    boolean delete(String word) {
        return deleteHelper(root, word, 0);
    }
    private boolean deleteHelper(TrieNode curr, String word, int index) {
        if (index == word.length()) {
            if (!curr.isEndOfWord) {
                return false; // Word does not exist in the Trie
            }
            curr.isEndOfWord = false; // Mark as deleted
            return curr.children.isEmpty(); // Return true if no more children
        }
        char ch = word.charAt(index);
        if (!curr.children.containsKey(ch)) {
            return false; // Word does not exist in the Trie
        }
        TrieNode child = curr.children.get(ch);
        boolean shouldDeleteChild = deleteHelper(child, word, index + 1);
        if (shouldDeleteChild) {
            curr.children.remove(ch); // Remove the child node if necessary
            return curr.children.isEmpty(); // Return true if no more children
        }

        return false;
    }
}
public class Main {
    public static void main(String[] args) {
        Trie car = new Trie(); 
       //Inserting the elements
        car.insert("Lamborghini");
        car.insert("Mercedes-Benz");
        car.insert("Land Rover");
        car.insert("Maruti Suzuki");
       //Before Deletion
        System.out.println("Before Deletion");
        //Printing the elements
        System.out.println(car.search("Lamborghini"));       // Output: true
        System.out.println(car.search("Mercedes-Benz")); // Output: true
        System.out.println(car.search("Land Rover"));      // Output: true
        System.out.println(car.search("Maruti Suzuki"));         // Output: true  
       //Deleting the elements using deletion operation
        car.delete("Lamborghini");
        car.delete("Land Rover");     
       // After Deletion
        System.out.println("After Deletion");
       // Prints the elements in the Boolean expression
        System.out.println(car.search("Lamborghini"));      // Output: false
        System.out.println(car.search("Mercedes-Benz"));   // Output: true
        System.out.println(car.search("Land Rover"));      // Output: false
        System.out.println(car.search("Maruti Suzuki"));  // Output: true
    }
}

Before Deletion
true
true
true
true
After Deletion
false
true
false
true

#python Code for Deletion operation of tries algorithm
class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEndOfWord = False
class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        curr = self.root
        for ch in word:
            if ch not in curr.children:
                curr.children[ch] = TrieNode()
            curr = curr.children[ch]
        curr.isEndOfWord = True
    def search(self, word):
        curr = self.root
        for ch in word:
            if ch not in curr.children:
                return False
            curr = curr.children[ch]
        return curr.isEndOfWord
    def startsWith(self, prefix):
        curr = self.root
        for ch in prefix:
            if ch not in curr.children:
                return False
            curr = curr.children[ch]
        return True
    def delete(self, word):
        return self.deleteHelper(self.root, word, 0)

    def deleteHelper(self, curr, word, index):
        if index == len(word):
            if not curr.isEndOfWord:
                return False  # Word does not exist in the Trie
            curr.isEndOfWord = False  # Mark as deleted
            return len(curr.children) == 0  # Return True if no more children
        ch = word[index]
        if ch not in curr.children:
            return False  # Word does not exist in the Trie
        child = curr.children[ch]
        shouldDeleteChild = self.deleteHelper(child, word, index + 1)
        if shouldDeleteChild:
            del curr.children[ch]  # Remove the child node if necessary
            return len(curr.children) == 0  # Return True if no more children
        return False
trie = Trie()
#inserting the elements
trie.insert("Lamborghini")
trie.insert("Mercedes-Benz")
trie.insert("Land Rover")
trie.insert("Maruti Suzuki")
#Before Deletion
print("Before Deletion:")
print(trie.search("Lamborghini"))       # Output: True
print(trie.search("Mercedes-Benz"))     # Output: True
print(trie.search("Land Rover"))        # Output: True
print(trie.search("Maruti Suzuki"))     # Output: True
#deleting the elements using Deletion operation
trie.delete("Lamborghini")
trie.delete("Land Rover")
#After Deletion
print("After Deletion:")
#print elements
print(trie.search("Lamborghini"))       # Output: False
print(trie.search("Mercedes-Benz"))     # Output: True
print(trie.search("Land Rover"))        # Output: False
print(trie.search("Maruti Suzuki"))     # Output: True

Before Deletion:
True
True
True
True
After Deletion:
False
True
False
True

搜索

在 trie 中搜索是一种相当简单的方法。我们只能根据关键节点（插入操作开始的节点）来向下移动 trie 的级别。搜索一直进行到到达路径末端为止。如果找到该元素，则查找成功；否则提示搜索失败。

例子

//C program for search operation of tries algorithm
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ALPHABET_SIZE 26
struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
    bool isEndOfWord;
};
struct TrieNode* createNode() {
    struct TrieNode* node = (struct TrieNode*)malloc(sizeof(struct TrieNode));
    node->isEndOfWord = false;
    
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        node->children[i] = NULL;
    }
    return node;
}

void insert(struct TrieNode* root, char* word) {
    struct TrieNode* curr = root;
    for (int i = 0; word[i] != '\0'; i++) {
        int index = word[i] - 'a';    
        if (curr->children[index] == NULL) {
            curr->children[index] = createNode();
        }  
        curr = curr->children[index];
    } 
    curr->isEndOfWord = true;
}
bool search(struct TrieNode* root, char* word) {
    struct TrieNode* curr = root;   
    for (int i = 0; word[i] != '\0'; i++) {
        int index = word[i] - 'a';
        
        if (curr->children[index] == NULL) {
            return false;
        }   
        curr = curr->children[index];
    }
    return (curr != NULL && curr->isEndOfWord);
}
bool startsWith(struct TrieNode* root, char* prefix) {
    struct TrieNode* curr = root;
    for (int i = 0; prefix[i] != '\0'; i++) {
        int index = prefix[i] - 'a';  
        if (curr->children[index] == NULL) {
            return false;
        } 
        curr = curr->children[index];
    }
    return true;
}

int main() {
    struct TrieNode* root = createNode();
    //inserting the elements
    insert(root, "Lamborghini");
    insert(root, "Mercedes-Benz");
    insert(root, "Land Rover");
    insert(root, "Maruti Suzuki");    
   //Searching elements
    printf("Searching Cars\n");
    //Printing searched elements
    printf("%d\n", search(root, "Lamborghini"));     // Output: 1 (true)
    printf("%d\n", search(root, "Mercedes-Benz"));   // Output: 1 (true)
    printf("%d\n", search(root, "Honda"));           // Output: 0 (false)
    printf("%d\n", search(root, "Land Rover"));      // Output: 1 (true)
    printf("%d\n", search(root, "BMW"));             // Output: 0 (false)   
    //Searching the elements the name starts with?
    printf("Cars name starts with\n");
    //Printing the elements
    printf("%d\n", startsWith(root, "Lambo"));       // Output: 1 (true)
    printf("%d\n", startsWith(root, "Hon"));         // Output: 0 (false)
    printf("%d\n", startsWith(root, "Hy"));          // Output: 0 (false)
    printf("%d\n", startsWith(root, "Mar"));         // Output: 1 (true)
    printf("%d\n", startsWith(root, "Land"));        // Output: 1 (true)   
    return 0;
}	

Searching Cars
1
1
0
1
0
Cars name starts with
1
0
0
1
1

//C++ code for Search operation of tries algorithm
#include <iostream>
#include <unordered_map>
using namespace std;
class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool isEndOfWord;
    
    TrieNode() {
        isEndOfWord = false;
    }
};
class Trie {
private:
    TrieNode* root;
public:
    Trie() {
        root = new TrieNode();
    }
    void insert(string word) {
        TrieNode* curr = root;
        for (char ch : word) {
            if (curr->children.find(ch) == curr->children.end()) {
                curr->children[ch] = new TrieNode();
            }
            curr = curr->children[ch];
        }
        curr->isEndOfWord = true;
    }
    bool search(string word) {
        TrieNode* curr = root;
        for (char ch : word) {
            if (curr->children.find(ch) == curr->children.end()) {
                return false;
            }
            curr = curr->children[ch];
        }
        return curr->isEndOfWord;
    }
    bool startsWith(string prefix) {
        TrieNode* curr = root;
        for (char ch : prefix) {
            if (curr->children.find(ch) == curr->children.end()) {
                return false;
            }
            curr = curr->children[ch];
        }
        return true;
    }
};
int main() {
    Trie car;
    //inserting the elements
    car.insert("Lamborghini");
    car.insert("Mercedes-Benz");
    car.insert("Land Rover");
    car.insert("Maruti Suzuki");
   //searching elements
    cout<< "Searching Cars"<< endl; 
    // Printing searched elements in Boolean expression
    cout << car.search("Lamborghini") << endl;     // Output: 1 (true)
    cout << car.search("Mercedes-Benz") << endl;    // Output: 1 (true)
    cout << car.search("Honda") << endl;     // Output: 0 (false)
    cout << car.search("Land Rover") << endl;    // Output: 1 (true)
    cout << car.search("BMW") << endl;   // Output: 0 (false)   
   //searching names starts with?
    cout<<"cars name starts with" << endl;
    //Printing the elements
    cout << car.startsWith("Lambo") << endl;   // Output: 1 (true)
    cout << car.startsWith("Hon") << endl;    // Output: 0 (false)
    cout << car.startsWith("Hy") << endl;    // Output: 0 (false)
    cout << car.startsWith("Mar") << endl;    // Output: 1 (true)
    cout << car.startsWith("Land") << endl;   // Output: 1 (true)
    return 0;
}

Searching Cars
1
1
0
1
0
cars name starts with
1
0
0
1
1

//Java program for tries Algorithm
import java.util.HashMap;
import java.util.Map;
class TrieNode {
    Map<Character, TrieNode> children;
    boolean isEndOfWord;
    TrieNode() {
        children = new HashMap<>();
        isEndOfWord = false;
    }
}
class Trie {
    private TrieNode root;
    Trie() {
        root = new TrieNode();
    }
    void insert(String word) {
        TrieNode curr = root;
        for (char ch : word.toCharArray()) {
            curr.children.putIfAbsent(ch, new TrieNode());
            curr = curr.children.get(ch);
        }
        curr.isEndOfWord = true;
    }
    boolean search(String word) {
        TrieNode curr = root;
        for (char ch : word.toCharArray()) {
            if (!curr.children.containsKey(ch)) {
                return false;
            }
            curr = curr.children.get(ch);
        }
        return curr.isEndOfWord;
    }
    boolean startsWith(String prefix) {
        TrieNode curr = root;
        for (char ch : prefix.toCharArray()) {
            if (!curr.children.containsKey(ch)) {
                return false;
            }
            curr = curr.children.get(ch);
        }
        return true;
    }
}
public class Main {
    public static void main(String[] args) {
        Trie car = new Trie();
        //Inserting the elements
        car.insert("Lamborghini");
        car.insert("Mercedes-Benz");
        car.insert("Land Rover");
        car.insert("Maruti Suzuki");
        //searching the elements
        System.out.println("Searching Cars");
        //Printing the searched elements
        System.out.println(car.search("Lamborghini"));     // Output: true
        System.out.println(car.search("Mercedes-Benz"));   // Output: true
        System.out.println(car.search("Honda"));           // Output: false
        System.out.println(car.search("Land Rover"));      // Output: true
        System.out.println(car.search("BMW"));             // Output: false  
        //searching the elements name start with?
        System.out.println("Cars name starts with");
        //Printing the elements
        System.out.println(car.startsWith("Lambo"));       // Output: true
        System.out.println(car.startsWith("Hon"));         // Output: false
        System.out.println(car.startsWith("Hy"));          // Output: false
        System.out.println(car.startsWith("Mar"));         // Output: true
        System.out.println(car.startsWith("Land"));        // Output: true
    }
}

Searching Cars
true
true
false
true
false
Cars name starts with
true
false
false
true
true

#Python code for Search operation of tries algorithm
class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEndOfWord = False
class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        curr = self.root
        for ch in word:
            if ch not in curr.children:
                curr.children[ch] = TrieNode()
            curr = curr.children[ch]
        curr.isEndOfWord = True
    def search(self, word):
        curr = self.root
        for ch in word:
            if ch not in curr.children:
                return False
            curr = curr.children[ch]
        return curr.isEndOfWord
    def startsWith(self, prefix):
        curr = self.root
        for ch in prefix:
            if ch not in curr.children:
                return False
            curr = curr.children[ch]
        return True
if __name__ == '__main__':
    car = Trie()
   #Inserting the elements
    car.insert("Lamborghini")
    car.insert("Mercedes-Benz")
    car.insert("Land Rover")
    car.insert("Maruti Suzuki")
    #Searching elements
    print("Searching Cars")
    #Printing the searched elements
    print(car.search("Lamborghini"))     # Output: True
    print(car.search("Mercedes-Benz"))   # Output: True
    print(car.search("Honda"))           # Output: False
    print(car.search("Land Rover"))      # Output: True
    print(car.search("BMW"))             # Output: False
    #printing elements name starts with?
    print("Cars name starts with")
    print(car.startsWith("Lambo"))       # Output: True
    print(car.startsWith("Hon"))         # Output: False
    print(car.startsWith("Hy"))          # Output: False
    print(car.startsWith("Mar"))         # Output: True
    print(car.startsWith("Land"))        # Output: True  

Before Deletion:
True
True
True
True
After Deletion:
False
True
False
True