[JAVA] Dizionario Ordinato con albero red-black

[Skarafaz]

Salve raga! Ho un problemone:

devo realizzare un dizionario ordinato con un albero red-black e non riesco ad implementare due metodi (il resto è a posto per fortuna ):

successors(k): restituisce un iteratore delle entry del dizionario con chiave maggiore o uguale a k (in ordine non decrescente)


predecessors(k): restituisce un iteratore delle entry del dizionario con chiave minore o uguale a k (in ordine non decrescente)

Io ho pensato a questo algoritmo:
- visito inorder i nodi dell'albero e inserisco le entry dei nodi interni (i nodi esterni sono vuoti) in una lista L (che quindi sarà ordinata in ordine non decrescente);
- scandisco le entry contenute in L e metto quelle con chiave maggiore o uguale a k in un'altra lista S;
- da S ricavo l'iteratore.

l'algoritmo funziona! Però non sfrutta le proprietà degli alberi binari di ricerca ed è inutilmente costoso!!!


qualcuno può suggerirmi qualcosa di meglio?

grazie.

[Skarafaz]

up

[gugoXX]

La specifica: "In ordine non decrescente" significa che li vuoi in "ordine crescente" oppure in "ordine qualsiasi, purche' soddisfino il filtro"?
Se l'ordine e' qualsiasi, allora dovrebbe essere sufficiente quanto segue, altrimenti occorre cambiarlo un po', ma si dovrebbe poter fare a paritre da questo:

Originariamente inviato da Skarafaz

successors(k): restituisce un iteratore delle entry del dizionario con chiave maggiore o uguale a k (in ordine non decrescente)

Cerco in il nodo Nk, con ricerca binaria
Dovrebbe essere sufficiente un iteratore su tutti i nodi che sono figli di destra di Nk

predecessors(k): restituisce un iteratore delle entry del dizionario con chiave minore o uguale a k (in ordine non decrescente)

Cerco in il nodo Nk, con ricerca binaria.
Lo cerco con una visita in profondita', prendendo sempre la strada di sinistra.
Restituisco tutti i valori, fino a che non trovo il primo > di k. Termino senza restituirlo.

[Skarafaz]

Parlo di ordine "non decrescente" perchè nel dizionario potrebbero esserci delle entry con chiave uguale, per cui parlare di ordine "crescente" non è propriamente corretto! Comunque in soldoni si può tranquillamente parlare di ordine crescente!

Esempio
supponiamo che nel dizionario ci siano entry con queste chiavi intere:
1,5,9,12,12,15,24

successors(9) dovrebbe restituire:12,12,15,24

[gugoXX]

Originariamente inviato da Skarafaz

Parlo di ordine "non decrescente" perchè nel dizionario potrebbero esserci delle entry con chiave uguale, per cui parlare di ordine "crescente" non è propriamente corretto! Comunque in soldoni si può tranquillamente parlare di ordine crescente!

Esempio
supponiamo che nel dizionario ci siano entry con queste chiavi intere:
1,5,9,12,12,15,24

successors(9) dovrebbe restituire:12,12,15,24

Ah ok, allora non basta quello che ho proposto...
Se vuoi la lista ordinata occorre pensarci meglio.

[Skarafaz]

up

[gugoXX]

Ah si' scusa.
Ho pensato alla Successors ed ho una soluzione davvero molto semplice, stasera te la posto.
Per la predecessors dovrebbe essere molto molto simile.

[gugoXX]

Eccomi.
La soluzione algoritmica dovrebbe funzionare.
Putroppo l'ho scritta in C# perche' il Java non lo conosco, ma dovrebbe essere adattabile.
Se definisco una classe nodo ragionevolmente come segue:

public class Node
{
     public Node Padre;
     public Node FiglioSinistro;
     public Node FiglioDestro;
     public int valore;
}

Allora un metodo per ottenere i successori potrebbe essere il seguente:

public class AlberoRedBlack
{
    public Node root;
    public IEnumerable<int> Successors(int n)
    {
        return Successors(root, n);
    }

    private static IEnumerable<int> Successors(Node Kn,int n)
    {
        if (Kn.valore > n)
        {
            if (Kn.FiglioSinistro != null)
            {
                foreach (int ret in Successors(Kn.FiglioSinistro, n)) yield return ret;
            }
        }

        if (Kn.valore>=n) yield return Kn.valore;  

        if (Kn.FiglioDestro != null)
        {
            foreach (int ret in Successors(Kn.FiglioDestro, n)) yield return ret;
        }                    
    }
}

In modo tale da poter usare l'enumeratore in un ciclo come questo

     AlberoRedBlack albero = new AlberoRedBlack();
     albero.Load(...qualcosa...);
     foreach (int ret in albero.Successors(9))
     {
         Console.WriteLine(ret);
     }

Non so se Java supporta una sitassi come questa dello
yield return
In pratica lo yield return serve per restituire immediatamente al chiamate un valore dell'enumerazione, che potra' pero' continuare dallom stesso punto in cui si trovava, compreso il livello di ricorsione.
In pratica inizio a navigare l'albero verso sinistra.
Per ogni nodo controllo se il valore e' maggiore della soglia. Se non lo e' magari ho qualche nodo nel sottoalbero di sinistra che devo restituire, che dovra' anche essere il primo restituito dato che li vuoi in ordine non decrescente.
A quel punto entro in ricorsione, fino a che non posso iniziare a restuire veramente qualcosa.

Onestamente pensavo il metodo ricorsivo fosse ancora piu' semplice di cosi'. Avrei sperato di ritornare direttamente l'Enumeratore da ciascun figlio al proprio padre durante la ricorsione.
Non me lo faceva compilare cosi' l'ho dovuto adattare in questo modo, cosi' ho dovuto svolgere i cicli di ciascuno dei due rami.
Ma grazie allo yield il valore viene ritornato direttamente al chiamante.

Il metodo dovrebbe essere l'ottimo, in quanto se non sbaglio viene fatto il minor numero di confronti possibile. Magari si puo' lavorare sulla pulizia del codice, ma ora devo scappare.

Ciau.

[Skarafaz]

GRAZIE MILLE!!!! L'algoritmo mi sembra buono, ora mi metto al lavoro sul codice!!!