Reversed Radix tree

In previous post, I explained radix (or) compressed tree. Reverse radix tree is also a radix tree, only difference is it stores string in reverse way.

Applications

1.   Used to find exact match of string

2.   Used to find all strings that end with given suffix.

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

import com.googlecode.concurrenttrees.common.Iterables;
import com.googlecode.concurrenttrees.common.PrettyPrinter;
import com.googlecode.concurrenttrees.radix.node.concrete.DefaultCharArrayNodeFactory;
import com.googlecode.concurrenttrees.radix.node.util.PrettyPrintable;
import com.googlecode.concurrenttrees.radixreversed.ConcurrentReversedRadixTree;
import com.googlecode.concurrenttrees.radixreversed.ReversedRadixTree;

public class ReverseRadixTreeEx {
    public static void main(String args[]){
        ReversedRadixTree<Integer> tree = new ConcurrentReversedRadixTree<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));
        tree.put("beap", new Integer(9));

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

        System.out.println();
        System.out.println("Value for 'buy' (exact match): " + tree.getValueForExactKey("buy"));
        System.out.println("Value for 'stop' (exact match): " + tree.getValueForExactKey("stop"));
        System.out.println();
        System.out.println("Keys ending with 'll': " + Iterables.toString(tree.getKeysEndingWith("ll")));
        System.out.println("Keys ending with 'p': " + Iterables.toString(tree.getKeysEndingWith("p")));
        System.out.println();
        System.out.println("Values for keys ending with 'll': " + Iterables.toString(tree.getValuesForKeysEndingWith("ll")));
        System.out.println("Key-Value pairs for keys ending with 'll': " + Iterables.toString(tree.getKeyValuePairsForKeysEndingWith("ll")));
    }
}

Output

Tree structure:
○
├── ○ dib (3)
├── ○ kcots (1)
├── ○ ll
│   ├── ○ e
│   │   ├── ○ b (4)
│   │   └── ○ s (7)
│   └── ○ ub (6)
├── ○ p
│   ├── ○ aeb (9)
│   └── ○ ots (8)
├── ○ raeb (2)
└── ○ yub (5)

Value for 'buy' (exact match): 5
Value for 'stop' (exact match): 8

Keys ending with 'll': [bell, sell, bull]
Keys ending with 'p': [beap, stop]

Values for keys ending with 'll': [4, 7, 6]
Key-Value pairs for keys ending with 'll': [(bell, 4), (sell, 7), (bull, 6)]

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

import com.googlecode.concurrenttrees.common.Iterables;
import com.googlecode.concurrenttrees.common.PrettyPrinter;
import com.googlecode.concurrenttrees.radix.node.concrete.DefaultCharArrayNodeFactory;
import com.googlecode.concurrenttrees.radix.node.concrete.voidvalue.VoidValue;
import com.googlecode.concurrenttrees.radix.node.util.PrettyPrintable;
import com.googlecode.concurrenttrees.radixreversed.ConcurrentReversedRadixTree;
import com.googlecode.concurrenttrees.radixreversed.ReversedRadixTree;

public class ReverseRadixTreeEx {
    public static void main(String args[]){
        ReversedRadixTree<VoidValue> tree = new ConcurrentReversedRadixTree<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);
        tree.put("beap", VoidValue.SINGLETON);

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

        System.out.println();
        System.out.println("Value for 'buy' (exact match): " + tree.getValueForExactKey("buy"));
        System.out.println("Value for 'stop' (exact match): " + tree.getValueForExactKey("stop"));
        System.out.println();
        System.out.println("Keys ending with 'll': " + Iterables.toString(tree.getKeysEndingWith("ll")));
        System.out.println("Keys ending with 'p': " + Iterables.toString(tree.getKeysEndingWith("p")));
        System.out.println();
        System.out.println("Values for keys ending with 'll': " + Iterables.toString(tree.getValuesForKeysEndingWith("ll")));
        System.out.println("Key-Value pairs for keys ending with 'll': " + Iterables.toString(tree.getKeyValuePairsForKeysEndingWith("ll")));
    }
}

Output

Tree structure:
○
├── ○ dib (-)
├── ○ kcots (-)
├── ○ ll
│   ├── ○ e
│   │   ├── ○ b (-)
│   │   └── ○ s (-)
│   └── ○ ub (-)
├── ○ p
│   ├── ○ aeb (-)
│   └── ○ ots (-)
├── ○ raeb (-)
└── ○ yub (-)

Value for 'buy' (exact match): -
Value for 'stop' (exact match): -

Keys ending with 'll': [bell, sell, bull]
Keys ending with 'p': [beap, stop]

Values for keys ending with 'll': [-, -, -]
Key-Value pairs for keys ending with 'll': [(bell, -), (sell, -), (bull, -)]

Prevoius                                                 Next                                                 Home