Radix tree implementation
In data structure, radix tree is a optimized version of a trie. Generally of Trie tree is capable to hold a single character. But radix tree is capable to store hole word.
Implementation
Given collection of words, Our goal is to using of this word construct a valid radix tree. Suppose following data are inserting in radix tree ["romane", "romanus", "romulus", "rubens", "ruber", "rubicon", "rubicundus"]. This example taken from wikipedia.

import java.util.Vector;
// Java Program for
// Radix tree insert
class TreeNode
{
public String label;
public Vector < TreeNode > child;
public TreeNode()
{
this.label = "";
this.child = new Vector < TreeNode > ();
}
public TreeNode(String value)
{
this.label = value;
this.child = new Vector < TreeNode > ();
}
}
public class RadixTree
{
public TreeNode root;
public RadixTree()
{
this.root = new TreeNode("");
}
private int matchingCharacters(String word, TreeNode node)
{
int matches = 0;
int minLength = 0;
if (node.label.length() >= word.length())
{
minLength = word.length();
}
else if (node.label.length() < word.length())
{
minLength = node.label.length();
}
if (minLength > 0)
{
// Count matches characters
for (int i = 0; i < minLength; i++)
{
if (word.charAt(i) == node.label.charAt(i))
{
// When characters are same
matches++;
}
else
{
// When characters are not same
return matches;
}
}
}
// Return the current number of matches
return matches;
}
// Add node in proper place
private void insertProcess(String word, TreeNode node)
{
int matches = matchingCharacters(word, node);
if ((matches == 0) || (node == root) ||
((matches > 0) && (matches < word.length()) &&
(matches >= node.label.length())))
{
boolean inserted = false;
String newWordPart = word.substring(matches, word.length());
for (int i = 0; i < node.child.size(); ++i)
{
if (node.child.get(i).label.startsWith(
"" + newWordPart.charAt(0)))
{
inserted = true;
insertProcess(newWordPart, node.child.get(i));
}
}
if (inserted == false)
{
// Add new part
node.child.add(new TreeNode(newWordPart));
}
}
else if (matches < word.length())
{
String commonRoot = word.substring(0, matches);
String branchPreviouslabel = node.label.substring(
matches, node.label.length());
String branchNewlabel = word.substring(matches, word.length());
node.label = commonRoot;
TreeNode newNodePreviouslabel = new TreeNode(branchPreviouslabel);
// Add current node child to new node
for (int i = 0; i < node.child.size(); ++i)
{
newNodePreviouslabel.child.add(node.child.get(i));
}
// Clear node element
node.child.clear();
// Add new node
node.child.add(newNodePreviouslabel);
// Add branch new label
node.child.add(new TreeNode(branchNewlabel));
}
else if (matches > node.label.length())
{
String newLabel = node.label.substring(
node.label.length(), word.length());
// Add new label
node.child.add(new TreeNode(newLabel));
}
}
public void insert(String word)
{
this.insertProcess(word, this.root);
}
// Display the preorder of tree elements
public void printPreorder(TreeNode node)
{
if (node == null)
{
return;
}
// Display node value
System.out.println(node.label);
for (int i = 0; i < node.child.size(); ++i)
{
// Visit child node
printPreorder(node.child.get(i));
}
}
public static void main(String[] args)
{
RadixTree tree = new RadixTree();
// Add tree node
tree.insert("romane");
tree.insert("romanus");
tree.insert("romulus");
tree.insert("rubens");
tree.insert("ruber");
tree.insert("rubicon");
tree.insert("rubicundus");
/*
r
/ \
/ \
/ \
/ \
om ub
/ \ / \
an ulus e ic
/ \ / \ / \
e us ns r on undus
*/
System.out.print("Preorder Tree Data ");
// Print Tree nodes
tree.printPreorder(tree.root);
}
}
Output
Preorder Tree Data
r
om
an
e
us
ulus
ub
e
ns
r
ic
on
undus
package main
import "fmt"
import "strings"
// Go Program for
// Radix tree insert
type TreeNode struct {
label string
child [] *TreeNode
}
func getTreeNode(value string) * TreeNode {
var me *TreeNode = &TreeNode {}
me.label = value
me.child = make([] *TreeNode,0)
return me
}
type RadixTree struct {
root * TreeNode
}
func getRadixTree() * RadixTree {
var me *RadixTree = &RadixTree {}
me.root = getTreeNode("")
return me
}
func(this RadixTree) matchingCharacters(word string,
node * TreeNode) int {
var matches int = 0
var minLength int = 0
if len(node.label) >= len(word) {
minLength = len(word)
} else if len(node.label) < len(word) {
minLength = len(node.label)
}
if minLength > 0 {
// Count matches characters
for i := 0 ; i < minLength ; i++ {
if word[i] == node.label[i] {
// When characters are same
matches++
} else {
// When characters are not same
return matches
}
}
}
// Return the current number of matches
return matches
}
// Add node in proper place
func(this RadixTree) insertProcess(word string, node * TreeNode) {
var matches int = this.matchingCharacters(word, node)
if (matches == 0) || (node == this.root) || (
(matches > 0) && (matches < len(word)) && (
matches >= len(node.label))) {
var inserted bool = false
var newWordPart string = word[matches : len(word) ]
for i := 0 ; i < len(node.child) ; i++ {
if strings.HasPrefix(node.child[i].label,
string(newWordPart[0])) {
inserted = true
this.insertProcess(newWordPart, node.child[i])
}
}
if inserted == false {
// Add new part
node.child = append(node.child, getTreeNode(newWordPart))
}
} else if matches < len(word) {
var commonRoot string = word[0 : matches]
var branchPreviouslabel string = node.label[matches : len(node.label)]
var branchNewlabel string = word[matches : len(word)]
node.label = commonRoot
var newNodePreviouslabel * TreeNode = getTreeNode(branchPreviouslabel)
// Add current node child to new node
for i := 0 ; i < len(node.child) ; i++ {
newNodePreviouslabel.child = append(newNodePreviouslabel.child,
node.child[i])
}
// Clear node element
node.child = nil
// Add new node
node.child = append(node.child, newNodePreviouslabel)
// Add branch new label
node.child = append(node.child, getTreeNode(branchNewlabel))
} else if matches > len(node.label) {
var newLabel string = node.label[len(node.label) : len(word)]
// Add new label
node.child = append(node.child, getTreeNode(newLabel))
}
}
func(this RadixTree) insert(word string) {
this.insertProcess(word, this.root)
}
// Display the preorder of tree elements
func(this RadixTree) printPreorder(node * TreeNode) {
if node == nil {
return
}
// Display node value
fmt.Println(node.label)
for i := 0 ; i < len(node.child) ; i++ {
// Visit child node
this.printPreorder(node.child[i])
}
}
func main() {
var tree * RadixTree = getRadixTree()
// Add tree node
tree.insert("romane")
tree.insert("romanus")
tree.insert("romulus")
tree.insert("rubens")
tree.insert("ruber")
tree.insert("rubicon")
tree.insert("rubicundus")
/*
r
/ \
/ \
/ \
/ \
om ub
/ \ / \
an ulus e ic
/ \ / \ / \
e us ns r on undus
*/
fmt.Print("Preorder Tree Data ")
// Tree Tree nodes
tree.printPreorder(tree.root)
}
Output
Preorder Tree Data
r
om
an
e
us
ulus
ub
e
ns
r
ic
on
undus
// Include header file
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// C++ Program for
// Radix tree insert
class TreeNode
{
public: string label;
vector < TreeNode *> child;
TreeNode(){
this->label = "";
}
TreeNode(string value)
{
this->label = value;
}
};
class RadixTree
{
public: TreeNode *root;
RadixTree()
{
this->root = new TreeNode("");
}
int matchingCharacters(string word, TreeNode *node)
{
int matches = 0;
int minLength = 0;
if (node->label.length() >= word.length())
{
minLength = word.length();
}
else if (node->label.length() < word.length())
{
minLength = node->label.length();
}
if (minLength > 0)
{
// Count matches characters
for (int i = 0; i < minLength; i++)
{
if (word[i] == node->label[i])
{
// When characters are same
matches++;
}
else
{
// When characters are not same
return matches;
}
}
}
// Return the current number of matches
return matches;
}
// Add node in proper place
void insertProcess(string word, TreeNode *node)
{
int matches = this->matchingCharacters(word, node);
if ((matches == 0) || (node == this->root) ||
((matches > 0) && (matches < word.length()) &&
(matches >= node->label.length())))
{
bool inserted = false;
string newWordPart = word.substr(matches, word.length()-matches);
for (int i = 0; i < node->child.size(); ++i)
{
if (node->child.at(i)->label[0] == newWordPart[0])
{
inserted = true;
this->insertProcess(newWordPart, node->child.at(i));
}
}
if (inserted == false)
{
// Add new part
node->child.push_back(new TreeNode(newWordPart));
}
}
else if (matches < word.length())
{
string commonRoot = word.substr(0, matches);
string branchPreviouslabel = node->label.substr(matches, node->label.length()-matches);
string branchNewlabel = word.substr(matches, word.length()-matches);
node->label = commonRoot;
TreeNode *newNodePreviouslabel = new TreeNode(branchPreviouslabel);
// Add current node child to new node
for (int i = 0; i < node->child.size(); ++i)
{
newNodePreviouslabel->child.push_back(node->child.at(i));
}
// Clear node element
node->child.clear();
// Add new node
node->child.push_back(newNodePreviouslabel);
// Add branch new label
node->child.push_back(new TreeNode(branchNewlabel));
}
else if (matches > node->label.length())
{
string newLabel =
node->label.substr(node->label.length(), word.length());
// Add new label
node->child.push_back(new TreeNode(newLabel));
}
}
void insert(string word)
{
this->insertProcess(word, this->root);
}
// Display the preorder of tree elements
void printPreorder(TreeNode *node)
{
if (node == NULL)
{
return;
}
// Display node value
cout << node->label << endl;
for (int i = 0; i < node->child.size(); ++i)
{
// Visit child node
this->printPreorder(node->child.at(i));
}
}
};
int main()
{
RadixTree *tree = new RadixTree();
// Add tree node
tree->insert("romane");
tree->insert("romanus");
tree->insert("romulus");
tree->insert("rubens");
tree->insert("ruber");
tree->insert("rubicon");
tree->insert("rubicundus");
/*
r
/ \
/ \
/ \
/ \
om ub
/ \ / \
an ulus e ic
/ \ / \ / \
e us ns r on undus
*/
cout << "Preorder Tree Data ";
// Display Tree nodes
tree->printPreorder(tree->root);
return 0;
}
Output
Preorder Tree Data
r
om
an
e
us
ulus
ub
e
ns
r
ic
on
undus
// Include namespace system
using System;
using System.Collections.Generic;
// Csharp Program for
// Radix tree insert
public class TreeNode
{
public String label;
public List < TreeNode > child;
public TreeNode()
{
this.label = "";
this.child = new List < TreeNode > ();
}
public TreeNode(String value)
{
this.label = value;
this.child = new List < TreeNode > ();
}
}
public class RadixTree
{
public TreeNode root;
public RadixTree()
{
this.root = new TreeNode("");
}
private int matchingCharacters(String word, TreeNode node)
{
int matches = 0;
int minLength = 0;
if (node.label.Length >= word.Length)
{
minLength = word.Length;
}
else if (node.label.Length < word.Length)
{
minLength = node.label.Length;
}
if (minLength > 0)
{
// Count matches characters
for (int i = 0; i < minLength; i++)
{
if (word[i] == node.label[i])
{
// When characters are same
matches++;
}
else
{
// When characters are not same
return matches;
}
}
}
// Return the current number of matches
return matches;
}
// Add node in proper place
private void insertProcess(String word, TreeNode node)
{
int matches = this.matchingCharacters(word, node);
if ((matches == 0) || (node == this.root) ||
((matches > 0) && (matches < word.Length) &&
(matches >= node.label.Length)))
{
Boolean inserted = false;
String newWordPart = word.Substring(matches, word.Length - matches);
for (int i = 0; i < node.child.Count; ++i)
{
if (node.child[i].label.StartsWith("" + newWordPart[0]))
{
inserted = true;
this.insertProcess(newWordPart, node.child[i]);
}
}
if (inserted == false)
{
// Add new part
node.child.Add(new TreeNode(newWordPart));
}
}
else if (matches < word.Length)
{
String commonRoot = word.Substring(0, matches);
String branchPreviouslabel = node.label.Substring(matches, node.label.Length- matches);
String branchNewlabel = word.Substring(matches, word.Length - matches);
node.label = commonRoot;
TreeNode newNodePreviouslabel = new TreeNode(branchPreviouslabel);
// Add current node child to new node
for (int i = 0; i < node.child.Count; ++i)
{
newNodePreviouslabel.child.Add(node.child[i]);
}
// Clear node element
node.child.Clear();
// Add new node
node.child.Add(newNodePreviouslabel);
// Add branch new label
node.child.Add(new TreeNode(branchNewlabel));
}
else if (matches > node.label.Length)
{
String newLabel = node.label.Substring(node.label.Length, word.Length);
// Add new label
node.child.Add(new TreeNode(newLabel));
}
}
public void insert(String word)
{
this.insertProcess(word, this.root);
}
// Display the preorder of tree elements
public void printPreorder(TreeNode node)
{
if (node == null)
{
return;
}
// Display node value
Console.WriteLine(node.label);
for (int i = 0; i < node.child.Count; ++i)
{
// Visit child node
this.printPreorder(node.child[i]);
}
}
public static void Main(String[] args)
{
RadixTree tree = new RadixTree();
// Add tree node
tree.insert("romane");
tree.insert("romanus");
tree.insert("romulus");
tree.insert("rubens");
tree.insert("ruber");
tree.insert("rubicon");
tree.insert("rubicundus");
/*
r
/ \
/ \
/ \
/ \
om ub
/ \ / \
an ulus e ic
/ \ / \ / \
e us ns r on undus
*/
Console.Write("Preorder Tree Data ");
// Show Tree nodes
tree.printPreorder(tree.root);
}
}
Output
Preorder Tree Data
r
om
an
e
us
ulus
ub
e
ns
r
ic
on
undus
<?php
// Php Program for
// Radix tree insert
class TreeNode
{
public $label;
public $child;
public function __construct($value)
{
$this->label = $value;
$this->child = array();
}
}
class RadixTree
{
public $root;
public function __construct()
{
$this->root = new TreeNode("");
}
private
function matchingCharacters($word, $node)
{
$matches = 0;
$minLength = 0;
if (strlen($node->label) >= strlen($word))
{
$minLength = strlen($word);
}
else if (strlen($node->label) < strlen($word))
{
$minLength = strlen($node->label);
}
if ($minLength > 0)
{
// Count matches characters
for ($i = 0; $i < $minLength; $i++)
{
if ($word[$i] == $node->label[$i])
{
// When characters are same
$matches++;
}
else
{
// When characters are not same
return $matches;
}
}
}
// Return the current number of matches
return $matches;
}
// Add node in proper place
private
function insertProcess($word, $node)
{
$matches = $this->matchingCharacters($word, $node);
if (($matches == 0) || ($node == $this->root) ||
(($matches > 0) && ($matches < strlen($word)) &&
($matches >= strlen($node->label))))
{
$inserted = false;
$newWordPart = substr($word, $matches, strlen($word) - $matches);
for ($i = 0; $i < count($node->child); ++$i)
{
if ($node->child[$i]->label[0] == $newWordPart[0])
{
$inserted = true;
$this->insertProcess($newWordPart, $node->child[$i]);
}
}
if ($inserted == false)
{
// Add new part
$node->child[] = new TreeNode($newWordPart);
}
}
else if ($matches < strlen($word))
{
$commonRoot = substr($word, 0, $matches - 0);
$branchPreviouslabel = substr($node->label,
$matches, strlen($node->label) - $matches);
$branchNewlabel = substr($word,
$matches, strlen($word) - $matches);
$node->label = $commonRoot;
$newNodePreviouslabel = new TreeNode($branchPreviouslabel);
// Add current node child to new node
for ($i = 0; $i < count($node->child); ++$i)
{
$newNodePreviouslabel->child[] = $node->child[$i];
}
// Clear node element
$node->child = array();
// Add new node
$node->child[] = $newNodePreviouslabel;
// Add branch new label
$node->child[] = new TreeNode($branchNewlabel);
}
else if ($matches > strlen($node->label))
{
$newLabel = substr($node->label,
strlen($node->label),
strlen($word) - strlen($node->label));
// Add new label
$node->child[] = new TreeNode($newLabel);
}
}
public function insert($word)
{
$this->insertProcess($word, $this->root);
}
// Display the preorder of tree elements
public function printPreorder($node)
{
if ($node == NULL)
{
return;
}
// Display node value
echo($node->label.
"\n");
for ($i = 0; $i < count($node->child); ++$i)
{
// Visit child node
$this->printPreorder($node->child[$i]);
}
}
}
function main()
{
$tree = new RadixTree();
// Add tree node
$tree->insert("romane");
$tree->insert("romanus");
$tree->insert("romulus");
$tree->insert("rubens");
$tree->insert("ruber");
$tree->insert("rubicon");
$tree->insert("rubicundus");
/*
r
/ \
/ \
/ \
/ \
om ub
/ \ / \
an ulus e ic
/ \ / \ / \
e us ns r on undus
*/
echo("Preorder Tree Data ");
// Tree Tree nodes
$tree->printPreorder($tree->root);
}
main();
Output
Preorder Tree Data
r
om
an
e
us
ulus
ub
e
ns
r
ic
on
undus
// Node JS Program for
// Radix tree insert
class TreeNode
{
constructor(value)
{
this.label = value;
this.child = [];
}
}
class RadixTree
{
constructor()
{
this.root = new TreeNode("");
}
matchingCharacters(word, node)
{
var matches = 0;
var minLength = 0;
if (node.label.length >= word.length)
{
minLength = word.length;
}
else if (node.label.length < word.length)
{
minLength = node.label.length;
}
if (minLength > 0)
{
// Count matches characters
for (var i = 0; i < minLength; i++)
{
if (word.charAt(i) == node.label.charAt(i))
{
// When characters are same
matches++;
}
else
{
// When characters are not same
return matches;
}
}
}
// Return the current number of matches
return matches;
}
// Add node in proper place
insertProcess(word, node)
{
var matches = this.matchingCharacters(word, node);
if ((matches == 0) || (node == this.root) ||
((matches > 0) && (matches < word.length) &&
(matches >= node.label.length)))
{
var inserted = false;
var newWordPart = word.substring(matches, word.length);
for (var i = 0; i < node.child.length; ++i)
{
if (node.child[i].label.startsWith("" + newWordPart.charAt(0)))
{
inserted = true;
this.insertProcess(newWordPart, node.child[i]);
}
}
if (inserted == false)
{
// Add new part
node.child.push(new TreeNode(newWordPart));
}
}
else if (matches < word.length)
{
var commonRoot = word.substring(0, matches);
var branchPreviouslabel =
node.label.substring(matches, node.label.length);
var branchNewlabel = word.substring(matches, word.length);
node.label = commonRoot;
var newNodePreviouslabel = new TreeNode(branchPreviouslabel);
// Add current node child to new node
for (var i = 0; i < node.child.length; ++i)
{
newNodePreviouslabel.child.push(node.child[i]);
}
// Clear node element
node.child = [];
// Add new node
node.child.push(newNodePreviouslabel);
// Add branch new label
node.child.push(new TreeNode(branchNewlabel));
}
else if (matches > node.label.length)
{
var newLabel = node.label.substring(
node.label.length, word.length);
// Add new label
node.child.push(new TreeNode(newLabel));
}
}
insert(word)
{
this.insertProcess(word, this.root);
}
// Display the preorder of tree elements
printPreorder(node)
{
if (node == null)
{
return;
}
// Display node value
console.log(node.label);
for (var i = 0; i < node.child.length; ++i)
{
// Visit child node
this.printPreorder(node.child[i]);
}
}
}
function main()
{
var tree = new RadixTree();
// Add tree node
tree.insert("romane");
tree.insert("romanus");
tree.insert("romulus");
tree.insert("rubens");
tree.insert("ruber");
tree.insert("rubicon");
tree.insert("rubicundus");
/*
r
/ \
/ \
/ \
/ \
om ub
/ \ / \
an ulus e ic
/ \ / \ / \
e us ns r on undus
*/
process.stdout.write("Preorder Tree Data ");
// Tree Tree nodes
tree.printPreorder(tree.root);
}
main();
Output
Preorder Tree Data
r
om
an
e
us
ulus
ub
e
ns
r
ic
on
undus
# Python 3 Program for
# Radix tree insert
class TreeNode :
def __init__(self) :
self.label = ""
self.child = []
def __init__(self, value) :
self.label = value
self.child = []
class RadixTree :
def __init__(self) :
self.root = TreeNode("")
def matchingCharacters(self, word, node) :
matches = 0
minLength = 0
if (len(node.label) >= len(word)) :
minLength = len(word)
elif (len(node.label) < len(word)) :
minLength = len(node.label)
if (minLength > 0) :
i = 0
# Count matches characters
while (i < minLength) :
if (word[i] == node.label[i]) :
# When characters are same
matches += 1
else :
# When characters are not same
return matches
i += 1
# Return the current number of matches
return matches
# Add node in proper place
def insertProcess(self, word, node) :
matches = self.matchingCharacters(word, node)
if ((matches == 0) or(node == self.root) or
((matches > 0) and(matches < len(word)) and
(matches >= len(node.label)))) :
inserted = False
newWordPart = word[matches: len(word)]
i = 0
while (i < len(node.child)) :
if (node.child[i].label[0] == newWordPart[0]) :
inserted = True
self.insertProcess(newWordPart, node.child[i])
i += 1
if (inserted == False) :
# Add new part
node.child.append(TreeNode(newWordPart))
elif (matches < len(word)) :
commonRoot = word[0: matches]
branchPreviouslabel = node.label[matches: len(node.label)]
branchNewlabel = word[matches: len(word)]
node.label = commonRoot
newNodePreviouslabel = TreeNode(branchPreviouslabel)
i = 0
# Add current node child to new node
while (i < len(node.child)) :
newNodePreviouslabel.child.append(node.child[i])
i += 1
# Clear node element
node.child.clear()
# Add new node
node.child.append(newNodePreviouslabel)
# Add branch new label
node.child.append(TreeNode(branchNewlabel))
elif (matches > len(node.label)) :
newLabel = node.label[len(node.label): len(word)]
# Add new label
node.child.append(TreeNode(newLabel))
def insert(self, word) :
self.insertProcess(word, self.root)
# Display the preorder of tree elements
def printPreorder(self, node) :
if (node == None) :
return
# Display node value
print(node.label)
i = 0
while (i < len(node.child)) :
# Visit child node
self.printPreorder(node.child[i])
i += 1
def main() :
tree = RadixTree()
# Add tree node
tree.insert("romane")
tree.insert("romanus")
tree.insert("romulus")
tree.insert("rubens")
tree.insert("ruber")
tree.insert("rubicon")
tree.insert("rubicundus")
# r
# / \
# / \
# / \
# / \
# om ub
# / \ / \
# an ulus e ic
# / \ / \ / \
# e us ns r on undus
print("Preorder Tree Data ", end = "")
# Tree Tree nodes
tree.printPreorder(tree.root)
if __name__ == "__main__": main()
Output
Preorder Tree Data
r
om
an
e
us
ulus
ub
e
ns
r
ic
on
undus
# Ruby Program for
# Radix tree insert
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :label, :child
attr_accessor :label, :child
def initialize()
self.label = ""
self.child = []
end
def initialize(value)
self.label = value
self.child = []
end
end
class RadixTree
# Define the accessor and reader of class RadixTree
attr_reader :root
attr_accessor :root
def initialize()
self.root = TreeNode.new("")
end
def matchingCharacters(word, node)
matches = 0
minLength = 0
if (node.label.length >= word.length)
minLength = word.length
elsif (node.label.length < word.length)
minLength = node.label.length
end
if (minLength > 0)
i = 0
# Count matches characters
while (i < minLength)
if (word[i] == node.label[i])
# When characters are same
matches += 1
else
# When characters are not same
return matches
end
i += 1
end
end
# Return the current number of matches
return matches
end
# Add node in proper place
def insertProcess(word, node)
matches = self.matchingCharacters(word, node)
if ((matches == 0) || (node == self.root) ||
((matches > 0) && (matches < word.length) &&
(matches >= node.label.length)))
inserted = false
newWordPart = word[matches...word.length]
i = 0
while (i < node.child.length)
if (node.child[i].label[0] == newWordPart[0].to_s)
inserted = true
self.insertProcess(newWordPart, node.child[i])
end
i += 1
end
if (inserted == false)
# Add new part
node.child.push(TreeNode.new(newWordPart))
end
elsif (matches < word.length)
commonRoot = word[0...matches]
branchPreviouslabel = node.label[matches...node.label.length]
branchNewlabel = word[matches...word.length]
node.label = commonRoot
newNodePreviouslabel = TreeNode.new(branchPreviouslabel)
i = 0
# Add current node child to new node
while (i < node.child.length)
newNodePreviouslabel.child.push(node.child[i])
i += 1
end
# Clear node element
node.child.clear()
# Add new node
node.child.push(newNodePreviouslabel)
# Add branch new label
node.child.push(TreeNode.new(branchNewlabel))
elsif (matches > node.label.length)
newLabel = node.label[node.label.length...word.length]
# Add new label
node.child.push(TreeNode.new(newLabel))
end
end
def insert(word)
self.insertProcess(word, self.root)
end
# Display the preorder of tree elements
def printPreorder(node)
if (node == nil)
return
end
# Display node value
print(node.label, "\n")
i = 0
while (i < node.child.length)
# Visit child node
self.printPreorder(node.child[i])
i += 1
end
end
end
def main()
tree = RadixTree.new()
# Add tree node
tree.insert("romane")
tree.insert("romanus")
tree.insert("romulus")
tree.insert("rubens")
tree.insert("ruber")
tree.insert("rubicon")
tree.insert("rubicundus")
# r
# / \
# / \
# / \
# / \
# om ub
# / \ / \
# an ulus e ic
# / \ / \ / \
# e us ns r on undus
print("Preorder Tree Data ")
# Tree Tree nodes
tree.printPreorder(tree.root)
end
main()
Output
Preorder Tree Data
r
om
an
e
us
ulus
ub
e
ns
r
ic
on
undus
import scala.collection.mutable._;
// Scala Program for
// Radix tree insert
class TreeNode(var label: String,
var child: ArrayBuffer[TreeNode])
{
def this()
{
this("", new ArrayBuffer[TreeNode]())
}
def this(value: String)
{
this(value, new ArrayBuffer[TreeNode]())
}
}
class RadixTree(var root: TreeNode)
{
def this()
{
this(new TreeNode(""));
}
def matchingCharacters(word: String, node: TreeNode): Int = {
var matches: Int = 0;
var minLength: Int = 0;
if (node.label.length() >= word.length())
{
minLength = word.length();
}
else if (node.label.length() < word.length())
{
minLength = node.label.length();
}
if (minLength > 0)
{
var i: Int = 0;
// Count matches characters
while (i < minLength)
{
if (word.charAt(i) == node.label.charAt(i))
{
// When characters are same
matches += 1;
}
else
{
// When characters are not same
return matches;
}
i += 1;
}
}
// Return the current number of matches
return matches;
}
// Add node in proper place
def insertProcess(word: String, node: TreeNode): Unit = {
var matches: Int = matchingCharacters(word, node);
if ((matches == 0) || (node == root) || ((matches > 0) &&
(matches < word.length()) && (matches >= node.label.length())))
{
var inserted: Boolean = false;
var newWordPart: String = word.substring(matches, word.length());
var i: Int = 0;
while (i < node.child.size)
{
if (node.child(i).label.startsWith(
"" + newWordPart.charAt(0).toString()))
{
inserted = true;
insertProcess(newWordPart, node.child(i));
}
i += 1;
}
if (inserted == false)
{
// Add new part
node.child += new TreeNode(newWordPart);
}
}
else if (matches < word.length())
{
var commonRoot: String = word.substring(0, matches);
var branchPreviouslabel: String = node.label.substring(
matches, node.label.length());
var branchNewlabel: String = word.substring(
matches, word.length());
node.label = commonRoot;
var newNodePreviouslabel: TreeNode =
new TreeNode(branchPreviouslabel);
var i: Int = 0;
// Add current node child to new node
while (i < node.child.size)
{
newNodePreviouslabel.child += node.child(i);
i += 1;
}
// Clear node element
node.child.clear();
// Add new node
node.child += newNodePreviouslabel;
// Add branch new label
node.child += new TreeNode(branchNewlabel);
}
else if (matches > node.label.length())
{
var newLabel: String = node.label.substring(
node.label.length(), word.length());
// Add new label
node.child += new TreeNode(newLabel);
}
}
def insert(word: String): Unit = {
this.insertProcess(word, this.root);
}
// Display the preorder of tree elements
def printPreorder(node: TreeNode): Unit = {
if (node == null)
{
return;
}
// Display node value
println(node.label);
var i: Int = 0;
while (i < node.child.size)
{
// Visit child node
printPreorder(node.child(i));
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: RadixTree = new RadixTree();
// Add tree node
tree.insert("romane");
tree.insert("romanus");
tree.insert("romulus");
tree.insert("rubens");
tree.insert("ruber");
tree.insert("rubicon");
tree.insert("rubicundus");
/*
r
/ \
/ \
/ \
/ \
om ub
/ \ / \
an ulus e ic
/ \ / \ / \
e us ns r on undus
*/
print("Preorder Tree Data ");
// Tree Tree nodes
tree.printPreorder(tree.root);
}
}
Output
Preorder Tree Data
r
om
an
e
us
ulus
ub
e
ns
r
ic
on
undus
// Kotlin Program for
// Radix tree insert
class TreeNode
{
var label: String;
var child: MutableList < TreeNode > ;
constructor()
{
this.label = "";
this.child = mutableListOf < TreeNode > ();
}
constructor(value: String)
{
this.label = value;
this.child = mutableListOf < TreeNode > ();
}
}
class RadixTree
{
var root: TreeNode ? ;
constructor()
{
this.root = TreeNode("");
}
fun matchingCharacters(word: String, node: TreeNode ? ): Int
{
var matches: Int = 0;
var minLength: Int = 0;
if (node!!.label.length >= word.length)
{
minLength = word.length;
}
else if (node.label.length < word.length)
{
minLength = node.label.length;
}
if (minLength > 0)
{
var i: Int = 0;
// Count matches characters
while (i < minLength)
{
if (word.get(i) == node.label.get(i))
{
// When characters are same
matches += 1;
}
else
{
// When characters are not same
return matches;
}
i += 1;
}
}
// Return the current number of matches
return matches;
}
// Add node in proper place
fun insertProcess(word: String, node: TreeNode ? ): Unit
{
val matches: Int = this.matchingCharacters(word, node);
if ((matches == 0) || (node == this.root) ||
((matches > 0) && (matches < word.length) &&
(matches >= node!!.label.length)))
{
var inserted: Boolean = false;
val newWordPart: String = word.substring(matches, word.length);
var i: Int = 0;
while (i < node!!.child.size)
{
if (node.child[i].label.startsWith(
"" + newWordPart.get(0).toString()))
{
inserted = true;
this.insertProcess(newWordPart, node.child[i]);
}
i += 1;
}
if (inserted == false)
{
// Add new part
node.child.add(TreeNode(newWordPart));
}
}
else if (matches < word.length)
{
val commonRoot: String = word.substring(0, matches);
val branchPreviouslabel: String = node!!.label.substring(
matches, node.label.length);
val branchNewlabel: String = word.substring(
matches, word.length);
node.label = commonRoot;
val newNodePreviouslabel: TreeNode = TreeNode(
branchPreviouslabel);
var i: Int = 0;
// Add current node child to new node
while (i < node.child.size)
{
newNodePreviouslabel.child.add(node.child[i]);
i += 1;
}
// Clear node element
node.child.clear();
// Add new node
node.child.add(newNodePreviouslabel);
// Add branch new label
node.child.add(TreeNode(branchNewlabel));
}
else if (matches > node!!.label.length)
{
val newLabel: String = node.label.substring(
node.label.length, word.length);
// Add new label
node.child.add(TreeNode(newLabel));
}
}
fun insert(word: String): Unit
{
this.insertProcess(word, this.root);
}
// Display the preorder of tree elements
fun printPreorder(node: TreeNode ? ): Unit
{
if (node == null)
{
return;
}
// Display node value
println(node.label);
var i: Int = 0;
while (i < node.child.size)
{
// Visit child node
this.printPreorder(node.child[i]);
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
val tree: RadixTree = RadixTree();
// Add tree node
tree.insert("romane");
tree.insert("romanus");
tree.insert("romulus");
tree.insert("rubens");
tree.insert("ruber");
tree.insert("rubicon");
tree.insert("rubicundus");
/*
r
/ \
/ \
/ \
/ \
om ub
/ \ / \
an ulus e ic
/ \ / \ / \
e us ns r on undus
*/
print("Preorder Tree Data ");
// Tree Tree nodes
tree.printPreorder(tree.root);
}
Output
Preorder Tree Data
r
om
an
e
us
ulus
ub
e
ns
r
ic
on
undus
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