Java Crit-bit Trees

Question

Czy istnieje wbudowana struktura danych w języku Java reprezentująca drzewo bitowe o wartości krytycznej? Lub dostępne biblioteki, które mogą zapewnić tę funkcjonalność? Za krótkie odpowiedzi uważałbym również krótki kod, który można wdrożyć w uproszczony sposób.

Answer 1

Czy wypróbowałeś projekt java radixtree?

Można znaleźć w nim strukturę, której szukasz, takich jak:

• RadixTree klasa

(wyciąg):

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

(wyciąg):

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

Inną opcją jest rkapsi na patricia-trie, lub jeśli szukasz czegoś trochę mniej skomplikowany, że można włamać się na siebie, można spróbować swoich simple-patricia-trie.

Mam również dostępną implementację functional-critbit, która koncentruje się na wydajności kosmicznej (chociaż jej wydajność jest również dobra). Występuje zarówno w zmiennym, jak i niezmiennym aromacie.

Answer 3

spróbować concurrent-trees

na Gradle:

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