5
Sto cercando un'implementazione Binary Search Tree integrata in .NET 4. Ce n'è una?Esiste un'implementazione dell'albero di ricerca binaria in .NET 4?
A
risposta
7
La classe SortedDictionary<K,V> utilizza un albero, è questo quello che stai cercando?
Vedere questo SO answer per una discussione.
4
Potreste usare SortedDictionary<TKey, TValue>
2
Un'altra opzione è quella di utilizzare un elenco e ordinarla. Quindi puoi usare il metodo BinarySearch per trovare gli oggetti. Per mantenere l'elenco ordinato è possibile utilizzare l'indice restituito da BinarySearch per inserire in. Se l'indice restituito è negativo, utilizzare il complemento (operatore ~) come posizione di inserimento, se l'indice restituito è positivo, è possibile inserire in quella posizione (a meno che non si desideri impostare un comportamento simile, nel qual caso non inserire affatto).
2
Classe TreeDictionary implementa interfaccia ISortedDictionary e rappresenta un dizionario di (chiave, valore) coppie o voci, che utilizzano un equilibrato redblack albero binario ordinato. Accesso alla voce, cancellazione della voce e inserimento della voce richiedono tempo O (logn). L'enumerazione delle chiavi, valori o voci di un dizionario ad albero segue l'ordine delle chiavi, come determinato dal comparatore di chiavi.
0
http://code.google.com/p/self-balancing-avl-tree/. Implementazione di alberi AVL bilanciati con operazioni concatenate e suddivise nonché SortedDictinary e SortedMultiDictionary basate sull'albero AVL.
Questo fornisce la stessa semantica di ricerca, ma la struttura sottostante è ancora una semplice lista vecchia, non una BST. –
Buona chiamata, non ci ho pensato fino a quando l'ho postato (solo 1 tazza di caffè in quel momento). Uso la lista con BinarySearch e l'inserimento dell'indice complementare per ottenere la semantica della ricerca BST. Dovrei leggere più attentamente :) – pstrjds