Come posso provare questa operazione su alberi di ricerca binari?

Question

Vorrei che mi desse un suggerimento per provare questo esercizio dal libro di Cormen: "Dimostra che non importa quale nodo iniziamo in un albero di ricerca binaria altezza-h, k chiamate successive a TREE-SUCCESSOR prendi il tempo O (k + h). "

Answer 1

• Sia x essere il nodo di partenza e z essere il nodo termina dopo k chiamate successive ALBERO-successore.
• Lasciate p essere il percorso semplice tra x e z incluso.
• Lascia che sia l'antenato comune di x e z che p visite.
• La lunghezza di p è al massimo 2h, ovvero O(h).
• Lasciate output essere gli elementi che i loro valori sono compresi tra x.key e z.key inclusi.
• La dimensione di output è O(k).
• Nell'esecuzione di k chiamate successive nell'albero-successore, i nodi che sono p sono visitati, e oltre ai nodi x, y e z, se un albero secondario di un nodo in p è visitato poi tutti i suoi elementi sono in output.
• Quindi il tempo di esecuzione è O(h+k).

Answer 2

Suggerimento: eseguire un piccolo esempio, osservare il risultato, provare a estrapolare il motivo.

Per iniziare, ecco alcune cose da considerare.

Iniziare in corrispondenza di un determinato nodo, k chiamate successive a Tree-Succcesor costituiscono una passeggiata albero parziale. Quanti (almeno e al massimo) nodi visitano questa passeggiata? (Suggerimento: pensa alla chiave (x)). Tieni presente che un margine viene visitato al massimo due volte (perché?).

Suggerimento finale: il risultato è O(2h+k).