# Aiutino per Vasi **URL:** \ **Category:** Aiuto\ **Created:** [29 Aprile 2014, 10:04am UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800 "2014-04-29T10:04:58Z")\ **Posts on this page:** 20\ **Page:** 5
**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\ **Post date:** [18 Luglio 2017, 10:58pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/81 "2017-07-18T22:58:50Z")
Normalmente ogni nodo contiene la propria chiave e, se necessario, un valore. > [@frakkiobello](#): > > nel bst normale l’altezza arriva fino a sqrt(n) In un BST non bilanciato di N nodi l’altezza può essere proprio N - pensa al caso in cui vengono inseriti i valori già ordinati, quello che si forma è una lista, e ogni nodo ha solo un figlio invece di due. > [@frakkiobello](#): > > Questo è quello che ho capito fino ad ora spero sia giusto. Mi manca da vedere bene l’implementazione e come adattarlo a questo problema, perché non capisco come sfruttare questa struttura 😄 In vasi quello che devi fare è supportare tre operazioni fondamentali: inserimento di un valore in una posizione, rimozione di un valore da una posizione, richiesta del valore in una posizione. Tutti e tre possono essere facilmente implementati con un avl, facendo attenzione a non utilizzare i valori come chiavi ma le dimensioni dei sottoalberi di ogni nodo. ---
**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\ **Post date:** [19 Luglio 2017, 1:37pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/82 "2017-07-19T13:37:08Z")
> [@dp\_1](#): > > In un BST non bilanciato di NNN nodi l’altezza può essere proprio NNN - pensa al caso in cui vengono inseriti i valori già ordinati, quello che si forma è una lista, e ogni nodo ha solo un figlio invece di due. Ci avevo pensato infatti, mi ero confuso nel tradurre: `"After a long intermixed sequence of random insertion and deletion, the expected height of the tree approaches square root of the number of keys, √n, which grows much faster than log n"` Scusa ma non ti seguo, tralasciando l’implementazione che mi devo ancore vedere (😅 ), non riesco a capire quali sono gli elementi che deve contenere il mio BST tu parli di “dimensioni dei sottoalberi” ma non collego la cosa con il problema e poi, quale sarà la struttura iniziale dell’albero? E quali sono i valori che devo inserire per esempio"s 2 4"? L’unica cosa che posso pensare è che la chiave sia quella detta da te, mentre il valore associato sia il vaso effettivo ma non ne sono sicuro 😅 Qualche aiutino? 😊 ---
**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\ **Post date:** [19 Luglio 2017, 2:11pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/83 "2017-07-19T14:11:10Z")
Quello che ti serve è una struttura dati che supporti le tre operazioni che ho detto prima. Questo perchè uno spostamento `s a b` è equivalente a eliminare il vaso in posizione a e inserirlo in posizione b, mentre `c a` è proprio la richiesta del valore salvato nella posizione a. Fin qui ci sei? ---
**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\ **Post date:** [19 Luglio 2017, 2:14pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/84 "2017-07-19T14:14:31Z")
Ok si almeno fino a ero arrivato. Grazie delle spiegazioni(😉 ) ---
**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\ **Post date:** [19 Luglio 2017, 2:43pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/85 "2017-07-19T14:43:40Z")
Pensa alla ricerca in un BST (per ora non importa se è bilanciato o meno, il funzionamento è identico, anche se ovviamente se non lo bilanci vai fuori tempo): ``` find(int key, Node *root): if(!root) return -1; if(key < root->key) return find(key, root->left); if(key > root->key) return find(key, root->right); if(key == root->key) return root->value; ``` Il problema è che le chiavi sono in un certo senso implicite: non ci viene mai data una chiave univoca per ogni vaso, ma vengono indicizzati per posizione. Il problema con la posizione è che questa può cambiare con le varie operazioni, e quindi salvarla in ogni nodo non è possibile. Quello che possiamo fare è però mantenere per ogni nodo la dimensione del suo sottoalbero (che sarà 1 se il nodo non ha figli) e utilizzare questa per trovare l’$i$esimo elemento. Quindi quando siamo in un nodo r e stiamo cercando un elemento in posizione p lo avremo trovato se `p == size(r->left)`, andremo a sinistra se `p < size(r->left)` o a destra se `p > size(r->left)`. ---
**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\ **Post date:** [19 Luglio 2017, 2:55pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/86 "2017-07-19T14:55:17Z")
> [@dp\_1](#): > > find(int key, Node \*root): > if(!root) return -1; > if(key \< root-\>key) return find(key, root-\>left); > if(key \> root-\>key) return find(key, root-\>right); > if(key == root-\>key) return root-\>value; Nella find() quindi, usando implicitamente la ricerca binaria dico, se il vaso che sto cercando è uguale a quello che sono ora(partendo dalla radice) restituisco la posizione del vaso (root-\>value) , se è maggiore vado al figlio destro se è minore a quello sinistro e ripeto il procedimento fino a quando trovo il valore desiderato. > [@dp\_1](#): > > lo avremo trovato se p == size(r-\>left), andremo a sinistra se p \< size(r-\>left) o a destra se p \> size(r-\>left). Continuo a non capire 😭, puoi provare con un esempio? ---
**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\ **Post date:** [19 Luglio 2017, 3:03pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/87 "2017-07-19T15:03:40Z")
Guardati [https://en.wikipedia.org/wiki/Order\_statistic\_tree](https://en.wikipedia.org/wiki/Order_statistic_tree), in particolare il funzionamento della funzione `select`, che è il tipo di ricerca necessario per vasi. ---
**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\ **Post date:** [19 Luglio 2017, 3:19pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/88 "2017-07-19T15:19:45Z")
Quindi se un nodo n ha k sotto alberi vuol dire che è il kesimo +1valore più piccolo(?), altrimenti salgo o scendo nell’albero fino a quando si verifica quello detto in precedenza? Perchè avendo k sottoalberi vuol dire che ha k valori più piccoli? ---
**Author:** ![daveede](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/e5b9ba/32.png) [@daveede](https://forum.olinfo.it/u/daveede)\ **Post date:** [21 Marzo 2018, 2:58pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/89 "2018-03-21T14:58:30Z")
Scusate se riapro per la seconda volta il dead post ma sarei interessato anche io a risolvere vasi2, la mia domanda è come faccio a tenere bilanciato l’ albero se devo mantenere intatta l’ informazione della size (ovvero la somma delle altezze dei sottoalberi) ? non va ricalcolata per ogni nodo ogni volta che inserisco un’ elemento? ---
**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\ **Post date:** [21 Marzo 2018, 3:05pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/90 "2018-03-21T15:05:08Z")
Puoi ricalcolare la dimensione in O(1) sapendo quella dei due figli ---
**Author:** ![daveede](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/e5b9ba/32.png) [@daveede](https://forum.olinfo.it/u/daveede)\ **Post date:** [21 Marzo 2018, 3:14pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/91 "2018-03-21T15:14:10Z")
Ok per il nodo inserito va bene, ma devo aggiornare anche tutti quelli sopra di lui? ---
**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\ **Post date:** [21 Marzo 2018, 3:16pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/92 "2018-03-21T15:16:07Z")
Direi proprio di si. Se mantieni l’albero bilanciato si tratta comunque \mathcal O(h) = \mathcal O(logN) operazioni ---
**Author:** ![daveede](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/e5b9ba/32.png) [@daveede](https://forum.olinfo.it/u/daveede)\ **Post date:** [21 Marzo 2018, 3:27pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/93 "2018-03-21T15:27:37Z")
Ok, invece per la questione del bilanciamento? se io uso un albero avl il bilanciamento non interferisce con le dimensioni dei sottoalberi? ![image](https://forum.olinfo.it/uploads/default/original/1X/6c41f581dae9a3e3e9d7321889e0454fe2525142.png) Se questo è l’ albero che rappresenta l’ array di partenza e voglio spostare il 2 in posizione 6 (1 3 4 5 2 6 7) allora elimino il 2 e lo reinserisco come successore di 5 facendolo diventare figlio destro di 5 ? ---
**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\ **Post date:** [21 Marzo 2018, 4:14pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/94 "2018-03-21T16:14:33Z")
Basta che una volta fatta una rotazione ricalcoli le dimensioni dei due nodi “ruotati” a partire dai loro figli ---
**Author:** ![MyK\_00L](https://forum.olinfo.it/user_avatar/forum.olinfo.it/myk_00l/32/3000_2.png) [@MyK\_00L](https://forum.olinfo.it/u/MyK_00L)\ **Post date:** [1 Giugno 2019, 12:06pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/95 "2019-06-01T12:06:38Z")
Scusate se riapro questa discussione dopo tanto tempo, ma mi e’ sorta una curiosita’: ho provato a risolvere vasi2 sia con treap che con avl e i treap prendono 40 per TLE. Capisco che i treap dovrebbero essere piu’ efficenti degli avl nel caso ci siano tante modifiche rispetto alle query. Considerato questo, qualcuno mi puo’ illustrare su quale potrebbe essere il bbst che performerebbe meglio in questo problema?[🤔](https://forum.olinfo.it/badges/17/lettore) ---
**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\ **Post date:** [1 Giugno 2019, 12:12pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/96 "2019-06-01T12:12:01Z")
Prova a dare un occhiata a questo: [https://en.m.wikipedia.org/wiki/Y-fast\_trie](https://en.m.wikipedia.org/wiki/Y-fast_trie) ---
**Author:** ![MyK\_00L](https://forum.olinfo.it/user_avatar/forum.olinfo.it/myk_00l/32/3000_2.png) [@MyK\_00L](https://forum.olinfo.it/u/MyK_00L)\ **Post date:** [1 Giugno 2019, 3:13pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/97 "2019-06-01T15:13:16Z")
La ringrazio per la risposta immediata signor Borto. [😘](https://es.wikipedia.org/wiki/Aborto) In effetti questi dovrebbero avere una complessita’ migliore in questo problema, ma sembrano molto complicati, un’implementazione dei Y-fast potrebbe davvero migliorare i tempi in questo problema o le costanti sarebbero troppo alte? ---
**Author:** ![giacomogallina](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/e495f1/32.png) [@giacomogallina](https://forum.olinfo.it/u/giacomogallina)\ **Post date:** [25 Luglio 2019, 6:29pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/98 "2019-07-25T18:29:01Z")
Sai se c’e’ qualche modo elegante per implementarne uno? [🛴](https://www.youtube.com/watch?v=l0hait9qXOE) ---
**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\ **Post date:** [26 Luglio 2019, 3:57pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/99 "2019-07-26T15:57:34Z")
Purtroppo ne so poco a riguardo ma so che @lukecavabarrett ne ha implementato uno ---
**Author:** ![filippos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/filippos/32/103_2.png) [@filippos](https://forum.olinfo.it/u/filippos)\ **Post date:** [29 Ottobre 2019, 1:43pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/100 "2019-10-29T13:43:39Z")
Dopo averne discusso a lungo con @MyK_00L, abbiamo trovato un linguaggio di codifica che parrebbe essere una valida opzione per il tuo peculiar dilemma: [Monicelli](https://github.com/esseks/monicelli) 😇 🥶 🤠 🍉 [Pagina precedente](https://forum.olinfo.it/t/aiutino-per-vasi/3800.md?page=4) [Pagina seguente](https://forum.olinfo.it/t/aiutino-per-vasi/3800.md?page=6)