prueba | (Borrar)

En la publicación anterior sobre trie , describimos cómo insertar y buscar un Node en trie. Aquí hay un algoritmo sobre cómo eliminar un Node de trie.
Durante la operación de eliminación, eliminamos la clave de forma ascendente utilizando la recursividad. Las siguientes son condiciones posibles al eliminar la clave de trie, 

1. Es posible que la clave no esté allí en trie. La operación de eliminación no debe modificar el intento.
2. Clave presente como clave única (ninguna parte de la clave contiene otra clave (prefijo), ni la clave en sí es prefijo de otra clave en trie). Eliminar todos los Nodes.
3. La clave es la clave de prefijo de otra clave larga en trie. Desmarque el Node hoja.
4. Clave presente en trie, que tiene al menos otra clave como clave de prefijo. Eliminar Nodes desde el final de la clave hasta el primer Node de hoja de la clave de prefijo más larga.

El siguiente código presenta un algoritmo para implementar las condiciones anteriores. 

// C++ implementation of delete
// operations on Trie
#include <bits/stdc++.h>
using namespace std;
 
const int ALPHABET_SIZE = 26;
 
// trie node
struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
 
    // isEndOfWord is true if the node represents
    // end of a word
    bool isEndOfWord;
};
 
// Returns new trie node (initialized to NULLs)
struct TrieNode* getNode(void)
{
    struct TrieNode* pNode = new TrieNode;
 
    pNode->isEndOfWord = false;
 
    for (int i = 0; i < ALPHABET_SIZE; i++)
        pNode->children[i] = NULL;
 
    return pNode;
}
 
// If not present, inserts key into trie
// If the key is prefix of trie node, just
// marks leaf node
void insert(struct TrieNode* root, string key)
{
    struct TrieNode* pCrawl = root;
 
    for (int i = 0; i < key.length(); i++) {
        int index = key[i] - 'a';
        if (!pCrawl->children[index])
            pCrawl->children[index] = getNode();
 
        pCrawl = pCrawl->children[index];
    }
 
    // mark last node as leaf
    pCrawl->isEndOfWord = true;
}
 
// Returns true if key presents in trie, else
// false
bool search(struct TrieNode* root, string key)
{
    struct TrieNode* pCrawl = root;
 
    for (int i = 0; i < key.length(); i++) {
        int index = key[i] - 'a';
        if (!pCrawl->children[index])
            return false;
 
        pCrawl = pCrawl->children[index];
    }
 
    return (pCrawl != NULL && pCrawl->isEndOfWord);
}
 
// Returns true if root has no children, else false
bool isEmpty(TrieNode* root)
{
    for (int i = 0; i < ALPHABET_SIZE; i++)
        if (root->children[i])
            return false;
    return true;
}
 
// Recursive function to delete a key from given Trie
TrieNode* remove(TrieNode* root, string key, int depth = 0)
{
    // If tree is empty
    if (!root)
        return NULL;
 
    // If last character of key is being processed
    if (depth == key.size()) {
 
        // This node is no more end of word after
        // removal of given key
        if (root->isEndOfWord)
            root->isEndOfWord = false;
 
        // If given is not prefix of any other word
        if (isEmpty(root)) {
            delete (root);
            root = NULL;
        }
 
        return root;
    }
 
    // If not last character, recur for the child
    // obtained using ASCII value
    int index = key[depth] - 'a';
    root->children[index] =
          remove(root->children[index], key, depth + 1);
 
    // If root does not have any child (its only child got
    // deleted), and it is not end of another word.
    if (isEmpty(root) && root->isEndOfWord == false) {
        delete (root);
        root = NULL;
    }
 
    return root;
}
 
// Driver
int main()
{
    // Input keys (use only 'a' through 'z'
    // and lower case)
    string keys[] = { "the", "a", "there",
                      "answer", "any", "by",
                      "bye", "their", "hero", "heroplane" };
    int n = sizeof(keys) / sizeof(keys[0]);
 
    struct TrieNode* root = getNode();
 
    // Construct trie
    for (int i = 0; i < n; i++)
        insert(root, keys[i]);
 
    // Search for different keys
    search(root, "the") ? cout << "Yes\n" : cout << "No\n";
    search(root, "these") ? cout << "Yes\n" : cout << "No\n";
 
    remove(root, "heroplane");
    search(root, "hero") ? cout << "Yes\n" : cout << "No\n";
    return 0;
}

// Java implementation of delete
// operations on Trie
import java.util.*;
 
public class GFG{
     
    static int ALPHABET_SIZE = 26;
 
    // trie node
    static class TrieNode {
        TrieNode children[] = new TrieNode[ALPHABET_SIZE];
 
        // isEndOfWord is true if the node represents
        // end of a word
        boolean isEndOfWord;
    }
 
 
    // If not present, inserts key into trie
    // If the key is prefix of trie node, just
    // marks leaf node
    static void insert(TrieNode root, String key)
    {
        TrieNode pCrawl = root;
 
        for (int i = 0; i < key.length(); i++) {
            int index = key.charAt(i) - 'a';
            if (pCrawl.children[index] == null)
                pCrawl.children[index] = new TrieNode();
 
            pCrawl = pCrawl.children[index];
        }
 
        // mark last node as leaf
        pCrawl.isEndOfWord = true;
    }
 
    // Returns true if key presents in trie, else
    // false
    static boolean search(TrieNode root, String key)
    {
        TrieNode pCrawl = root;
 
        for (int i = 0; i < key.length(); i++) {
            int index = key.charAt(i) - 'a';
            if (pCrawl.children[index] == null)
                return false;
 
            pCrawl = pCrawl.children[index];
        }
 
        return (pCrawl != null && pCrawl.isEndOfWord);
    }
 
    // Returns true if root has no children, else false
    static boolean isEmpty(TrieNode root)
    {
        for (int i = 0; i < ALPHABET_SIZE; i++)
            if (root.children[i] != null)
                return false;
        return true;
    }
 
    // Recursive function to delete a key from given Trie
    static TrieNode remove(TrieNode root, String key, int depth)
    {
        // If tree is empty
        if (root == null)
            return null;
 
        // If last character of key is being processed
        if (depth == key.length()) {
 
            // This node is no more end of word after
            // removal of given key
            if (root.isEndOfWord)
                root.isEndOfWord = false;
 
            // If given is not prefix of any other word
            if (isEmpty(root)) {
                root = null;
            }
 
            return root;
        }
 
        // If not last character, recur for the child
        // obtained using ASCII value
        int index = key.charAt(depth) - 'a';
        root.children[index] =
            remove(root.children[index], key, depth + 1);
 
        // If root does not have any child (its only child got
        // deleted), and it is not end of another word.
        if (isEmpty(root) && root.isEndOfWord == false){
            root = null;
        }
 
        return root;
    }
 
    // Driver
    public static void main(String args[])
    {
        // Input keys (use only 'a' through 'z'
        // and lower case)
        String keys[] = { "the", "a", "there",
                        "answer", "any", "by",
                        "bye", "their", "hero", "heroplane" };
        int n = keys.length;
 
        TrieNode root = new TrieNode();
 
        // Construct trie
        for (int i = 0; i < n; i++)
            insert(root, keys[i]);
 
        // Search for different keys
        if(search(root, "the"))
            System.out.println("Yes");
        else
            System.out.println("No");
 
        if(search(root, "these"))
            System.out.println("Yes");
        else
            System.out.println("No");
 
        remove(root, "heroplane", 0);
         
        if(search(root, "hero"))
            System.out.println("Yes");
        else
            System.out.println("No");
 
    }
}
 
// This code is contributed by aditypande88.

<script>
// Javascript implementation of delete
// operations on Trie
 
let ALPHABET_SIZE = 26;
 
// trie node
class TrieNode
{
    constructor()
    {
        this.children=new Array(ALPHABET_SIZE);
        this.isEndOfWord=false;
    }
}
 
// If not present, inserts key into trie
    // If the key is prefix of trie node, just
    // marks leaf node
function insert(root,key)
{
    let pCrawl = root;
  
        for (let i = 0; i < key.length; i++) {
            let index = key[i].charCodeAt(0) - 'a'.charCodeAt(0);
            if (pCrawl.children[index] == null)
                pCrawl.children[index] = new TrieNode();
  
            pCrawl = pCrawl.children[index];
        }
  
        // mark last node as leaf
        pCrawl.isEndOfWord = true;
}
 
// Returns true if key presents in trie, else
    // false
function search(root,key)
{
    let pCrawl = root;
  
        for (let i = 0; i < key.length; i++) {
            let index = key[i].charCodeAt(0) - 'a'.charCodeAt(0);
            if (pCrawl.children[index] == null)
                return false;
  
            pCrawl = pCrawl.children[index];
        }
  
        return (pCrawl != null && pCrawl.isEndOfWord);
}
 
// Returns true if root has no children, else false
function isEmpty(root)
{
    for (let i = 0; i < ALPHABET_SIZE; i++)
            if (root.children[i] != null)
                return false;
        return true;
}
 
// Recursive function to delete a key from given Trie
function remove(root,key,depth)
{
    // If tree is empty
        if (root == null)
            return null;
  
        // If last character of key is being processed
        if (depth == key.length) {
  
            // This node is no more end of word after
            // removal of given key
            if (root.isEndOfWord)
                root.isEndOfWord = false;
  
            // If given is not prefix of any other word
            if (isEmpty(root)) {
                root = null;
            }
  
            return root;
        }
  
        // If not last character, recur for the child
        // obtained using ASCII value
        let index = key[depth].charCodeAt(0) - 'a'.charCodeAt(0);
        root.children[index] =
            remove(root.children[index], key, depth + 1);
  
        // If root does not have any child (its only child got
        // deleted), and it is not end of another word.
        if (isEmpty(root) && root.isEndOfWord == false){
            root = null;
        }
  
        return root;
}
 
// Driver
// Input keys (use only 'a' through 'z'
// and lower case)
let keys = [ "the", "a", "there",
                 "answer", "any", "by",
                 "bye", "their", "hero", "heroplane" ];
let n = keys.length;
 
let root = new TrieNode();
 
// Construct trie
for (let i = 0; i < n; i++)
    insert(root, keys[i]);
 
// Search for different keys
if(search(root, "the"))
    document.write("Yes<br>");
else
    document.write("No<br>");
 
if(search(root, "these"))
    document.write("Yes<br>");
else
    document.write("No<br>");
 
remove(root, "heroplane", 0);
 
if(search(root, "hero"))
    document.write("Yes<br>");
else
    document.write("No<br>");
 
 
// This code is contributed by patel2127
</script>