La prova per la profondità di albero di ricerca bilanciato

Question

Se T è un BST ottenuta con n elementi, L suo sottoalbero sinistro e R la sua quello giusto, come posso dimostrare che la sua profondità è inferiore o uguale a 2log (n) + 1?

Non è una prova per induzione che ho, ma io non capisco.

(capisco che StackOverflow è principalmente programmazione orientata, ma ho trovato alcune domande su alberi binari di ricerca e ha deciso di fare un tentativo, spero non sto facendo qualcosa non va bene:.))

Answer 1

Per definizione di "bilanciata", profondità di ogni sottoalberi sinistro e destro stesso nodo differiscono al massimo di uno. "Depth" è normalmente definito come "numero di passo di lunga piedi dalla radice verso foglio", così per esempio un BST con una radice e due foglie (tre elementi in unico modo che possano essere disposti in BST bilanciata) è ha detto di avere profondità di uno (sembra che si sta utilizzando una definizione leggermente diversa che darebbe profondità due?), come se si trattasse di una radice e una foglia (se tale foglia è sottoalbero a sinistra oa destra della radice non fa differenza), mentre uno con solo una radice che è anche una foglia (un unico elemento) avrebbe profondità 0. (non c'è BST con zero elementi).

Così per n <= 3 elementi, chiamata D (n) la profondità dell'albero come sopra definito, chiaramente D(n) < log(n) + 1 (con log significato logaritmo a base 2) mediante ispezione, poiché 1 = D(2) < log(2) + 1 = 2 (e anche 1 = D(3) per i quali la RHS di disuguaglianza, log(3) + 1, è infatti > 2), e 0 = D(1) < log(1) + 1 = 1 - questo ci dà la base di induzione

.

Per completare la dimostrazione per induzione dobbiamo dimostrare che, se D(k) < log(k) + 1 per tutti k < n, ne consegue anche che D(n) < log(n) + 1.

Se n è dispari, chiaramente a sinistra ea destra sotto-albero hanno (n-1)/2 elementi ciascuno, e l'albero ha una profondità maggiore rispetto alle sottostrutture 1; ma poi D(n) = 1 + D((n-1)/2) < 1 + 1 + log((n-1)/2) (per ipotesi induttiva) = 1 + log(n-1) (dal log((n-1)/2) = log(n-1) - 1) e quindi un < 1 + log(n) maggior ragione, QED.

Se n è addirittura si seguono solo gli stessi passi con log(n) invece di log(n-1) e senza la finitura "a maggior ragione", e la prova tiene ancora.

Answer 2

La tua risposta è vero se Balanced albero binario è completo il numero di elementi a destra e di sottostruttura sinistra può essere (n-1) / 2, ma se non è completo, il numero di elementi hanno bisogno di non essere (n-1) / 2 come ultimo livello può avere diversi elementi