Alberi Java Crit-bit

Question

Esiste una struttura dati integrata in Java per rappresentare un albero Crit-bit? O eventuali librerie disponibili che potrebbero fornire questa funzionalità? Accetterei anche un breve codice come risposta, se uno può essere implementato in modo semplicistico.

Answer 1

Hai provato il progetto java radixtree?

Si potrebbe trovare in esso la struttura che si sta cercando, come il:

• RadixTree classe

(estratto):

/** 
* This interface represent the operation of a radix tree. A radix tree, 
* Patricia trie/tree, or crit bit tree is a specialized set data structure 
* based on the trie that is used to store a set of strings. In contrast with a 
* regular trie, the edges of a Patricia trie are labelled with sequences of 
* characters rather than with single characters. These can be strings of 
* characters, bit strings such as integers or IP addresses, or generally 
* arbitrary sequences of objects in lexicographical order. Sometimes the names 
* radix tree and crit bit tree are only applied to trees storing integers and 
* Patricia trie is retained for more general inputs, but the structure works 
* the same way in all cases. 
* 
* @author Tahseen Ur Rehman 
* email: tahseen.ur.rehman {at.spam.me.not} gmail.com 
*/ 
public interface RadixTree<T> { 
    /** 
    * Insert a new string key and its value to the tree. 
    * 
    * @param key 
    *   The string key of the object 
    * @param value 
    *   The value that need to be stored corresponding to the given 
    *   key. 
    * @throws DuplicateKeyException 
    */ 
    public void insert(String key, T value) throws DuplicateKeyException; 

• RadixTreeNode classe

(estratto):

/** 
* Represents a node of a Radix tree {@link RadixTreeImpl} 
* 
* @author Tahseen Ur Rehman 
* @email tahseen.ur.rehman {at.spam.me.not} gmail.com 
* @param <T> 
*/ 
class RadixTreeNode<T> { 
    private String key; 

    private List<RadixTreeNode<T>> childern; 

    private boolean real; 

    private T value; 

    /** 
    * intailize the fields with default values to avoid null reference checks 
    * all over the places 
    */ 
     public RadixTreeNode() { 
     key = ""; 
     childern = new ArrayList<RadixTreeNode<T>>(); 
     real = false; 
    } 

Answer 2

Un'altra opzione è quella di rkapsi patricia-trie, o se siete alla ricerca di qualcosa di un po 'meno complicato che si può incidere su se stessi, si può provare la sua simple-patricia-trie.

Ho anche disponibile un'implementazione functional-critbit focalizzata sull'efficienza dello spazio (anche se le sue prestazioni vanno bene). È disponibile in entrambi i gusti mutevoli e immutabili.

Answer 3

provare concurrent-trees

su Gradle:

compile 'com.googlecode.concurrent-trees:concurrent-trees:2.4.0'