Skip to content

Instantly share code, notes, and snippets.

@kp96
Created December 7, 2015 12:47
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kp96/6636962a921de0b46d42 to your computer and use it in GitHub Desktop.
Save kp96/6636962a921de0b46d42 to your computer and use it in GitHub Desktop.
Trie datastructure simple implementation of insert and delete in java
//import java.util.*;
public class Trie {
private static final int ALPHABET_SIZE = 26;
private TrieNode root;
private int count;
public Trie() {
this.root = new TrieNode();
this.count = 0;
}
public void insert(String key) {
this.count++;
TrieNode cur = this.root;
for (int i = 0; i < key.length(); i++) {
int idx = (int) key.charAt(i) - (int) 'a';
if(cur.children[idx] == null) {
cur.children[idx] = new TrieNode();
}
cur = cur.children[idx];
}
cur.value = this.count;
}
public boolean search(String key) {
TrieNode cur = this.root;
for (int i = 0; i < key.length(); i++) {
int idx = (int) key.charAt(i) - (int) 'a';
if(cur.children[idx] == null) {
return false;
}
cur = cur.children[idx];
}
if(cur.value != 0 && cur != null)
return true;
return false;
}
private static class TrieNode {
int value;
TrieNode[] children;
public TrieNode() {
this.value = 0;
this.children = new TrieNode[ALPHABET_SIZE];
for(int i = 0; i < ALPHABET_SIZE; i++)
this.children[i] = null;
}
}
}
// class Test {
// public static void main(String[] args) {
// Trie trie = new Trie();
// trie.insert("hello");
// trie.insert("hi");
// trie.insert("newyork");
// System.out.println(trie.search("hello") + " " +
// trie.search("hi") + " "+ trie.search("newyork"));
// }
// }
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment