costo amortizado del árbol desplegable: costo + P (tf) - P (ti) ≤ 3 (rankf (x) - ranki (x)) explicación

Question

Al leer acerca de los árboles desplegables encontré alguna expresión sobre el rango del nodo desplegable 'X' y el costo amortizado en wikipedia. Se da como, { Podemos unido el coste amortizado de cualquier operación de zig-zig o en zig-zag por:

amortized cost = cost + P(tf) - P(ti) ≤ 3(rankf(x) - ranki(x)), 

donde X es el nodo que está siendo movido hacia la raíz, y los subíndices "f" e "i" indican después y antes de la operación, respectivamente. Cuando se suma a toda la operación de separación, este se telescópica a 3 (rango (raíz)) que es O (log n). Como hay como máximo una operación en zig, esto solo agrega una constante.}

No puedo interpretar esto. ¿Puede alguien explicar los detalles en detalle por favor? Si es posible con algunos ejemplos.

Sírvanse proporcionar algunos enlaces para las explicaciones de otros teoremas de árbol biselado

, gracias

Answer 1

Usted desea llevar a cabo un simple análisis amortizado del árbol biselado estáticas. Si toma un zigzag básico como el ejemplo en wikipedia. es el peor caso senario. y usted tiene:

P (TF) - P (ti) ≤ 3 (rankf (x) - Ranki (x))

Prueba: con la notación utilizada en la wikipedia, puesto que x está en el raíz del árbol en el después de la transformación, puede fácilmente llegar:

rankf (x)> = rankf (g) y rankf (x)> = rankf (f)

por lo tanto,

PTF = rankf (x) + rankf (g) + rankf (p) < = 3 * rankf (x)

Con María Dolores El discurso opuesto con x antes de la transformación que se obtiene:

Pti = Ranki (x) + Ranki (g) + Ranki (p)> = 3 * Ranki (x)

que pueda generalizar eso a toda la operación para calcular el costo amortizado.

Supongo que muestra el resultado, pero no estoy seguro de que sea lo que estaba buscando.