Skip to main content

Trie Deletion

Trie Node Deletion

Here given code implementation process.

/*
  C++ program
  Trie Deletion
*/

#include <iostream>

#include <string.h>

#define ALPHABETS 26

using namespace std;

class Node {
  public:
    bool end;
    Node *children[ALPHABETS];
    Node() {
      this->end = false;
      for (int i = 0; i < ALPHABETS; ++i) {
        this->children[i] = NULL;
      }
    }
};
class Trie {
  public:

    Node *root;
    Trie() {
      this->root = new Node();
    }
    //Search given text is exist in tire
    bool search(string text) {
      int length = text.size();
      int index = 0;
      Node *head = this->root;
      for (int level = 0; level < length; level++) {
        index = text[level] - 'a';
        if (head->children[index] == NULL) {
          return false;
        }
        head = head->children[index];
      }
      if (head != NULL && head->end == true) {
        return true;
      } else {
        return false;
      }
    }

    void insert(string text) {
      int length = text.size();
      int index = 0;
      Node *head = this->root;
      for (int level = 0; level < length; level++) {
        index = text[level] - 'a';
        if (head->children[index] == NULL) {
          head->children[index] = new Node();
        }
        head = head->children[index];
      }
      if (head != NULL) {
        //indicates end of string
        head->end = true;
      }
    }
    bool emptyNode(Node *root) {
      for (int i = 0; i < ALPHABETS; i++) {
        if (root->children[i] != NULL) {
          return false;
        }
      }
      return true;
    }
    Node *lastNode(string text) {
      int length = text.size();
      int index = 0;
      Node *head = this->root;
      for (int level = 0; level < length; level++) {
        index = text[level] - 'a';
        if (head->children[index] == NULL) {
          return NULL;
        }
        head = head->children[index];
      }
      if (head != NULL && head->end == true) {
        return head;
      } else {
        return NULL;
      }
    }


    //This method are handle the request of deleted text in trie tree
    Node *deleteNode(string text, Node *root, int level) {
      if (root != NULL) {
        if (level == text.size()) {
          if (this->emptyNode(root)) {
            return NULL;
          }
          return root;
        }
        int index = text[level] - 'a';
        root->children[index] = this->deleteNode(text, root->children[index], level + 1);
        if (root->end == false && this->emptyNode(root)) {
          return NULL;
        }
      }
      return root;
    }

    void deleteText(string text) {
      Node *last = this->lastNode(text);
      if (last != NULL) {
        if (this->emptyNode(last)) {
          this->deleteNode(text, this->root, 0);
        } else {
          last->end = false;
        }
        cout << "Delete Text " << text << endl;
      } else {
        cout << "Not Exist Delete Text String : " << text << endl;
      }
    }
};

int main() {
  Trie obj;
  obj.insert("cooky");
  obj.insert("cool");
  string text = "cooky";
  if (obj.search(text)) {
    cout << "Exist : " << text << endl;
  } else {
    cout << "Not Exist : " << text << endl;
  }
  obj.deleteText("cooky");
  if (obj.search(text)) {
    cout << "Exist : " << text << endl;
  } else {
    cout << "Not Exist : " << text << endl;
  }
  return 0;
}

Output

Exist : cooky
Delete Text cooky
Not Exist : cooky

/*
  Java program
  Trie Deletion
*/

class Node {
  //Indicates end of string
  public boolean end;

  public Node[] children;

  public Node(int size) {
    end = false;
    children = new Node[size];
  }
}
public class Trie {

  public int ALPHABETS = 26;

  public Node root;

  public Trie() {
    root = new Node(ALPHABETS);
  }
  //Search given text is exist in tire
  public boolean search(String text) {
    //first get the length of text
    int length = text.length();

    //This variable are used to task find the index location of character
    int index = 0;

    //get the root node
    Node head = root;

    for (int level = 0; level < length; level++) {
      //Get the index
      index = text.charAt(level) - 'a';

      if (head.children[index] == null) {
        return false;
      }

      head = head.children[index];
    }
    if (head != null && head.end == true) {
      return true;
    } else {
      return false;
    }
  }
  public void insert(String text) {
    //First get the length of text
    int length = text.length();

    //This variable are used to task find the index location of character
    int index = 0;

    //Get the root node
    Node head = root;

    for (int level = 0; level < length; level++) {
      //Get the index
      index = text.charAt(level) - 'a';

      if (head.children[index] == null) {
        //When need to add new Node
        head.children[index] = new Node(ALPHABETS);
      }

      head = head.children[index];
    }
    if (head != null) {
      //indicates end of string
      head.end = true;
    }
  }
  public boolean emptyNode(Node root) {

    for (int i = 0; i < ALPHABETS; i++) {
      if (root.children[i] != null) {
        return false;
      }
    }
    return true;
  }
  //Search given text is exist in tire
  public Node lastNode(String text) {
    //first get the length of text
    int length = text.length();

    //This variable are used to task find the index location of character
    int index = 0;

    //get the root node
    Node head = root;

    for (int level = 0; level < length; level++) {
      //Get the index
      index = text.charAt(level) - 'a';

      if (head.children[index] == null) {
        return null;
      }

      head = head.children[index];
    }
    if (head != null && head.end == true) {
      return head;
    } else {
      return null;
    }
  }
  public Node deleteNode(String text, Node root, int level) {

    if (root != null) {

      //if get last node of string
      if (level == text.length()) {

        if (emptyNode(root)) {
          return null;
        }
        return root;
      }

      int index = text.charAt(level) - 'a';

      root.children[index] =
        deleteNode(text, root.children[index], level + 1);

      if (root.end == false && emptyNode(root)) {
        return null;
      }

    }
    return root;

  }
  //This method are handle the request of deleted text in trie tree
  public void delete(String text) {
    //Get last node of deleted text
    Node last = lastNode(text);

    if (last != null) {

      if (emptyNode(last)) {
        //If last node of deleted text is not a part of other text string
        deleteNode(text, root, 0);
      } else {
        last.end = false;
      }

      System.out.println("Delete Text " + text);
    } else {
      //When node element are not exist
      System.out.println("Not Exist Delete Text String : " + text);
    }
  }
  public static void main(String[] args) {
    //Make object
    Trie obj = new Trie();

    obj.insert("cooky");
    obj.insert("cool");

    String text = "cooky";

    if (obj.search(text)) {
      System.out.println("Exist : " + text);
    } else {
      System.out.println("Not Exist : " + text);
    }

    obj.delete("cooky");

    //After Delete
    if (obj.search(text)) {
      System.out.println("Exist : " + text);
    } else {
      System.out.println("Not Exist : " + text);
    }
  }
}

Output

Exist : cooky
Delete Text cooky
Not Exist : cooky
Trie Delete Node 
#Python Code
#Trie Deletion
class Node :

  def __init__(self,size) :
    self.end = False
    self.children = [None] * size
  

class Trie :
 
  def __init__(self) :
    self.ALPHABETS = 26
    self.root = Node(self.ALPHABETS)
  
  def search(self,text) :
    length = len(text)
    index = 0
    head = self.root
    level = 0
    while ( level < length ) :
      index =  ord(text[level]) - ord('a')
      if (head.children[index] == None) :
        return False
      
      head = head.children[index]
      level += 1
    if (head != None and head.end == True) :
      return True
    else :
      return False
    
  
  def insert(self,text) :
    length = len(text)
    index = 0
    head = self.root
    level = 0
    while ( level < length ) :
      index =  ord(text[level]) - ord('a')
      if (head.children[index] == None) :
        head.children[index] = Node(self.ALPHABETS)
      
      head = head.children[index]
      level += 1
    if (head != None) :
      head.end = True
    
  
  def emptyNode(self,root) :
    i = 0
    while ( i < self.ALPHABETS ) :
      if (self.root.children[i] != None) :
        return False
      i += 1
    
    return True
  
  def lastNode(self,text) :
    length = len(text)
    index = 0
    head = self.root
    level = 0
    while ( level < length ) :
      index = ord(text[level]) - ord('a')
      if (head.children[index] == None) :
        return None
      
      head = head.children[index]
      level += 1
    if (head != None and head.end == True) :
      return head
    else :
      return None
    
  
  def deleteNode(self,text, root, level) :
    if (self.root != None) :
      if (level == len(text)) :
        if (self.emptyNode(self.root)) :
          return None
        
        return self.root
      
      index = ord(text[level]) - ord('a')
      self.root.children[index] = self.deleteNode(text, self.root.children[index], level + 1)
      if (self.root.end == False and self.emptyNode(self.root)) :
        return None
      
    
    return self.root
  
  def delete(self,text) :
    last = self.lastNode(text)
    if (last != None) :
      if (self.emptyNode(last)) :
        self.deleteNode(text, self.root, 0)
      else :
        last.end = False
      
      print("Delete Text ", text)
    else :
      print("Not Exist Delete Text String : ", text)
    
  
def main() :
  obj = Trie()
  obj.insert("cooky")
  obj.insert("cool")
  text = "cooky"
  if (obj.search(text)) :
    print("Exist : ", text)
  else :
    print("Not Exist : ", text)
  
  obj.delete("cooky")
  if (obj.search(text)) :
    print("Exist : ", text)
  else :
    print("Not Exist : ", text)
    
  

if __name__ == "__main__":
  main()

Output

Exist :  cooky
Delete Text  cooky
Not Exist :  cooky

/*
  C# program
  Trie Deletion
*/
using System;
public class Node {
  //Indicates end of string
  public Boolean end;

  public Node[] children;

  public Node(int size) {
    end = false;
    children = new Node[size];
  }
}
public class Trie {

  public int ALPHABETS = 26;

  public Node root;

  public Trie() {
    root = new Node(ALPHABETS);
  }
  //Search given text is exist in tire
  public Boolean search(String text) {
    //first get the.Length of text
    int length = text.Length;

    //This variable are used to task find the index location of character
    int index = 0;

    //get the root node
    Node head = root;

    for (int level = 0; level < length; level++) {
      //Get the index
      index = text[level] - 'a';

      if (head.children[index] == null) {
        return false;
      }

      head = head.children[index];
    }
    if (head != null && head.end == true) {
      return true;
    } else {
      return false;
    }
  }
  public void insert(String text) {
    //First get the.Length of text
    int length = text.Length;

    //This variable are used to task find the index location of character
    int index = 0;

    //Get the root node
    Node head = root;

    for (int level = 0; level < length; level++) {
      //Get the index
      index = text[level] - 'a';

      if (head.children[index] == null) {
        //When need to add new Node
        head.children[index] = new Node(ALPHABETS);
      }

      head = head.children[index];
    }
    if (head != null) {
      //indicates end of string
      head.end = true;
    }
  }
  public Boolean emptyNode(Node root) {

    for (int i = 0; i < ALPHABETS; i++) {
      if (root.children[i] != null) {
        return false;
      }
    }
    return true;
  }
  //Search given text is exist in tire
  public Node lastNode(String text) {
    //first get the.Length of text
    int length = text.Length;

    //This variable are used to task find the index location of character
    int index = 0;

    //get the root node
    Node head = root;

    for (int level = 0; level < length; level++) {
      //Get the index
      index = text[level] - 'a';

      if (head.children[index] == null) {
        return null;
      }

      head = head.children[index];
    }
    if (head != null && head.end == true) {
      return head;
    } else {
      return null;
    }
  }
  public Node deleteNode(String text, Node root, int level) {

    if (root != null) {

      //if get last node of string
      if (level == text.Length) {

        if (emptyNode(root)) {
          return null;
        }
        return root;
      }

      int index = text[level] - 'a';

      root.children[index] =
        deleteNode(text, root.children[index], level + 1);

      if (root.end == false && emptyNode(root)) {
        return null;
      }

    }
    return root;

  }
  //This method are handle the request of deleted text in trie tree
  public void delete(String text) {
    //Get last node of deleted text
    Node last = lastNode(text);

    if (last != null) {

      if (emptyNode(last)) {
        //If last node of deleted text is not a part of other text string
        deleteNode(text, root, 0);
      } else {
        last.end = false;
      }

      Console.WriteLine("Delete Text " + text);
    } else {
      //When node element are not exist
      Console.WriteLine("Not Exist Delete Text String : " + text);
    }
  }
  public static void Main(String[] args) {
    //Make object
    Trie obj = new Trie();

    obj.insert("cooky");
    obj.insert("cool");

    String text = "cooky";

    if (obj.search(text)) {
      Console.WriteLine("Exist : " + text);
    } else {
      Console.WriteLine("Not Exist : " + text);
    }

    obj.delete("cooky");

    //After Delete
    if (obj.search(text)) {
      Console.WriteLine("Exist : " + text);
    } else {
      Console.WriteLine("Not Exist : " + text);
    }
  }
}

Output

Exist : cooky
Delete Text cooky
Not Exist : cooky

<?php

/*
  Php program
  Trie Deletion
*/
class Node {
  public $end;
  public $children;

  function __construct($size) {
    $this->end = false;
    $this->children = array_fill(0, $size, NULL);
  }
}
class Trie {
  public $ALPHABETS = 26;
  public $root;

  function __construct() {
    $this->root = new Node($this->ALPHABETS);
  }
  public function search($text) {
    $length = strlen($text);
    $index = 0;
    $head = $this->root;
    for ($level = 0; $level < $length; $level++) {
      $index = ord($text[$level]) - ord('a');
      if ($head->children[$index] == null) {
        return false;
      }
      $head = $head->children[$index];
    }
    if ($head != null && $head->end == true) {
      return true;
    } else {
      return false;
    }
  }
  public function insert($text) {
    $length = strlen($text);
    $index = 0;
    $head = $this->root;
    for ($level = 0; $level < $length; $level++) {
      $index = ord($text[$level]) - ord('a');
      if ($head->children[$index] == null) {
        $head->children[$index] = new Node($this->ALPHABETS);
      }
      $head = $head->children[$index];
    }
    if ($head != null) {
      $head->end = true;
    }
  }
  public function emptyNode($root) {
    for ($i = 0; $i < $this->ALPHABETS; $i++) {
      if ($this->root->children[$i] != null) {
        return false;
      }
    }
    return true;
  }
  public function lastNode($text) {
    $length = strlen($text);
    $index = 0;
    $head = $this->root;
    for ($level = 0; $level < $length; $level++) {
      $index = ord($text[$level]) - ord('a');
      if ($head->children[$index] == null) {
        return null;
      }
      $head = $head->children[$index];
    }
    if ($head != null && $head->end == true) {
      return $head;
    } else {
      return null;
    }
  }
  public function deleteNode($text, $root, $level) {
    if ($this->root != null) {
      if ($level == strlen($text)) {
        if ($this->emptyNode($this->root)) {
          return null;
        }
        return $this->root;
      }
      $index = ord($text[$level]) - ord('a');
      $this->root->children[$index] = $this->deleteNode($text, $this->root->children[$index], $level + 1);
      if ($this->root->end == false && $this->emptyNode($this->root)) {
        return null;
      }
    }
    return $this->root;
  }
  public function delete($text) {
    $last = $this->lastNode($text);
    if ($last != null) {
      if ($this->emptyNode($last)) {
        $this->deleteNode($text, $this->root, 0);
      } else {
        $last->end = false;
      }
      echo("Delete Text $text\n");
    } else {
      echo("Not Exist Delete Text String : $text\n");
    }
  }
}
function main() {
  $obj = new Trie();
  $obj->insert("cooky");
  $obj->insert("cool");
  $text = "cooky";
  if ($obj->search($text)) {
    echo ("Exist : $text\n");
  } else {
    echo("Not Exist : $text \n");
  }
  $obj->delete("cooky");
  if ($obj->search($text)) {
    echo("Exist : $text\n");
  } else {
    echo("Not Exist : $text\n");
  }
}
main();

Output

Exist : cooky
Delete Text cooky
Not Exist : cooky

#
#  Ruby program
#  Trie Deletion
#
class Node 
  attr_reader :end, :children
  attr_accessor :end, :children
  def initialize(size) 
    @end = false
    @children =  Array.new(size){nil}
  end
end

class Trie 
  attr_reader :ALPHABETS, :root
  attr_accessor :ALPHABETS, :root
  def initialize() 
    @ALPHABETS = 26
    @root = Node.new(@ALPHABETS)
  end
  def search(text) 
    length = text.length
    location = 0
    head = @root
    level = 0
    while ( level < length ) do
      location = text[level].ord-'a'.ord
      if (head.children[location] == nil) 
        return false
      end
      head = head.children[location]

      level += 1
    end
    if (head != nil and head.end == true) 
      return true
    else 
      return false
    end
  end
  def insert(text) 
    length = text.length
    location = 0
    head = @root
    level = 0
    while ( level < length ) 
      location = text[level].ord-'a'.ord
      if (head.children[location] == nil) 
        head.children[location] = Node.new(@ALPHABETS)
      end
      head = head.children[location]

      level += 1
    end
    if (head != nil) 
      head.end = true
    end
  end
  def emptyNode(root) 
    i = 0
    while ( i < @ALPHABETS ) 
      if (@root.children[i] != nil) 
        return false
      end
      i += 1
    end
    return true
  end
  def lastNode(text) 
    length = text.length
    location = 0
    head = @root
    level = 0
    while ( level < length ) 
      location = text[level].ord-'a'.ord
      if (head.children[location] == nil) 
        return nil
      end
      head = head.children[location]
      level += 1
    end
    if (head != nil and head.end == true) 
      return head
    else 
      return nil
    end
  end
  def deleteNode(text, root, level) 
    if (@root != nil) 
      if (level == text.length) 
        if (self.emptyNode(@root)) 
          return nil
        end
        return @root
      end
      location = text[level].ord-'a'.ord
      @root.children[location] = self.deleteNode(text, @root.children[location], level + 1)
      if (@root.end == false and self.emptyNode(@root)) 
        return nil
      end
    end
    return @root
  end
  def delete(text) 
    last = self.lastNode(text)
    if (last != nil) 
      if (self.emptyNode(last)) 
        self.deleteNode(text, @root, 0)
      else 
        last.end = false
      end
      print("Delete Text " + text + "\n")
    else 
      print("Not Exist Delete Text String  :" + text + "\n")
    end
  end
end



def main() 
  obj = Trie.new()
  obj.insert("cooky")
  obj.insert("cool")
  text = "cooky"
  if (obj.search(text)) 
    print("Exist  :" + text + "\n")
  else 
    print("Not Exist  :" + text + "\n")
  end
  obj.delete("cooky")
  if (obj.search(text)) 
    print("Exist  :" + text + "\n")
  else 
    print("Not Exist  :" + text + "\n")
  end
end
main()

Output

Exist  :cooky
Delete Text cooky
Not Exist  :cooky

/*
  Node JS program
  Trie Deletion
*/
class Node {
  
  constructor(size) {
    this.end = false;
    this.children = new Array(size).fill(null);
  }
}
class Trie {
  
  constructor() {
    this.ALPHABETS = 26;
    this.root = new Node(this.ALPHABETS);
  }
  search(text) {
    var length = text.length;
    var index = 0;
    var head = this.root;
    for (var level = 0; level < length; level++) {
      index = text.charCodeAt(level) - 'a'.charCodeAt(0);
      if (head.children[index] == null) {
        return false;
      }
      head = head.children[index];
    }
    if (head != null && head.end == true) {
      return true;
    } else {
      return false;
    }
  }
  insert(text) {
    var length = text.length;
    var index = 0;
    var head = this.root;
    for (var level = 0; level < length; level++) {
      index = text.charCodeAt(level) - 'a'.charCodeAt(0);
      if (head.children[index] == null) {
        head.children[index] = new Node(this.ALPHABETS);
      }
      head = head.children[index];
    }
    if (head != null) {
      head.end = true;
    }
  }
  emptyNode(root) {
    for (var i = 0; i < this.ALPHABETS; i++) {
      if (this.root.children[i] != null) {
        return false;
      }
    }
    return true;
  }
  lastNode(text) {
    var length = text.length;
    var index = 0;
    var head = this.root;
    for (var level = 0; level < length; level++) {
      index = text.charCodeAt(level) - 'a'.charCodeAt(0);
      if (head.children[index] == null) {
        return null;
      }
      head = head.children[index];
    }
    if (head != null && head.end == true) {
      return head;
    } else {
      return null;
    }
  }
  deleteNode(text, root, level) {
    if (this.root != null) {
      if (level == text.Length) {
        if (this.emptyNode(this.root)) {
          return null;
        }
        return this.root;
      }
      var index = text.charCodeAt(level) - 'a'.charCodeAt(0);
      this.root.children[index] = this.deleteNode(text, this.root.children[index], level + 1);
      if (this.root.end == false && this.emptyNode(this.root)) {
        return null;
      }
    }
    return this.root;
  }
  delete(text) {
    var last = this.lastNode(text);
    if (last != null) {
      if (this.emptyNode(last)) {
        this.deleteNode(text, this.root, 0);
      } else {
        last.end = false;
      }
      console.log ("Delete Text " + text);
    } else {
      console.log ("Not Exist Delete Text String : " + text);
    }
  }

}

function main() {
  var obj = new Trie();
  obj.insert("cooky");
  obj.insert("cool");
  var text = "cooky";
  if (obj.search(text)) {
    console.log ("Exist : " + text);
  } else {
    console.log ("Not Exist : " + text);
  }
  obj.delete("cooky");
  if (obj.search(text)) {
    console.log ("Exist : " + text);
  } else {
    console.log ("Not Exist : " + text);
  }
}
main();

Output

Exist : cooky
Delete Text cooky
Not Exist : cooky
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment