Java Crit-bit Trees

Question

Java中是否有內置的數據結構來表示Crit位樹？或者任何可能提供這種功能的庫？如果可以簡單簡單地實施，我也會接受簡短的代碼作爲答案。

Answer 1

您是否嘗試過radixtree java項目？

你可能在其中找到你要找的結構，如：

• RadixTree類

（摘錄）：

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

（摘錄）：

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

另一種選擇是rkapsi的patricia-trie，或者如果你正在尋找的東西少一點複雜，你可以在自己的破解，你可以嘗試他的simple-patricia-trie。

我也有一個functional-critbit實現可用，專注於空間效率（雖然它的性能也很好）。它具有可變和不可變的風味。

Answer 3

嘗試concurrent-trees

的gradle上：

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