Java Kritik Bit Ağaçları

Question

Java'da bir Crit-bit ağacını temsil etmek için yerleşik bir veri yapısı var mı? Veya bu işlevselliği sağlayabilecek herhangi bir kütüphane var mı? Basit bir şekilde uygulanabiliyorsa kısa kodu bir cevap olarak kabul ediyorum.

Answer 1

radixtree java projesini denediniz mi?

Bunun gibi aradığınız yapısını bulabilirsiniz:

• RadixTree sınıf

(özü):

/** 
* 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 sınıfı

(özü):

/** 
* 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

Diğer bir seçenek rkapsi en patricia-trie, ya da sen kendin üzerinde kesmek anlamına biraz daha az karmaşık bir şey arıyorsanız, onun simple-patricia-trie deneyebilirsiniz.

Ayrıca, alan verimliliğine odaklanmış bir functional-critbit uygulaması var (performansı da iyi olsa da). Hem değişebilen hem de değişmez tatlarda gelir.

Answer 3

gradle üzerinde concurrent-trees

bağlantılar:

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