using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace TrieRWayTree
{
public interface IContainer
{
void MakeEmpty();
bool Empty();
int Size();
}
//————————————————————————-
public interface ITrie
{
bool Insert(string key, T value);
bool Remove(string key);
T Value(string key);
}
//————————————————————————-
class Trie
{
private Node root; // Root node of the Trie
private class Node
{
public T value; // Value associated with a key; otherwise default
public int numValues; // Number of descendent values of a Node
public Node[] child; // Branch for each letter ‘a’ .. ‘z’
// Node
// Creates an empty Node
// All children are set to null by default
// Time complexity: O(1)
public Node()
{
value = default(T);
numValues = 0;
child = new Node[26];
}
}
// Trie
// Creates an empty Trie
// Time complexity: O(1)
public Trie()
{
MakeEmpty();
}
// Public Insert
// Calls the private Insert which carries out the actual insertion
// Returns true if successful; false otherwise
public bool Insert(string key, T value)
{
return Insert(root, key, 0, value);
}
// Private Insert
// Inserts the key/value pair into the Trie
// Returns true if the insertion was successful; false otherwise
// Note: Duplicate keys are ignored
// Time complexity: O(L) where L is the length of the key
private bool Insert(Node p, string key, int j, T value)
{
int i;
if (j == key.Length)
{
if (p.value.Equals(default(T)))
{
// Sets the value at the Node
p.value = value;
p.numValues++;
return true;
}
// Duplicate keys are ignored (unsuccessful insertion)
else
return false;
}
else
{
// Maps a character to an index
i = Char.ToLower(key[j]) – ‘a’;
// Creates a new Node if the link is null
// Note: Node is initialized to the default value
if (p.child[i] == null)
p.child[i] = new Node();
// If the inseration is successful
if (Insert(p.child[i], key, j + 1, value))
{
// Increase number of descendant values by one
p.numValues++;
return true;
}
else
return false;
}
}
// Value
// Returns the value associated with a key; otherwise default
// Time complexity: O(min(L,M)) where L is the length of the given key and
// M is the maximum length of a key in the trie
public T Value(string key)
{
int i;
Node p = root;
// Traverses the links character by character
foreach (char ch in key)
{
i = Char.ToLower(ch) – ‘a’;
if (p.child[i] == null)
return default(T); // Key is too long
else
p = p.child[i];
}
return p.value; // Returns the value or default
}
// Public Remove
// Calls the private Remove that carries out the actual deletion
// Returns true if successful; false otherwise
public bool Remove(string key)
{
return Remove(root, key, 0);
}
// Private Remove
// Removes the value associated with the given key
// Time complexity: O(min(L,M)) where L is the length of the key
// where M is the maximum length of a key in the trie
private bool Remove(Node p, string key, int j)
{
int i;
// Key not found
if (p == null)
return false;
else if (j == key.Length)
{
// Key/value pair found
if (!p.value.Equals(default(T)))
{
p.value = default(T);
p.numValues–;
return true;
}
// No value with associated key
else
return false;
}
else
{
i = Char.ToLower(key[j]) – ‘a’;
// If the deletion is successful
if (Remove(p.child[i], key, j + 1))
{
// Decrease number of descendent values by one and
// Remove Nodes with no remaining descendents
if (p.child[i].numValues == 0)
p.child[i] = null;
p.numValues–;
return true;
}
else
return false;
}
}
// MakeEmpty
// Creates an empty Trie
// Time complexity: O(1)
public void MakeEmpty()
{
root = new Node();
}
// Empty
// Returns true if the Trie is empty; false otherwise
// Time complexity: O(1)
public bool Empty()
{
return root.numValues == 0;
}
// Size
// Returns the number of Trie values
// Time complexity: O(1)
public int Size()
{
return root.numValues;
}
// Public Print
// Calls private Print to carry out the actual printing
public void Print()
{
Print(root,””);
}
// Private Print
// Outputs the key/value pairs ordered by keys
// Time complexity: O(n) where n is the number of nodes in the trie
private void Print(Node p, string key)
{
int i;
if (p != null)
{
if (!p.value.Equals(default(T)))
Console.WriteLine(key + ” ” + p.value + ” ” + p.numValues);
for (i = 0; i < 26; i++)
Print(p.child[i], key+(char)(i+'a'));
}
}
}
class Program
{
static void Main(string[] args)
{
Trie
T = new Trie
T.Insert(“abba”, 10);
T.Insert(“c”, 30);
T.Insert(“bc”, 50);
T.Insert(“bba”, 40);
T.Insert(“ab”, 20);
T.Insert(“cbc”, 30);
T.Print();
T.Remove(“ab”);
T.Remove(“abba”);
T.Remove(“cc”);
T.Remove(“bb”);
T.Print();
Console.ReadKey();
}
}
}