2010-02-19 6 views
50

Esiste un modulo per AVL o Red-Black o qualche altro tipo di albero binario bilanciato nella libreria standard di Python? Ho provato a trovarne uno, ma senza successo (sono relativamente nuovo a Python).Libreria standard di Python - Esiste un modulo per l'albero binario bilanciato?

+1

mi basta usare set o dizionari. Se ho bisogno di usare una routine di hashing migliore, definisco '__hash __()'. Hai bisogno di qualcosa di più creativo? Se è così, perché? BTW, se non riesci a trovarlo in docs.python.org, probabilmente non è un modulo standard. –

+0

@Mike - Sto provando a risolvere un compito da Project Euler. Penso che usare un albero di ricerca binario bilanciato invece di un elenco per uno dei miei contenitori di dati acceleri l'algoritmo con il rapporto logaritmico (a causa delle ricerche O (logn)), che risolverebbe l'attività senza surriscaldare il mio computer. Inoltre, ero solo curioso. – aeter

+1

Che dire di un set per O (1) lookup – Mark

risposta

23

No, non c'è un albero binario bilanciato nello stdlib. Tuttavia, dai tuoi commenti, sembra che tu possa avere alcune altre opzioni:

  • Si dice che si desidera un BST anziché un elenco per le ricerche O(log n). Se la ricerca è completa e i dati sono già ordinati, il modulo bisect fornisce un algoritmo di ricerca binaria per gli elenchi.
  • Mike DeSimone consigliava set e dict e hai spiegato perché le liste sono troppo algoritmicamente lente. Set e dict sono implementati come tabelle hash, che hanno ricerca O (1). La soluzione alla maggior parte dei problemi in Python è in realtà "use a dict".

Se nessuna delle due soluzioni funziona correttamente, è necessario passare a un modulo di terze parti o implementare le proprie.

+1

Grazie mille! L'utilizzo di un set ha risolto il mio problema. Non avevo idea di avere le ricerche O (1) in Python (ho sempre pensato che l'intero set dovesse essere attraversato prima di trovare il giusto valore - ma come ho detto, sono nuovo di Python). Grazie anche per la spiegazione delle solite strutture dati in Python. – aeter

8

Ci sono stati alcuni casi in cui ho trovato che lo heapq package (nella libreria stadndard) sia utile, specialmente se in qualsiasi momento si desidera O (1) tempo di accesso all'elemento più piccolo della propria raccolta.

Per quanto mi riguarda, tenevo traccia di una raccolta di timer e di solito mi interessava solo verificare se il tempo più breve (quello da eseguire per primo) era già pronto per partire.

4

C'è un nuovo pacchetto chiamato "bintrees" che supporta alberi ubalanced, AVL e RB. Lo puoi trovare here.

+0

Ho installato il modulo bintrees (2.0.1), ma quando lo importa, ottengo il messaggio: 'Attenzione: FastBinaryTree non disponibile, utilizzando la versione di Python BinaryTree. Qualche idea su come risolvere questo problema? Ho installato Cython, ma continua a dare quell'errore durante l'importazione. – yaraju

+0

Mi spiace, non ho idea :( –

+0

Ho capito che - Su Windows, le versioni FastXTree hanno bisogno di un compilatore C installato come MSVC o Mingw32. Non l'ho provato - perché probabilmente implementerò un albero personalizzato per il mio scopo – yaraju