Una mediana de un AVL. ¿Cómo aprovechar la AVL?

8

Aquí está la fuente de mi pregunta.

Dado un árbol de auto-equilibrio (AVL), codifique un método que devuelva la mediana.

(Mediana: el valor numérico que separa la mitad superior de una muestra de datos de la mitad inferior. Ejemplo: si la serie es

2, 7, 4, 9, 1, 5, 8, 3, 6

entonces la mediana es 5.)

Puedo ofrecer la siguiente solución:

  1. Atraviesa el árbol dado, devuelve el número de elementos.
  2. Atraviese n / 2 + 1(si nes extraño) el árbol nuevamente aplicando un recorrido de árbol en orden. El valor del n / 2 + 1elemento th es la mediana.

Pero puedo hacerlo con un árbol de búsqueda binario, ¿no? ¿Hay un mejor algoritmo para un AVL?

Maksim Dmitriev
fuente
1
El enlace ya responde a su pregunta: ¿qué más está buscando?
Yuval Filmus
Por lo general, los algoritmos de búsqueda para un Árbol de búsqueda binaria funcionan con un árbol AVL, pero con un AVL obtienes la garantía adicional de que la altura de tu árbol es logarítmica en la cantidad de nodos.
jmite

Respuestas:

9

Si modifica el árbol AVL almacenando el tamaño del subárbol en cada nodo en lugar de solo su altura, puede encontrar la mediana en el tiempo usando el hecho de que el árbol está equilibrado. Para lograr esto, se escribe un procedimiento más general Seleccionar el cual acepta un nodo y un número , y encuentra el ésimo nodo más pequeño en el subárbol con raíz en .O(logn)vkkv

Suponga que el subárbol izquierdo (si lo hay) tiene nodos. Si , recurrimos al subárbol izquierdo. Si entonces devolvemos . De lo contrario, recurrimos al subárbol derecho, reduciendo en .LkLk=L+1vkL+1

El tiempo de ejecución de este algoritmo es lineal en la altura del árbol, que es .O(logn)

Yuval Filmus
fuente
¿Me podría dar un ejemplo?
Maksim Dmitriev
No, tendrás que construir uno tú mismo. Trate de entender lo que mi algoritmo está tratando de lograr y cómo.
Yuval Filmus
Mi solución está en codereview.stackexchange.com/q/104525/23821
Maksim Dmitriev el
0

AVL es un árbol de búsqueda binario con alguna propiedad especial: es un árbol de equilibrio automático. Su altura siempre es logarítmica. El árbol binario ordinario en el peor de los casos se puede vincular a la lista (si agrega datos ordenados) por lo que su altura es n. El árbol AVL en el peor escenario es el árbol fibonacci.

usuario3371350
fuente