자바

class Node{
	HashMap<Character, Node> child;
    boolean isTerminal;
}

class Node{
    HashMap<Character, Node> child;
    boolean isTerminal;

    public Node(){
        this.child = new HashMap<>();
        isTerminal = false;
    }
}

class Trie{
    Node root;
    public Trie(){
        this.root = new Node();
    }

    public void insert(String str){
        Node cur = this.root;

        for(int i = 0; i < str.length(); i++){
            char c = str.charAt(i);

            cur.child.putIfAbsent(c, new Node());
            cur = cur.child.get(c);

            if(i == str.length() - 1){
                cur.isTerminal = true;
                return;
            }
        }
    }

    public boolean search(String str){
        Node cur = this.root;

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);

            if(cur.child.containsKey(c)){
                cur = cur.child.get(c);
            }else{
                return false;
            }

            if(i == str.length() - 1){
                if(!cur.isTerminal){
                    return false;
                }
            }
        }
        return true;
    }

    public void delete(String str){
        boolean ret = this.delete(this.root, str, 0);
        if(ret){
            System.out.println(str + " 삭제 완료");
        }else{
            System.out.println(str + "단어가 없습니다.");
        }
    }

    public boolean delete(Node node, String str, int idx){
        char c = str.charAt(idx);

        if(!node.child.containsKey(c)){
            return false;
        }

        Node cur = node.child.get(c);
        idx++;

        if(idx == str.length()){
            if(!cur.isTerminal){
                return false;
            }

            cur.isTerminal = false;

            if(cur.child.isEmpty()){
                node.child.remove(c);
            }
        }else{
            // 지워야 하는 문자 찾기 전
            if(!this.delete(cur, str, idx)){
                return false;
            }

            if(!cur.isTerminal && cur.child.isEmpty()){
                node.child.remove(c);
            }
        }
        return true;
    }
}

실행

public class Main {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        trie.insert("april");
        trie.insert("app"); // 이부분 주석처리하면 밑에서 false;
        trie.insert("ace");
        trie.insert("bear");
        trie.insert("best");
        System.out.println(trie.search("apple"));
        System.out.println(trie.search("april"));
        System.out.println(trie.search("app"));
        System.out.println(trie.search("ace"));
        System.out.println(trie.search("bear"));
        System.out.println(trie.search("best"));
        System.out.println(trie.search("abc")); // 혼자 false;

        System.out.println();
        trie.delete("apple");
        System.out.println(trie.search("apple")); // false
        System.out.println(trie.search("april"));
        System.out.println(trie.search("appl")); // false
        trie.delete("apple");
    }
}

JS

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let current = this.root;

    for (let i = 0; i < word.length; i++) {
      const ch = word[i];
      let node = current.children[ch];

      if (!node) {
        node = new TrieNode();
        current.children[ch] = node;
      }

      current = node;
    }

    current.isEndOfWord = true;
  }

  search(word) {
    let current = this.root;

    for (let i = 0; i < word.length; i++) {
      const ch = word[i];
      const node = current.children[ch];

      if (!node) {
        return false;
      }

      current = node;
    }

    return current.isEndOfWord;
  }

  startsWith(prefix) {
    let current = this.root;

    for (let i = 0; i < prefix.length; i++) {
      const ch = prefix[i];
      const node = current.children[ch];

      if (!node) {
        return false;
      }

      current = node;
    }

    return true;
  }
  
  delete(word) {
    this._delete(this.root, word, 0);
  }

  _delete(node, word, index) {
    if (index === word.length) {
      if (!node.isEndOfWord) {
        return false;
      }

      node.isEndOfWord = false;

      // Check if the node has no children, if so, remove it.
      return Object.keys(node.children).length === 0;
    }

    const ch = word[index];
    const childNode = node.children[ch];

    if (!childNode) {
      return false;
    }

    const shouldDeleteChildNode = this._delete(childNode, word, index + 1);

    if (shouldDeleteChildNode) {
      delete node.children[ch];

      // Check if the node has no children, if so, remove it.
      return Object.keys(node.children).length === 0;
    }

    return false;
  }
}

실행

const trie = new Trie();
trie.insert("apple");
console.log(trie.search("apple")); // true
console.log(trie.search("app")); // false
console.log(trie.startsWith("app")); // true
trie.insert("app");
console.log(trie.search("app")); // true

trie.insert("appk");
trie.delete("appk");
console.log(trie.search("app")); // true
console.log(trie.search("appk")); // true

Go

package main

import "fmt"

type TrieNode struct {
    children map[rune]*TrieNode
    isEndOfWord bool
}

type Trie struct {
    root *TrieNode
}

func NewTrie() *Trie {
    return &Trie{root: &TrieNode{children: make(map[rune]*TrieNode)}}
}

func (t *Trie) Insert(word string) {
    node := t.root
    for _, c := range word {
        child, ok := node.children[c]
        if !ok {
            fmt.Println("생성 :", string(c))
            child = &TrieNode{children: make(map[rune]*TrieNode)}
            node.children[c] = child
        }
        node = child
    }
    node.isEndOfWord = true
}

func (t *Trie) Search(word string) bool {
    node := t.root
    for _, c := range word {
        child, ok := node.children[c]
        if !ok {
            return false
        }
        node = child
    }
    return node.isEndOfWord
}

func (t *Trie) StartsWith(prefix string) bool {
    node := t.root
    for _, c := range prefix {
        child, ok := node.children[c]
        if !ok {
            return false
        }
        node = child
    }
    return true
}

func main() {
	trie := NewTrie()
    trie.Insert("apple")
    fmt.Println(trie.Search("apple")) // true
    fmt.Println(trie.Search("app")) // false
    fmt.Println(trie.StartsWith("app")) // true
    trie.Insert("app")
    fmt.Println(trie.Search("app")) // true
    trie.Insert("appk")

}