Compressed Trie (Radix trie)

Compressed trie is a trie with only one addition rule such that, every internal node must have ≥ 2 children.  Compressed trie is also known as Radix trie (or) Patricia trie.

Trie shown in above figure converted to compressed trie like below.

As you observe, nodes

‘a’, ‘r’ are combined and form “ar”.

‘l’,’l’ are combined and form “ll”

‘I’, ‘d’ are combined and form “id”

‘e’, ‘l’, ‘l’ are combined and form “ell”

‘t’, ‘o’ are combined and form “to”

‘c’, ‘k’ are combined and form “ck”

Below program uses concurrent-trees package, you can download at https://code.google.com/p/concurrent-trees/.

import com.googlecode.concurrenttrees.radix.RadixTree;
import com.googlecode.concurrenttrees.radix.ConcurrentRadixTree;
import com.googlecode.concurrenttrees.radix.node.concrete.DefaultCharArrayNodeFactory;
import com.googlecode.concurrenttrees.radix.node.util.PrettyPrintable;
import com.googlecode.concurrenttrees.common.Iterables;
import com.googlecode.concurrenttrees.common.PrettyPrinter;

public class Main {
    public static void main(String[] args) {
        RadixTree<Integer> tree = new ConcurrentRadixTree<Integer>(new DefaultCharArrayNodeFactory());
        tree.put("stock", new Integer(1));
        tree.put("bear", new Integer(2));
        tree.put("bid", new Integer(3));
        tree.put("bell", new Integer(4));
        tree.put("buy", new Integer(5));
        tree.put("bull", new Integer(6));
        tree.put("sell", new Integer(7));
        tree.put("stop", new Integer(8));

        System.out.println("Tree structure:");
        PrettyPrinter.prettyPrint((PrettyPrintable) tree, System.out);

        System.out.println();
        System.out.println("Value for 'stock' (exact match): " + tree.getValueForExactKey("stock"));
        System.out.println("Value for 'bell' (exact match): " + tree.getValueForExactKey("bell"));
        System.out.println();
        System.out.println("Keys starting with 'b': " + Iterables.toString(tree.getKeysStartingWith("b")));
        System.out.println("Keys starting with 'be': " + Iterables.toString(tree.getKeysStartingWith("be")));
        System.out.println();
        System.out.println("Values for keys starting with 'be': " + Iterables.toString(tree.getValuesForKeysStartingWith("be")));
        System.out.println("Key-Value pairs for keys starting with 'be': " + Iterables.toString(tree.getKeyValuePairsForKeysStartingWith("be")));
        System.out.println();
        System.out.println("Keys closest to 'buying': " + Iterables.toString(tree.getClosestKeys("buying")));
    }
}

Output

Tree structure:
○
├── ○ b
│   ├── ○ e
│   │   ├── ○ ar (2)
│   │   └── ○ ll (4)
│   ├── ○ id (3)
│   └── ○ u
│       ├── ○ ll (6)
│       └── ○ y (5)
└── ○ s
    ├── ○ ell (7)
    └── ○ to
        ├── ○ ck (1)
        └── ○ p (8)

Value for 'stock' (exact match): 1
Value for 'bell' (exact match): 4

Keys starting with 'b': [bear, bell, bid, bull, buy]
Keys starting with 'be': [bear, bell]

Values for keys starting with 'be': [2, 4]
Key-Value pairs for keys starting with 'be': [(bear, 2), (bell, 4)]

Keys closest to 'buying': [buy]

If you want to add keys without any value, you can use “VoidValue.SINGLETON”.

Example

tree.put("stock", VoidValue.SINGLETON);

import com.googlecode.concurrenttrees.radix.RadixTree;
import com.googlecode.concurrenttrees.radix.ConcurrentRadixTree;
import com.googlecode.concurrenttrees.radix.node.concrete.DefaultCharArrayNodeFactory;
import com.googlecode.concurrenttrees.radix.node.util.PrettyPrintable;
import com.googlecode.concurrenttrees.common.Iterables;
import com.googlecode.concurrenttrees.common.PrettyPrinter;
import com.googlecode.concurrenttrees.radix.node.concrete.voidvalue.VoidValue;

public class Main {
    public static void main(String[] args) {
        RadixTree<VoidValue> tree = new ConcurrentRadixTree<VoidValue>(new DefaultCharArrayNodeFactory());
        tree.put("stock", VoidValue.SINGLETON);
        tree.put("bear", VoidValue.SINGLETON);
        tree.put("bid", VoidValue.SINGLETON);
        tree.put("bell", VoidValue.SINGLETON);
        tree.put("buy", VoidValue.SINGLETON);
        tree.put("bull", VoidValue.SINGLETON);
        tree.put("sell", VoidValue.SINGLETON);
        tree.put("stop", VoidValue.SINGLETON);

        System.out.println("Tree structure:");
        PrettyPrinter.prettyPrint((PrettyPrintable) tree, System.out);

        System.out.println();
        System.out.println("Value for 'stock' (exact match): " + tree.getValueForExactKey("stock"));
        System.out.println("Value for 'bell' (exact match): " + tree.getValueForExactKey("bell"));
        System.out.println();
        System.out.println("Keys starting with 'b': " + Iterables.toString(tree.getKeysStartingWith("b")));
        System.out.println("Keys starting with 'be': " + Iterables.toString(tree.getKeysStartingWith("be")));
        System.out.println();
        System.out.println("Values for keys starting with 'be': " + Iterables.toString(tree.getValuesForKeysStartingWith("be")));
        System.out.println("Key-Value pairs for keys starting with 'be': " + Iterables.toString(tree.getKeyValuePairsForKeysStartingWith("be")));
        System.out.println();
        System.out.println("Keys closest to 'buying': " + Iterables.toString(tree.getClosestKeys("buying")));
    }
}

Output

Tree structure:
○
├── ○ b
│   ├── ○ e
│   │   ├── ○ ar (-)
│   │   └── ○ ll (-)
│   ├── ○ id (-)
│   └── ○ u
│       ├── ○ ll (-)
│       └── ○ y (-)
└── ○ s
    ├── ○ ell (-)
    └── ○ to
        ├── ○ ck (-)
        └── ○ p (-)

Value for 'stock' (exact match): -
Value for 'bell' (exact match): -

Keys starting with 'b': [bear, bell, bid, bull, buy]
Keys starting with 'be': [bear, bell]

Values for keys starting with 'be': [-, -]
Key-Value pairs for keys starting with 'be': [(bear, -), (bell, -)]

Keys closest to 'buying': [buy]

Prevoius                                                 Next                                                 Home