Un albero AVL con valori ripetuti e doppio confronto

Question 1

Ho la necessità di creare una struttura di dati (utilizzando principalmente gli alberi AVL) di oggetti con due valori: livello (non unica) e id (che è unico).

Ho necessità di sostenere la ricerca per id, la stampa, l'ordine dei livelli, così come la fusione di due alberi e mantenere queste funzionalità con il nuovo albero.

Ho già diverse soluzioni in mente, ma volevo chiedere informazioni su uno specifico:

Funzionerà per implementare questa struttura con un singolare albero AVL in cui due nodi sono prima rispetto in base al loro livello, e quindi il loro id? Per lo più faccio fatica a rendersi conto di come l'unione di due alberi di lavoro, in particolare nel caso di Un albero, dove tutti gli oggetti sono di livello x e albero B, dove tutti gli oggetti sono di livello y.

EDIT: Anche per la ricerca di id in aggiunta ci sarà un solo albero ordinato per id.

Potrebbe questo metodo di lavoro?

Question 2

singolare albero AVL in cui due nodi sono prima rispetto in base al loro livello, e quindi il loro id?

Purtroppo non c'è. Se non che non sarà in grado di trovare in modo efficiente un nodo per id-avrete bisogno di guardare attraverso tutti i possibili 'livelli', che non hai specificato quindi presumo che può essere illimitato.

Penso che si potrebbe desidera inserire ogni nodo in due distinti alberi AVL, invece. Un albero AVL ordine nodi di livello, gli altri dalla loro identificazione. Tutte le query, inserimenti, eliminazioni e si fonde può essere fatto su ogni albero separatamente.

In altre parole devi creare due indici dei tuoi dati.

Nel codice:

struct Node {
    int id;
    int level;

    // by id
    int id_bf;
    Node *id_left, *id_right;

    // by level
    int level_bf;
    Node *level_left, *level_right;
};

EDIT: Anche per la ricerca di id in aggiunta ci sarà un solo albero ordinato per id.

Quindi essenzialmente descrivere la stessa cosa come me. Tuttavia, il vostro albero ordinati composito (level, id) la chiave è dispendioso; tutto ciò che serve è un albero ordinato per (level) e un albero ordinato per (id) (scalare le chiavi). Non c'è bisogno, tra le operazioni che hai fornito, per l'ordinamento (level, id) e (id).

Yakov Galka · Answer 1 · 2021-11-23T19:29:44

singolare albero AVL in cui due nodi sono prima rispetto in base al loro livello, e quindi il loro id?

Purtroppo non c'è. Se non che non sarà in grado di trovare in modo efficiente un nodo per id-avrete bisogno di guardare attraverso tutti i possibili 'livelli', che non hai specificato quindi presumo che può essere illimitato.

Penso che si potrebbe desidera inserire ogni nodo in due distinti alberi AVL, invece. Un albero AVL ordine nodi di livello, gli altri dalla loro identificazione. Tutte le query, inserimenti, eliminazioni e si fonde può essere fatto su ogni albero separatamente.

In altre parole devi creare due indici dei tuoi dati.

Nel codice:

struct Node {
    int id;
    int level;

    // by id
    int id_bf;
    Node *id_left, *id_right;

    // by level
    int level_bf;
    Node *level_left, *level_right;
};

EDIT: Anche per la ricerca di id in aggiunta ci sarà un solo albero ordinato per id.

Quindi essenzialmente descrivere la stessa cosa come me. Tuttavia, il vostro albero ordinati composito (level, id) la chiave è dispendioso; tutto ciò che serve è un albero ordinato per (level) e un albero ordinato per (id) (scalare le chiavi). Non c'è bisogno, tra le operazioni che hai fornito, per l'ordinamento (level, id) e (id).

Grazie per la risposta, purtroppo ho dimenticato di menzionare che, inoltre io sono un albero ordinato per id per questa funzionalità. Ho pensato a te la soluzione che vi ho appena state chiedendo su questo particolare soluzione di un compagno di classe mi ha detto che penso che non funzionerà a causa della fusione,
@user3917631: un albero ordinato da (livello, id) è ordinato secondo (livello). Quindi, se si dispone di un albero ordinato da (id) in aggiunta a quelli, sarete in grado di eseguire le operazioni in modo efficiente, proprio come ho descritto. È un po ' uno spreco per l'ordinamento (livello, id) se ti serve (livello).
Lo so, sto solo chiedendo di interesse, può funzionare? E ' possibile avere due alberi ordinati per (livello, id) sia numeri interi e li fondono in O(n) (n numero di combinato nodi).
@user3917631: sì è possibile, e non diverso dalla fusione di due alberi ordinati per qualsiasi altra cosa. Binari di ricerca, alberi confronto basato, in modo che non "cura" che cosa stai usando per il tuo tasto finchè si tratta di un insieme totalmente ordinato. Una tupla di numeri interi è un set. Articolo di Wikipedia su alberi AVL viene descritto come eseguire efficiente unione; ci si chiama unione europea. Tuttavia, se si desidera memorizzare il nodo di altezza invece di un fattore di equilibrio per farlo.

Un albero AVL con valori ripetuti e doppio confronto

Domanda

Migliore risposta

In altre lingue

Questa pagina è in altre lingue

Popolare in questa categoria

Domande popolari in questa categoria