Encuentra la mediana en O (1) en el árbol binario

Supongamos que tengo una BST balanceada (árbol de búsqueda binaria). Cada nodo de árbol contiene un campo especial count, que cuenta todos los descendientes de ese nodo + el nodo en sí. Llaman a esta estructura de datos order statistics binary tree.Encuentra la mediana en O (1) en el árbol binario

Esta estructura de datos compatible con dos operaciones de O (log n):

rank(x) - número de elementos que están a menos de x
findByRank(k) - encontrar el nodo con rank == k

Ahora me gustaría agregar una nueva operación median() para encontrar la mediana. ¿Puedo suponer que esta operación es O (1) si el árbol está equilibrado?

Fuente

2012-08-10 Michael

Creo que la mediana sería la raíz del árbol – Gir

Estoy de acuerdo con Gir. Pero esto solo es cierto si el árbol está completamente equilibrado. – brano

Si el árbol está completo (es decir, todos los niveles están completamente llenos), sí puede.

Fuente

2012-08-10 12:22:26

¿Qué sucede si un árbol está equilibrado pero no está "completo"? – Michael

puede usar el conteo para decidir qué camino tomar. no estoy seguro acerca de O (1) en este caso, aunque – Gir

@Michael Depende de su definición de equilibrado, si sabe que ambos subárboles de la raíz tienen exactamente el mismo número de hijos, la raíz será la mediana. –

A menos que el árbol esté completo, la mediana podría ser un nodo de hoja. Entonces, en general, el costo será O (logN). Supongo que hay una estructura de datos con propiedades solicitadas y con una operación O (1) findMedian (tal vez una lista de omisiones + un puntero al nodo mediano; no estoy seguro acerca de las operaciones findByRank y rank) pero una BST balanceada no es uno de ellos.

Fuente

2012-08-10 13:48:35

Sí, podemos implementar una estructura de datos _special_ para encontrar la mediana en O (1), p. 2 montones binarios o una lista de omisiones, como sugieres. Sin embargo, me pregunto si puedo hacerlo con el BST equilibrado y aumentado. – Michael

En un árbol de estadísticas de orden equilibrada, encontrar la mediana es O (log N). Si es importante encontrar la mediana en el tiempo O (1), puede aumentar la estructura de datos manteniendo un puntero a la mediana. La captura, por supuesto, es que necesitarías actualizar este puntero durante cada operación Insertar o Eliminar. La actualización del puntero tomaría el tiempo O (log N), pero como esas operaciones ya toman el tiempo O (log N), el trabajo extra de actualizar el puntero mediano no cambia su costo de O grande.

Como una cuestión práctica, esto solo tiene sentido si realiza muchas operaciones de "búsqueda de mediana" en comparación con el número de inserciones/eliminaciones.

Si lo desea, puede reducir el costo de actualizar el puntero mediano durante Insertar/Borrar en O (1) usando un (doubly) threaded binary tree, pero Insertar/Borrar seguirá siendo O (log N).

Fuente

2012-08-11 20:39:42

Encuentra la mediana en O (1) en el árbol binario

Respuesta

Cuestiones relacionadas