[Algoritmi] RB-tree contenente n nodi ha altezza O(n)

[eusebi1]

Domanda:

Un RB-tree contenente n nodi ha altezza O(n) ?

Possibile risposta:
Si se completamente sbilanciato e con tutti i nodi neri
Se con i nodi rossi alternati e sbilanciato O(n/2)
Se bilanciato O(log n)
------------------------------------------------------------
Domanda:

Sia H una max-Heap contenente n chiavi intere, priva di ripetizioni. Indicare quali tra le seguenti affermazioni sono vere,
motivando brevemente le risposte.

a. BuildHeap(H) ha complessita (n);
No O(n log n)
b. Posso sempre ordinare H con un algoritmo avente complessita O(n);
No mai
c. Posso sempre trovare il mediano di H in tempo O(n);
Si O(n) d. Posso sempre trovare il mediano di H in tempo O(log n).
Si applicando partion e la procedura select per il pivot

Corretto??

[hamming_burst]

"eusebi":Domanda:

Un RB-tree contenente n nodi ha altezza O(n) ?

no

Possibile risposta:
Si se completamente sbilanciato e con tutti i nodi neri

anche se sbilanciato è limitato.

Se con i nodi rossi alternati e sbilanciato O(n/2)

sempre limitato

Se bilanciato O(log n)

al più 2log(n) se ricordo bene.

Domanda:

Sia H una max-Heap contenente n chiavi intere, priva di ripetizioni. Indicare quali tra le seguenti affermazioni sono vere,
motivando brevemente le risposte.

a. BuildHeap(H) ha complessita (n);
No O(n log n)

O(n) post549206.html#p549206 vedi seconda parte

b. Posso sempre ordinare H con un algoritmo avente complessita O(n);
No mai

ok per il limite inferiore sull'ordinamento

c. Posso sempre trovare il mediano di H in tempo O(n);
Si O(n)
perchè sì?

d. Posso sempre trovare il mediano di H in tempo O(log n).
Si applicando partion e la procedura select per il pivot

forse hai invertito le risposte...

[eusebi1]

Grazie mi son riguardato le cose e mi torna. Il mio ragionamento sui RB-tree non era molto chiaro. Siccome sono dei Bst ho pensato al caso degenere ma se le foglie sono sempre nere e nil per la condizione sulla lunghezza dei percorsi non posso avere
una fila di elementi neri.
Ho solo un dubbio sulla complessità della ricerca della mediana nel caso di un array ordinato (non è questo il caso però).