Cây Crit-bit Java

Question

Có cấu trúc dữ liệu tích hợp trong Java để biểu diễn cây Crit-bit không? Hoặc bất kỳ thư viện nào có thể cung cấp chức năng này? Tôi cũng sẽ chấp nhận mã ngắn gọn như một câu trả lời, nếu có thể được thực hiện một cách đơn giản.

Answer 1

Bạn đã thử dự án java radixtree?

Bạn có thể tìm thấy trong đó cấu trúc bạn đang tìm kiếm, giống như:

• RadixTree lớp

(trích):

/** 
* 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 lớp

(trích):

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

lựa chọn khác là rkapsi của patricia-trie, hoặc nếu bạn đang tìm kiếm cái gì một chút ít phức tạp mà bạn có thể hack vào chính mình, bạn có thể thử simple-patricia-trie mình.

Tôi cũng có một triển khai functional-critbit có sẵn, tập trung vào hiệu quả không gian (mặc dù hiệu suất của nó cũng tốt). Nó có cả hương vị có thể thay đổi và bất biến.

Answer 3

thử concurrent-trees

trên gradle:

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