altezza media di un albero binario di ricerca

Question

Come si fa a calcolare l'altezza media di un albero binario di ricerca durante l'aggiunta di 1000 interi casuali? Qual è l'altezza media?

Answer 1

È possibile calcolare l'altezza di un albero binario utilizzando questa definizione ricorsiva:

height(empty) = 0 
height(tree) = 1 + max(height(tree.left), height(tree.right)) 

Un modo per misurare empiricamente l'altezza media di un tale albero è quello di creare più volte un albero vuoto e aggiungere 1000 articoli casuali esso. Misurare l'altezza di ogni prova usando la funzione sopra, e mediali.

ho il sospetto il vostro compito è probabilmente quello di trovare una formula per l'altezza media di un albero binario.

Answer 2

dipende l'ordine sono aggiunti. Se inizi con il valore più piccolo, l'albero sarà più profondo perché tutti i nuovi valori verranno aggiunti al BST figlio destro. Se aggiungi prima il valore più grande, allora il figlio sinistro sarà in profondità mentre il diritto è vuoto.

Answer 3

Dipende se si sta utilizzando qualsiasi tipo di struttura ad albero bilanciato (come ad esempio un albero rosso-nero). Dato che stai inserendo numeri casuali in un albero binario, è ragionevole aspettarsi che la profondità media sia approssimativamente log2 (1000), quindi i valori 10 e 11 sarebbero "normali". Non sono sicuro di quanto lontano potrebbe deviare da ciò; non più profondo di 10 livelli, forse un po 'più profondo. Un caso estremo senza bilanciamento sarebbe 1000 profondi; è improbabile che accada con numeri casuali.

Answer 4

Indipendentemente da quale albero si utilizza l'altezza media sarà log2 (1000), come qualcuno ha detto prima. E 'vero che a seconda dell'ordine dei numeri inserito l'altezza effettiva può variare, ma assumendo i numeri distribuiti in modo casuale, che voi dite, allora il valore effettivo, il più delle volte, approssimare il valore atteso (che, ancora una volta, è log2 (1000))

Answer 5

questa domanda è, infatti, difficile. La risposta non sarà 1000, perché è improbabile, ma anche log2 (1000) è improbabile, ma ancora di più a seconda di come viene coltivato l'albero.

Se si aggiunge un int facendo un passo anche se l'albero poi ingenuamente aggiungendo che l'albero sarà virtualmente sempre più alto di log2 (1000).

Parla con un esperto di statistica, perché questo sembra essere legata a normali distribuzioni di probabilità. Quelli sono generati da un sacco di eventi casuali iterati (testa una unità a destra, code ditto a sinistra), e il valore di un intero casuale itera attraverso l'albero mentre si deposita in una foglia.

Answer 6

Questa domanda mi ha fatto chiedere se è possibile lavorare definitivamente questo fuori senza realmente generare gli alberi.

sono riuscito a scrivere un'applicazione che potrebbe calcolare la risposta a ciò che l'altezza media sarebbe se si è aggiunto ogni possibile permutazione dei numeri unici N ad un albero binario ingenuamente implementato.

Le risposte che ho ricevuto sono in questo grafico. (L'asse X è il numero di elementi nella struttura, la linea blu è l'altezza media, e la linea rossa è l'altezza ottimale possibile)

 
N  Average Height 
2  2 
16 7.039 
32 9.280 
64 11.679 
256 16.783 
343 17.896 

Granitebolshevik ragione: è possibile ma statisticamente improbabile che un albero ingenuamente implementato sia l'altezza ottimale, senza funzionalità di bilanciamento extra.

L'algoritmo ha una complessità di O (N^2) e non è abbastanza veloce per calcolare numeri veramente grandi.

Answer 7

Non sembra essere una semplice risposta a questa domanda, anche se ci sono una serie di approssimazioni numeriche, es .:

Devroye, Luc. "Una nota sull'altezza degli alberi di ricerca binari." Journal of the ACM (JACM) 33.3 (1986): 489-498.

Reed, Bruce. "L'altezza di un albero di ricerca binario casuale." Journal of the ACM (JACM) 50.3 (2003): 306-332.

http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap13.htm

Queste approssimazioni generalmente prendono la forma: A ln n - B ln ln n + C

Dove A~4.311 e B~1.953

Quindi probabilmente la cosa più utile da dire è che l'altezza media per inserimenti casuali è O(log n), ma se effettivamente hai bisogno di un'approssimazione numerica, penso che (4.311 ln n - 1.953 ln ln n) sarebbe abbastanza vicino per il grande n.

per n=1000, che fornisce circa 26 - che si adatta perfettamente ai risultati sperimentali riportati altrove.