Altura promedio de un árbol de búsqueda binaria

Question

¿Cómo se calcula la altura promedio de un árbol de búsqueda binario al agregar 1000 entradas aleatoriamente? ¿Cuál es la altura promedio?

Answer 1

Puede calcular la altura de un árbol binario utilizando esta definición recursiva:

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

Una forma de medir empíricamente la altura media de un árbol tal es crear repetidamente un árbol vacío y añada 1000 elementos aleatorios para eso. Mida la altura de cada prueba usando la función anterior y promedie.

que sospecha que su tarea es probable encontrar una fórmula para la altura media de un árbol binario.

Answer 2

depende del orden en que se agregan. Si comienza con el valor más pequeño, el árbol será más profundo porque todos los valores nuevos se agregarán al BST secundario derecho. Si agrega el valor más grande primero, el hijo izquierdo será profundo mientras que el derecho estará vacío.

Answer 3

Depende de si usted está usando alguna especie de estructura de árbol de equilibrado (como un árbol rojo-negro). Dado que está insertando números aleatorios en un árbol binario, sería razonable esperar que la profundidad promedio sea aproximadamente log2 (1000), por lo que los valores 10 y 11 serían 'normales'. No estoy seguro de hasta qué punto podría desviarse de eso; no menos profundo que 10 niveles, posiblemente algo más profundo. Un caso extremo sin equilibrio sería 1000 de profundidad; es poco probable que suceda con números aleatorios.

Answer 4

Independientemente de lo que el árbol está utilizando la altura media será log2 (1000), como alguien ha mencionado antes. Es cierto que dependiendo del orden de los números insertados, la altura real puede variar, pero asumiendo los números distribuidos al azar, que mencionas, el valor real se aproximará, en la mayoría de los casos, al valor esperado (que, una vez más, es log2 (1000))

Answer 5

Esta pregunta es, de hecho, engañosa. La respuesta no será 1000, porque eso es improbable, pero log2 (1000) también es improbable, pero aún más dependiendo de cómo se cultive el árbol.

si se agrega un int mediante la intensificación de que el árbol entonces ingenuamente anexando que el árbol será prácticamente siempre será más alto que log2 (1000).

Hable con un estadístico, porque esto parece estar relacionado con las distribuciones de probabilidad normales. Esos son generados por muchos eventos aleatorios iterados (encabeza una unidad a la derecha, las colas lo mismo que a la izquierda), y el valor de un entero aleatorio itera a través del árbol a medida que se establece en una hoja.

Answer 6

Esta pregunta me tiene que pregunta si se puede trabajar definitivamente esto sin llegar a la generación de los árboles.

me las arreglé para escribir una aplicación que podría calcular la respuesta a lo que sería la altura media si se ha añadido cada posible permutación de N números únicos a un árbol binario en práctica ingenua.

Las respuestas que obtuve están en este gráfico. (El eje X es el número de elementos en el árbol, la línea azul es la altura media, y la línea roja es la altura óptima posible)

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

Granitebolshevik tiene razón: es posible pero estadísticamente improbable que un árbol implementado ingenuamente sea la altura óptima, sin una funcionalidad adicional de equilibrio.

El algoritmo tiene una complejidad de O (N^2), y no es lo suficientemente rápido para calcular números realmente grandes.

Answer 7

No parece ser una respuesta sencilla a esta pregunta, sin embargo hay una serie de aproximaciones numéricas, por ejemplo .:

Devroye, Luc. "Una nota sobre la altura de los árboles de búsqueda binarios". Journal of the ACM (JACM) 33.3 (1986): 489-498.

Reed, Bruce. "La altura de un árbol de búsqueda binaria aleatorio". Revista de la ACM (JACM) 50.3 (2003): 306-332.

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

Estas aproximaciones generalmente toman la forma: A ln n - B ln ln n + C

Dónde A~4.311 y B~1.953

Así que probablemente lo más útil que decir es que la altura media de las inserciones al azar es O(log n), pero si realmente necesita una aproximación numérica, creo que (4.311 ln n - 1.953 ln ln n) estaría lo suficientemente cerca para n grande.

Para n=1000, que da alrededor de 26 - que se ajusta muy bien a los resultados experimentales informados en otros lugares.