Full transcript
0:04Buenos días y bienvenidos a la clase. E
0:11hoy día vamos a abordar el problema de
0:16analizar problemas de búsqueda binaria
0:18desde un punto de vista
0:21casi opuesto al que hemos tomado antes.
0:25Esto es algo que vamos a llamar
0:28análisis.
0:30del borde
0:35para árboles de búsqueda binaria.
0:50Supongamos que tenemos un cierto árbol
0:52de búsqueda binaria, eh, y marquemos con
0:55un punto los lugares donde hay una
0:57llave. Ah, todos los nodos internos
0:59tienen una llave en su interior.
1:11Ya. Y dibujemos también las hojas.
1:20Las hojas representan punteros nulos,
1:24por lo tanto, en realidad no tiene
1:26ninguna llave en su interior,
1:28lo cual
1:30no necesariamente va a ser cierto
1:32siempre. Ah, pero es cierto en este
1:34caso.
1:36E, okay.
1:39Lo que vamos a llamar el el borde del
1:41árbol son básicamente
1:44las hojas. Entonces,
1:49entonces
1:57eso es lo que llamamos el borde
2:03y en inglés French.
2:11Y la diferencia que vamos a tener entre
2:15este enfoque y lo que hemos hecho antes
2:18es que anteriormente
2:20hemos, por ejemplo, estudiado el largo
2:22de la rama derecha, ¿no? Que por
2:25supuesto lo mismo que el largo de la
2:26rama izquierda, ¿no?
2:28Y en base a eso, después hemos visto
2:30cuál es el costo esperado de de una
2:33inserción,
2:36perdón, de una búsqueda infructuosa que
2:38corresponde a lo mismo que la inserción
2:39en realidad. E pero siempre partiendo de
2:43la raíz hasta llegar al punto de destino
2:45y tratando de calcular cuál es esta
2:46distancia, ¿no es cierto?
2:49Hoy día y en las alguna de las clases
2:52que vienen nos vamos a a nos vamos a
2:55enfocar esto al revés.
2:57Vamos a examinar solamente lo que ocurre
2:59en el borde y vamos a ignorar lo que
3:00pasa más arriba. Eh, y vamos a ver e que
3:04a pesar de eso igual vamos a ser capaces
3:06de eh recuperar los mismos resultados
3:09que habíamos obtenido antes e incluso
3:11llegar más allá. Ah, y ¿por qué puede
3:15ser eso? Si solamente estamos mirando lo
3:17que ocurre en las hojas, es porque las
3:19hojas en realidad acarrean toda una
3:21historia. No han llegado a estar ahí de
3:24la nada. Ah, de hecho el árbol al
3:27principio consistía solo de una hoja que
3:29estaba en el en la raíz, ¿no es cierto?
3:30Y a partir de las sucesivas inserciones
3:33fuimos obteniendo hojas que están más
3:35abajo y más abajo y más abajo, pero de
3:36alguna manera la posición donde están
3:38ahora reflejan lo que es la historia.
3:40Así es que no por mirar solo lo que pasa
3:43en las hojas, yo estoy ignorando lo que
3:45pasa más arriba. Eh, vamos a ver de qué
3:47manera eso resulta ser cierto. Okay,
3:51para referirnos a
3:54a la posición donde están eh estas
3:58hojas, vamos a hablar de niveles dentro
3:59del árbol.
4:02Entonces vamos a
4:07vamos a decir que la raíz
4:10está a nivel cero, los hijos de la raíz
4:13están a nivel uno, eh y así
4:16sucesivamente.
4:18Ya.
4:26Y así sucesivamente.
4:28Ahora, ¿en qué se
4:32es más esquemáticamente
4:35podemos decir que que nuestro árbol
4:38ya
4:41tiene una cierta estructura de ese
4:42estilo
4:44donde arriba están todos los nodos
4:47internos, ¿no es cierto?
4:49Y acá abajo están todas las hojas.
4:57Y ese es el borde del que estamos
4:59hablando. Okay. Ahora, ¿cuál cuál va a
5:03ser nuestro enfoque aquí? Eh, supongamos
5:06que vamos a hacer una inserción.
5:09Pongamos aquí en en otro color
5:13una inserción.
5:18una inserción es como una búsqueda
5:19infructuosa. Yo voy a, supongamos que yo
5:23voy recorriendo
5:26eh bueno, parto de la raíz, por
5:28supuesto, eh veo si lo que yo estoy
5:31tratando de insertar es menor o mayor
5:34que la raíz. Ah, no debera de poder ser
5:36igual porque estamos hablando de llaves
5:38primarias, las llaves primarias no se
5:39repiten, así que o es menor o es mayor,
5:41supongamos que que es menor, ¿ya? Y
5:45comparado con ese otro, supongamos que
5:46es mayor, ¿ya? Y supongamos que
5:48comparado con este también es mayor y
5:51comparado con este es menor. Entonces
5:53terminamos finalmente en este punto.
5:57Ya. Si esto fuera una búsqueda
5:59infructuosa, esa hoja sería el punto de
6:01término de la búsqueda. Pero como es una
6:04inserción, lo que va a pasar es que
6:06justo en ese punto vamos a colocar un
6:09nodo interno,
6:12o sea, un nodo circular
6:14y van a aparecer dos hojas, un nivel más
6:17abajo. Ah, en este caso vendría a ser
6:19hasta altura al nivel 5.
6:22Okay.
6:23Por lo tanto, el efecto de una inserción
6:35es que eh
6:39es que si yo tengo una hoja
6:42en el nivel K
6:45y la inserción
6:47llega
6:49hasta este punto, termina en esa hoja,
6:55Entonces ese elemento que viene entrando
6:59se instala en un nodo interno que se
7:02crea para este efecto y que reemplaza la
7:04hoja en su lugar.
7:07Ya.
7:09Y aparecen dos hojas,
7:14un nivel más abajo.
7:20Eh, ese es el efecto de una de una
7:23inserción. una hoja se transforma en un
7:26nodo interno con dos hojas eh un nivel
7:28más abajo. Eh, ahora supongamos
7:38que el árbol
7:42eh tiene
7:45n llaves,
7:48¿ya? Esto implica que tiene
7:52n + 1 hojas, ¿no es cierto? Siempre el
7:54número de hojas es uno más que el número
7:56de nodos internos.
7:58y eh y la desde el punto de vista de la
8:03inserción vamos a suponer que todas las
8:06hojas son x probables.
8:27respecto
8:30de una inserción.
8:39esa
8:41esa suposición eh es no trivial, ah eh
8:46pero es razonable.
8:48Si por ejemplo, si yo estoy insertando
8:54n + 1 eh llave, ya eh que siempre yo
8:58puedo suponer que son los números del 1
8:59al n + 1, porque lo único importa entre
9:02ellos, como decíamos el otro día, es la
9:04relación de orden que hay. Ah, no
9:06importan los valores eh que eh que
9:09[resoplido] tienen, sino que solo el
9:10orden entre esos valores. Entonces, eh
9:13yo puedo siempre suponer que son los
9:15números del uno en adelante. Eh y
9:19si yo inserto los números del uno en
9:20adelante, eh y esta secuencia viene en
9:23orden aleatorio, ¿okay?
9:26Eh, si yo tomo los n primeros y
9:29construyo un árbol con ellos y luego
9:32llega el último, ese último, como esto
9:34es una permutación aleatoria, tiene la
9:36misma probabilidad de ser el mínimo de
9:38todos o el que está en el segundo orden
9:41en el ranking o en el tercero o incluso
9:43en el orden n + 1. Puede ser que el
9:46último por casualidad sea el máximo,
9:48¿cierto? Y y como todas las
9:50permutaciones son equobables, entonces
9:52este último tiene la misma probabilidad
9:54de ser el mínimo, el segundo, el tercero
9:56o el o el máximo. Ya. Eh, la
9:59probabilidad es 1 parido por n + 1. Y si
10:02es el mínimo y lo estamos insertando en
10:04un árbol como aquí,
10:07entonces va va a venir a dar a esta
10:09hoja.
10:11Si es el segundo en el ranking, entonces
10:14va a ser mayor que este, pero va a ser
10:16menor que todos los demás. Entonces se
10:17va a venir a esta hoja, ¿ya? Y así
10:19sucesivamente. Si es el máximo va a
10:23venir a dar a esta hoja, ¿no es cierto?
10:26Entonces, eh y todos esos casos son
10:28equobables. Por eso es que es tiene
10:30sentido, es razonable suponer que todas
10:32las hojas son equobrables respecto de
10:35una de una inserción. Ya, otra forma de
10:39de argumentar esto mismo que requiere un
10:41poquito más de de cálculo tres
10:44es e suponer que las eh llaves que yo
10:49estoy insertando son números reales
10:52obtenidos por muestreos eh
10:56eh independientes a partir de una
10:58distribución, por ejemplo, uniforme 01.
11:01Entonces, todos números reales entre 0 y
11:03un elegidos al azar. ¿Okay?
11:05Eh, y supongamos yo ya he muestreado n
11:09eh de estos números, ¿okay? Y y luego
11:15muestreo el siguiente.
11:18¿Cuál es la probabilidad de que el
11:19siguiente sea menor que todo? ¿Cuál es
11:20la probabilidad que est entre el primero
11:22y el segundo? Ah, ¿cuál es la
11:23probabilidad que sea mayor que todo?
11:25Bueno, los neros que yo hice al comienzo
11:29son n variables aleatorias que ordenadas
11:32me definen n más un intervalo. Entonces,
11:34lo que yo tengo que hacer es todas las
11:36integrales múltiples para poder llegar a
11:37calcular la probabilidad de que un nuevo
11:41punto elegido al azar caiga en el primer
11:42intervalo, en el segundo o en el último.
11:45Ya. Y si uno hace todas las integrales,
11:49resulta que la probabilidad es uniforme,
11:511 parido por n + 1. ¿Ya? Así que eso es
11:54otro elemento que argumenta en favor de
11:56que este es un modelo razonable. Ahora,
11:59¿por qué yo dije que no siempre? Ah,
12:01porque eh supongamos que yo tengo un
12:07pequeño arbolito, por decir algo, de
12:09tamaño dos, ¿ya? Entonces, un arbolito
12:11de tamaño dos tiene una raíz y tiene un
12:15nodo que cuelga hacia la izquierda o a
12:16la derecha. Supongamos que cuelga hacia
12:18la izquierda, ¿ya?
12:20Eh, y supongamos ahora que yo eh elimino
12:25un dato en ese árbol y justo el que
12:27estaba colgando ahí. Entonces, ahora lo
12:29que queda es la pura raíz, ¿no es
12:30cierto? Y ahora después de haber hecho
12:32esa
12:34esa eliminación,
12:36inserto un dúo elemento. La pregunta es,
12:39¿cuál es la probabilidad que caiga a la
12:41izquierda o a la derecha? Uno diría un
12:43medio. 1 medio, ¿no es cierto? Pero no,
12:45o sea, no porque estos números,
12:47supongamos que fueron números reales
12:48muestreados. Independientemente yo
12:51mostré el uno que quiso fue la raíz,
12:53mostré el otro que cayó a este a este
12:55lado y ahora mostró el tercero. El hecho
12:59que se que el segundo ya no está en el
13:02árbol da lo mismo. Des el punto de vista
13:04del mostreo probabilístico, ese es ese
13:08ese de dato existe. De modo que cuando
13:12llega un un tercero
13:15va a caer con la misma probabilidad a la
13:17derecha del eh máximo del perdón, a la
13:21derecha de la raíz entre la raíz y donde
13:25estuvo el que eliminé
13:28o al lado de acá del que eliminé. O sea,
13:31el que eliminé es como un fantasma que
13:32todavía existe y los datos entrantes
13:35pueden caer a su izquierda o a su
13:36derecha, aunque él no esté.
13:38Por lo tanto, la probabilidad de que
13:40este nuevo dato caiga a la derecha de la
13:43raíz es un tercio y la probabilidad de
13:45que caiga a la izquierda es 2 tercios. A
13:48pesar de que el árbol mismo se ve como
13:50una raíz con dos hojas coloqueando al
13:52lado y lado, pero esas dos hojas ya no
13:54son equrbables debido a la historia.
13:57Eso complica absolutamente todo. Ah,
14:00porque eso este es el siguiente, el
14:01primer paso no más. Supongamos que este
14:03ciclo yo lo repito. En cada inserción yo
14:05elimino un elemento del árbol y en la
14:07siguiente inserto, elimino, inserto,
14:08elimino, inserto. Después de eso ya eh,
14:12¿cuál es la probabilidad de caer en la
14:13hoja izquierda o derecha? es sumamente
14:15difícil de saber, ¿no? Así es que eh
14:21muy importante, vamos a suponer que la
14:26probabilidad
14:30que la probabilidad
14:32de que eh la inserción
14:39caiga
14:42en una
14:44hoja dada.
14:50es igual a 1 parido por n + 1,
14:56suponiendo que no hay eliminaciones.
15:12[suspiro]
15:15El caso de cómo analizar esto cuando hay
15:19eliminaciones es un problema casi
15:22completamente abierto.
15:26El el
15:29caso que yo les describí, este caso
15:31pequeñito
15:33con
15:35dos, tres elementos, ese fue analizado
15:38por Can y un coautor que en este momento
15:43su nombre se me escapa
15:45y es un análisis bastante complicado que
15:49cuando
15:51eh que si se hace con detalle, como
15:54hicieron ellos, eh,
15:58implica la aparición en la solución de
16:00funciones de Vésel, ¿no? Eh, y es
16:03solamente y es un caso tan pequeño, eh,
16:06el caso general está completamente
16:08abierto,
16:10muy muy difícil. Hay experimentos al
16:13respecto, hay resultados experimentales,
16:16pero resultados analíticos yo diría que
16:18prácticamente nada.
16:20Así es que para todos nuestros efectos,
16:22vamos a todos nuestros análisis se van a
16:25fundamentar en esta suposición de que no
16:27hay eliminaciones eh en el en el árbol.
16:31Entonces, vamos, lo que vamos a hacer
16:34ahora es vamos a definir
16:38a sub n k
16:41igual al número esperado
16:46de hojas.
16:49en el nivel K,
16:55en un árbol, en una bebé
17:01con n llave.
17:04Ese esta función a su nome acá va a ser
17:08el el objetivo de nuestro estudio. Ah e
17:14bueno, ¿qué condición de borde tiene
17:16esto? a sub0 comaca.
17:21Eh, ¿qué pasa en un árbol con cero
17:22llaves? Un árbol con cero llaves
17:24consiste exclusivamente de una hoja nada
17:27más que está al nivel cero. Okay. Eh,
17:32nivel por que no parezca un nodo
17:34interno.
17:36Está al nivel cero, ¿cierto? Entonces,
17:39si en el nivel k = 0 hay una hoja y en
17:44los otros niveles hay cero, ¿ya? Por lo
17:46tanto, eso es un delta de cronicer que
17:48en este caso lo escribimos así k = 0,
17:52una función indicatriz. Ya, esa función
17:55vale un cuando cae cer y cer en todos
17:58los demás casos. Ya. Eh, ahí tenemos una
18:01condición de borte. Y ahora supongamos
18:12que se produce una inserción aleatoria.
18:26Okay. Su se produce una inserción
18:28aleatoria y veamos qué efecto tiene esa
18:30inserción aleatoria sobre el número de
18:32hojas en cada nivel. Entonces ahora lo
18:35que vamos a tener entonces es cuánto
18:37vale a sub n + 1, k, ¿cierto? ¿Cuántas
18:42hojas hay en el nivel k ahora que el
18:45árbol tiene n + 1 llave?
18:48comparado con lo que pasaba antes cuando
18:49había n llave. Entonces, el número de
18:52hojas en el nivel que a causa de una
18:56inserción no varía mucho, ¿no es cierto?
18:58No va a ser tan distinto antes o después
19:01de de que yo hice la inserción. Por lo
19:04tanto, nuestro punto de partida es que
19:05el número de hojas que hay en el nivel K
19:07es el mismo que había antes,
19:11¿ya?
19:13Pero puede haber una leve variación,
19:18¿cierto?
19:20Eh, ¿cómo?
19:22Porque
19:25si la inserción
19:28aleatoria
19:30cayó justo un nivel más arriba que el
19:33nivel K, o sea, el nivel K -1,
19:37entonces
19:39esa hoja que había ahí arriba se
19:43transformó en un nodo interno circular y
19:46aparecieron dos hojas un nivel más
19:47abajo, o sea, en el nivel K.
19:50Por lo tanto, es posible que a las hojas
19:51que había en el nivel K, yo tenga que
19:54sumarle dos
19:56con alguna probabilidad. ¿Cuál es la
19:58probabilidad? La probabilidad de que la
20:00inserción haya caído justo un nivel más
20:01arriba. ¿Y cuál es la probabilidad que
20:03la inserción haya caído justo un nivel
20:05más arriba? Bueno, es el número de hojas
20:07que hay un nivel más arriba, o sea, a
20:10sub n - 1 dividido por el total de hojas
20:13que existen, que es siempre n + 1. ¿Ya?
20:16Por lo tanto, eh hay que sumar dos hojas
20:20con probabilidad a sub n k - 1 dividido
20:25por n + 1.
20:28Ya, pero eso no es todo.
20:33También es posible que yo tenga que
20:35restarle hojas a lo que hay en el nivel
20:38K.
20:39¿Por qué? Porque a lo mejor la inserción
20:42que hay justo en el nivel K. Y si es
20:44así, esa hoja en donde cayó ya no existe
20:48porque ahora es un nodo interno. A
20:49cambio hay dos hojas en el nivel
20:51siguiente, ¿no es cierto? Pero en este
20:52nivel hay una hoja menos. Entonces, hay
20:55que restar una hoja
20:59con la probabilidad de que la inserción
21:00haya caído justo en este nivel y eso es
21:03a sub n k
21:07dividido por n + 1.
21:11Ahí tengo una ecuación de de
21:14recurrencia.
21:17Okay.
21:19Entonces, eh
21:22introduzcamos
21:31la función generatriz
21:38a su n z, perdón, no coma z.
21:44[suspiro][grito ahogado]
21:47a su n de z
21:52como la sumatoria
21:53para acá mayor o igual que 0 de a su n k
21:59por z a la k. ¿Ya?
22:02Entonces la función generatriz
22:04es e transforma la variable k en la
22:08variable z.
22:11Entonces, eh si yo le aplico función
22:15generatriz
22:17a la
22:20a la a la ecuación que acaba de obtener,
22:23ya me va a quedar a sub n + 1 de z
22:31igual a sub n de z
22:36+ 2. Y fíjense que la variable a es k -
22:411. Ustedes se acuerdan que la generatriz
22:43de a sub n - 1 decíamos en esa época
22:46cuando n era la variable que estamos
22:48estudiando, en este caso es cap, e eso
22:52implica multiplicar por z.
22:55Entonces esto va a ser eh 2 z
23:03por a sub n de z y todo eso partido por
23:06n + 1
23:09y este de acá va a ser menos
23:13eh a su n dez
23:22partido por n +
23:24No hay Z en este caso porque es la misma
23:26variable K, ¿no es cierto? Y a subcero
23:30de Z, ¿cuánto va a valer?
23:32La generatriz del delta croner es un
23:37y aquí tengo mis
23:39unas ecuaciones en de funciones
23:41generatrices.
23:43Y esto lo puedo reescribir como que a
23:45sub n + 1 de z
23:49igual a 1
23:53más
23:552z - 1
23:58paro por n + 1
24:02y todo eso multiplicando por a su n z,
24:04¿cierto?
24:07O sea, el efecto de la inserción
24:11ya es que eh
24:15la función generatriz
24:17se tiene que multiplicar por 1 + 2z - 1
24:21par n + 1 y con eso obtenemos la
24:23siguiente la función genérriz
24:26correspondiente a un árbol con una llave
24:28más.
24:29Okay. Y y por supuesto parto con a sub0
24:34de z = 1.
24:45Okay.
24:48Muy bien. Eh, de hecho, hay otra manera
24:51de obtener esta ecuación. Antes de
24:53resolverla vemos otra manera de obtener
24:55esta ecuación que nos va a servir para
24:56más adelante.
25:18Observemos
25:22el efecto
25:25de una inserción aleatoria
25:35sobre
25:37una hoja
25:40en el nivel K.
25:45Ya no veamos ninguna otra hoja, solo
25:48una. Entonces, la idea es que yo tengo
25:51aquí un árbol,
25:54¿ya? Y
25:58y tomo una hoja de nivel K y observo qué
26:01le pasa cuando viene
26:05una inserción.
26:12Entonces, una hoja en el nivel K yo la
26:16represento por Z a la K, ¿cierto? Z a la
26:20K es una función generatriz que me
26:22cuenta una hoja que esté en el nivel K.
26:26Okay. Y ahora viene la inserción.
26:34¿Y qué es lo que ocurre?
26:36Hay
26:38dos posibilidades, que la inserción
26:42afecte, caiga justo en esta hoja o que
26:45no. ¿No es cierto?
26:49Pongámonos primero en el caso que la
26:51inserción no caiga en esta hoja. Hay n
26:53más una hoja, así es que la probabilidad
26:56de que no caiga aquí es super grande,
26:58¿no es cierto? Bueno, pero ¿cuánto es la
26:59probabilidad de que no caiga justo aquí?
27:01Es 1 - 1/ por n + 1, ¿no es cierto? Ya,
27:06porque con probabilidad 1 partido por n
27:07+ 1, la inserción va a caer justo ahí.
27:10Por lo tanto, la probabilidad
27:10complementaria es que caiga en cualquier
27:13otra parte menos aquí. Y si cae en
27:15cualquier otra parte menos aquí, esta
27:17hoja que esté en el nivel K sigue siendo
27:20la misma hoja que sigue estando en nivel
27:22K. Entonces, con probabilidad
27:251 - 1/ por N + 1,
27:31esto sigue siendo una hoja en el nivel
27:33K.
27:36Pero,
27:38¿qué pasa con la probabilidad
27:39complementaria? Con probabilidad 1/ido
27:41por n + 1.
27:44Con probabilidad 1 parido por n + 1.
27:47Esta la inserción cae justo en esta hoja
27:51y por lo tanto esta hoja ya deja de
27:55estar en el ya
27:58no es una hoja en el nivel K. Ahora se
28:00transformó en dos hojas en el nivel K+
28:021. Entonces
28:06se transforma en dos Z a la C+ 1.
28:11Z la C+1 porque está un nivel más abajo
28:13y dos porque ahora son dos hojas. Esta
28:15hoja como que explotó
28:17y y se transforma en dos hojas un nivel
28:19más abajo. Okay.
28:22Entonces
28:24aquí es el antes de la inserción.
28:30Y esto es el después.
28:36Ya. Por lo tanto, esta hoja que está en
28:40el nivel K, el efecto que una inserción
28:43tiene sobre ella es que
28:46ahora esto es 1
28:49eh más
28:522 - 1
28:54dividido por n + 1
28:57por z la k.
29:00O sea, el efecto que tiene sobre una
29:02hoja es multiplicarse por ese factor.
29:05Eh, y ahora por superposición yo puedo
29:10lograr el efecto sobre el conjunto total
29:12de las hojas.
29:14Ya. Eh, multiplico por el número de
29:17hojas que hay en el nivel K, que es AV
29:21N.
29:23Y sumo sobre todo K. Y lo que me queda
29:26es la generatriz a la izquierda y a la
29:28derecha me queda ese factor por la
29:30generatriz. O sea, esto implica
29:34que ahora el a sub n de z, ¿cierto?
29:40A partir de de lo anterior por
29:43superposición, como digo, va a ser igual
29:46a 1 +
29:492z - 1
29:53por su z.
29:57que es lo mismo que habíamos encontrado
29:59antes, por supuesto, ya, pero esta vez
30:02obtenido de esta de esta otra manera.
30:06Okay, muy bien. Esto esto es bueno
30:09tenerlo en mente porque más adelante
30:11vamos a analizar procesos bastante más
30:13complicados que eh se que la mejor
30:16manera de abordarlo es es por esta,
30:18viendo el efecto sobre sobre una hoja y
30:20luego eh
30:23por superposición, ¿no es cierto?,
30:24haciendo la combinación lineal,
30:26obtenemos la función generatriz, el
30:28efecto sobre toda la función generatriz.
30:30Muy bien. Entonces, ahora resolvamos la
30:32ecuación. Ya, ya hemos encontrado dos
30:34maneras de derivar la ecuación. Ahora
30:36resolvámosla,
30:40que es s simple, ¿no?
30:49A ver, esta
30:52ecuación la podemos reescribir como que
30:53a su n de z.
31:02Voy a poner de de común n + 1.
31:06Entonces va a quedar 2z - 1 más
31:13más n.
31:17A ver, eh, aquí tengo
31:20un pequeño error,
31:22¿sí o no?
31:25Eh, claro.
31:27Déjeme corregir al tiro el pequeño error
31:32porque lo que hay a la izquierda no es
31:33el a sub n de z,
31:35sino que la sub n + 1 de z.
31:40Eso ahí. Okay.
31:44Ya. Eh,
31:51ya. Y acá entonces también sería lo
31:52mismo.
31:59Entonces sería a su n + 1 de z. Eh,
32:03tomando denominador como un n + 1 sería
32:06n + 1 + 2z - 1 2 + n, ¿no es cierto?
32:17Ya. Eh, para desenrollar,
32:22vamos a desenrollar esto.
32:27Reescribamos
32:32para a su n,
32:35entonces lo corro en uno. Entonces, a su
32:37n de z va a ser igual a 2z + n - 1. Y
32:43acá tamb y acá va a ser n y acá va a
32:46estar a su n - 1 z. Ya, así me resulta
32:49un poquito más fácil para desenrollar.
32:53Entonces ahora esto eh va a ser 2z + n -
32:581
33:00por n y desenrollo la sub n - 1.
33:02Entonces va a ser 2z
33:05+ n - 2 obtivo por n - 1 por a sub n - 2
33:13de z, ¿cierto?
33:15Y si sigo aquí voy a llegar
33:202z + n - 1 activo por n
33:252z + n - 2 paro por n - 1.
33:32Y yo quiero llegar hasta sub cero.
33:35Eh, fíjense que eh el subíndice que hay
33:38aquí es lo mismo que yo sumo acá.
33:42Entonces, si llego hasta sub voy a
33:44llegar hasta 2Z + 0, o sea, 2z.
33:48Y este que está acá es uno más que este,
33:50por lo tanto, en ese caso va a ser uno.
33:53Ya. Entonces, al desenrollar yo voy a
33:55llegar hasta 2 z partido por 1 por a sub
34:00de z, que por supuesto
34:05es 1.
34:11Y por lo tanto
34:15a su n Z.
34:19Si ahora yo lo leo de derecha a
34:20izquierda,
34:22va a ser
34:262z * 2z + 1, 2 z + 2 hasta 2z + n - 1 n
34:30factores, o sea, es una potencia
34:33factorial ascendente, ¿no es cierto? Y
34:36el denominador va a ser n por n - 1
34:38hasta 1, o sea, n factorial.
34:42O sea, va a ser 2 z
34:46a la n ascendente
34:48partido por n factorial.
34:52Y eso es lo mismo que el coeficiente
34:54binomial simétrico
34:562 z - 1 n.
35:04Ya, esa es la
35:09ese es la
35:12función generatriz a su n de z
35:16que
35:18en las clases anteriores ya la hemos
35:19encontrado, la hemos encontrado por otro
35:21método. Ah, totalmente distinto, pero
35:23por supuesto es la misma porque esa es
35:24la solución. Ahora, esto es número de
35:27hojas. A mí, si yo quiero estudiar, por
35:30ejemplo, la eh el costo de búsqueda
35:33infructuosa, ya eh ahí lo que yo
35:36necesito es la probabilidad de que una
35:39búsqueda termine en en una hoja del
35:42nivel K, por ejemplo. Ya. Eh, ¿cómo pasó
35:46el número de hoja probabilidad?
35:47Dividiendo por n + 1, ¿cierto? Si haya
35:50sub n k hojas, la probabilidad de
35:53terminar justo ahí es a su n dividido
35:55por n + 1. Entonces definamos
36:04eh P sub N como K
36:09igual la probabilidad
36:11de que una hoja aleatoria
36:20este es del nivel K
36:26porque esa es la probabilidad que la
36:29búsqueda infructuosa que termina esta
36:32hoja tenga costo K, eh, y eso va a ser a
36:36sub n k dividido por n + 1.
36:44Y por lo tanto,
36:46p sub n de z
36:51va a ser a sub n de zido por n + 1
36:59y esto va a ser igual a
37:09dividido por n + 1.
37:12Ya.
37:13Y esa es la función generatriz de
37:15probabilidad del costo de búsqueda
37:17infructuosa en un árbol de búsqueda
37:19binaria, que es algo que antes ya lo
37:21encontramos, pero lo encontramos a
37:24través de este método de estudiar el
37:25largo de la rama derecha y luego a
37:27partir de ahí encontrar el largo de una
37:30de una búsqueda infructuosa y la función
37:33generativa de probabilidad resultante es
37:36la que ustedes ven ahí, ¿no es cierto?
37:39también eh ahí se obtiene la
37:46eh eh si uno lo ve como estos procesos
37:48de lanzamiento de monedas que aparecían
37:50en la charla de Canus, ¿no?
37:54Si yo tengo un proceso de lanzamiento de
37:56monedas que cuya función generatriz es f
37:58de z y después sustituyo z por c* z 2 z
38:03en este caso, ya eh después tengo que
38:06normalizar dividiendo por f de c f de2
38:09en este caso, que es justamente lo que
38:11pasa aquí. Este denominador es lo que es
38:14necesario para normalizar y que esta
38:15función generatriz eh sea sea
38:18efectivamente de probabilidad. ¿Okay?
38:21Eh, porque se verifica
38:27que
38:29Pun de 1,
38:31¿cuánto es? Si Z es 1, esto sería 1, n
38:36por n + 1, pero 1, n es n + 1, por lo
38:40tanto esto es 1. O sea, check.
38:44Ahora nos interesa
38:51estudiar
38:55el mus, que es el average de p de z
39:01y el sigma cuadrado sub n, que es la
39:04varianza
39:06de p subn de z. Okay. Entonces, ¿cómo lo
39:12cómo lo vamos a hacer?
39:18Eh,
39:20bueno, PU de Z
39:26e es, si vamos a
39:29al sub n es 2z a la n ascendente partido
39:33por n factorial, ¿no es cierto? Entonces
39:362 la ncendente
39:38va a ser 2z
39:42por 2z + 1
39:45hasta 2z + n - 1
39:51dividido por n factorial,
39:56pero como ahora está dividido además por
39:58n + 1, va a ser n + 1 factorial u, o
40:01sea, va a
40:07va a ser 1 * 2 * 3 hasta por n + 1.
40:16Entonces, eh
40:19el uno me voy a olvidar de él y voy a
40:21agrupar así este
40:25es s ese así es que esto
40:28yo lo puedo escribir como la pitatoria.
40:34de eh 2z + jido
40:42por j
40:47menor igual que j menor o igual que n-
40:501, ¿cierto?
40:52Claro, porque para j = 0 es 2z/ por 2 y
40:55ahí voy sumando uno arriba y sumando uno
40:57abajo.
40:59Para el último j = n - 1.
41:03Eh, arriba va a ser 2 z + n - 1 y abajo
41:07va a ser n + 1. O sea, che se queda
41:10bien.
41:13Ahora, esto
41:16entre paréntesis yo lo podría escribir
41:18así
41:20como la pitatoria
41:24de eh por un lado puedo poner el jartido
41:28por jido
41:34por j.
41:40Y esto es lanzamiento de monedas,
41:51¿cierto? Esta es la esto es la
41:54probabilidad de cara
41:57y esta es la probabilidad de sello.
42:00Así que esto se puede interpretar como
42:01lanzamiento de unidad.
42:05Eh, okay. Ahora, eh,
42:10ustedes se acuerdan que el average de un
42:14producto es la suma de los averages y
42:17que el bar de un producto es la suma de
42:21los bar. Ya. Así es que eh para poder
42:26hacer esto, yo necesito ver cuánto es el
42:29average
42:31de 2 + J.
42:35parti por j + 2.
42:38[grito ahogado]
42:39Y eso es fácil porque hay que derivar
42:41respecto de zal en 7 = 1. Así es que
42:43queda 2 par por junto
42:48es el par de 2z + jido
42:54por j.
42:57Ahí tengo que derivar dos veces y evalu
43:01= 1, pero al derivar dos veces esto es
43:02ceru,
43:06o sea, 2 par por j
43:11al cuadrado, o sea, 4 par por j
43:16al cuadrado.
43:19Y por lo tanto
43:22el muso n va a ser la suma
43:27de 2 parido por j
43:34menor o igual que j menor o igual que n-
43:371.
43:40Y si esto lo desenrollamos va a ser dos
43:42factor de que para acero va a ser 1/2
43:47después un tercio, después un cuarto
43:52y el último va a ser 1/ido por n + 1.
43:58Así que esto yo lo puedo escribir como
44:01dos.
44:03Lo que hay ahí adentro es casi el número
44:05armónico hn + 1,
44:10pero le falta el uno inicial, por lo
44:13tanto lo sumo para completar el armónico
44:15y lo resto.
44:18Y ahí tengo
44:21el esto es sería
44:24el costo
44:27esperado
44:31de búsqueda
44:35infuctuosa,
44:40eh, dos veces un número armónico.
44:44Y la varianza, ¿qué pasa con la
44:45varianza?
44:52sigma cuadrado sub n
44:55va a ser la
45:03eh
45:06bueno, va a ser la sumatoria
45:09de 2 par j
45:120 menor o igual que j menor igual que n
45:14- 1
45:16menos sumatoria de 4 parido por j²
45:23en el mismo rango
45:28y eso es 2
45:32hn + 1 - 1, ¿no es cierto? lo que ya
45:34calculamos para el mu
45:39eh pasa algo parecido, pero para
45:42armónicos de segundo orden. Igual le
45:45falta el primer término, así es que hay
45:46que sumarlo y restarlo, así que va a
45:49quedar -4
45:52h
45:54n + 1, pero de segundo orden, que los
45:57denominadores están elevado al cuadrado
45:59y -1.
46:02Así es que esto
46:05esto eh pasado en limpio sería
46:112 hn + 1.
46:18Aquí tengo -2 + 4, o sea, má 2
46:24y -4
46:29H n + 1 de segundo orden, ¿ya?
46:34donde el hn de segundo orden es igual a
46:39la suma
46:41para 1 menor o igual que j menor igual
46:43que n de 1/
46:56en general
47:02HN de orden S
47:06es 1 partido, perdón, sumatoria, falto
47:11sumatoria de 1/ido por j
47:15menor o igual que j menor igual que n y
47:18se sabe
47:23que HN de S converge a una constante
47:30para
47:31S mayor que un para igual un no es el
47:36logaritmo e pero para ese mayor que uno
47:39converge una constante en particular
47:48HN de segundo orden
47:52converge a pi cuadrado sexos
47:56cuando n tende a infinito.
48:01Ya. Así es que la varianza
48:06esencialmente
48:09una
48:14eh es una es un logaritmo, es un
48:17armónico ya eh más constante, ¿no?
48:24La constante proviene, por una parte de
48:26la convergencia del del armónico de
48:29segundo orden, de la constante dos que
48:32tenemos aquí,
48:34¿ya? y de la constante gama que que está
48:38escondida dentro del armónico, ¿no? Que
48:41ahí tenemos nuestro análisis para
48:44árboles de búsqueda binaria,
48:46esta vez realizado a través de eh
48:50análisis del borde, fringe analisis, ya
48:53obserando solo lo que ocurre en las
48:55hojas.
48:57Por supuesto, todos estos resultados
48:58reproducen sobre los que habíamos
49:01obtenido antes, si es el mismo proceso
49:02que estamos analizando, pero como este
49:05curso se refiere al análisis de
49:07algoritmo, nos interesa estudiar eh
49:11cuando existen distintos enfoques para
49:13un problema nos interesa verlos todos
49:14porque de esa manera ampliamos nuestra
49:17repertorio de de métodos analíticos, ¿no
49:20es cierto? Y el y el análisis del borde
49:24es uno muy
49:26muy interesante que nos va a permitir
49:28abordar eh problemas como el que viene a
49:31continuación. Pero antes de de ir al
49:34problema que viene a continuación,
49:35veamos si tienen de ustedes algunas
49:37preguntas, algo.
49:39No parece que ha estado claro hasta
49:40ahora.
49:42Entonces, ahora vamos a introducir una
49:45idea bien interesante
49:50que son los
49:53árboles de búsqueda binaria
49:56con mediana de tres.
50:10Ustedes el término mediana de tres
50:12probablemente lo han escuchado,
50:13mencionar antes en relación a
50:17eksicort,
50:20¿cierto?
50:22El algoritmo básico de Quicksort lo que
50:24hace es que escoge un elemento aleatorio
50:28para usarlo como pivote
50:30y luego particiona, ¿no es cierto? Todos
50:32los menores que el pivote van a un lado,
50:33los mayores al otro y después de eso,
50:36recursivamente, ordenamos la mitad
50:38izquierda y ordenamos la mitad derecha.
50:41Ah, mitad entre comillas porque no tiene
50:43por qué ser del mismo tamaño, ¿no es
50:44cierto? Ya. Y eso es recursivo, o sea,
50:47el proceso se reproduce más abajo.
50:50Bueno, eh ese proceso
50:53eh
50:56tiene eh si el si el si el pivote se
51:02elige al azar, en realidad no hay no hay
51:05mucho problema. Ah eh, pero eh hay
51:08algunas implementaciones o había, pero
51:11ah porque no creo que se siga
51:12programando igual, pero había algunas
51:14implementaciones en donde el
51:16razonamiento era el siguiente, decía,
51:18"Si si el conjunto que yo quiero ordenar
51:20ya viene de un orden aleatorio, entonces
51:23como pivote eh yo puedo elegir el primer
51:26elemento del conjunto porque es tan
51:28aleatorio como todos los demás, ¿no es
51:29cierto? y particionar con ese con ese
51:32elemento. Ese argumento en sí es válido
51:36si es que eh el conjunto viene en orden
51:40aleatorio, pero a veces los conjuntos no
51:42vienen en orden aleatorio y y y a veces
51:44incluso tienden a venir ordenados o casi
51:47ordenados porque son el resultado de
51:49algún otro proceso que que los entregó
51:51ordenado. Entonces si si el conjunto ya
51:54viene ordenado y yo escojo el primero
51:56como pivote, la partición va a ser
51:57pésima. A un lado no va a quedar nadie y
51:59al otro lado todos los demás y eso va a
52:01seguir siendo cierto en las llamadas
52:03recursivas. Y al final eh voy a terminar
52:06demorándome en el cuadrado. Ah eh a
52:10pesar de que si el la partición hubiera
52:13sido con un elemento aleatorio, el costo
52:16esperado habría sido no en el cuadrado,
52:17sino que en el log, pero en ese caso
52:20particular el algoritmo Quicksord genera
52:23a un algoritmo cuadrático.
52:26Bueno, conclusión, no tomar el primer
52:28elemento, sino no confiar en que el
52:29primer elemento va a ser aleatorio, sino
52:31que elegir realmente un elemento
52:32aleatorio.
52:34Pero eh otra manera de que se les
52:36ocurrió de contrarrestar ese efecto era
52:39en ese caso no tomar al al eh elegir el
52:44pivote de una manera un poquito más
52:45astuta, tomar tres elementos como
52:49muestra. Ah, el primero, el del medio y
52:52el último.
52:54Y de esos tres elementos, tomar la
52:55mediana de los tres y la mediana usarlo
52:58como como pivote. Ya. Si esos tres
53:02elementos son aleatorios, eh elegir la
53:05mediana, eh vamos a ver que ayuda,
53:08mejora el desempeño del algoritmo
53:11comparado a que si hubiera elegido un
53:12elemento, un solo elemento, ah, hacer la
53:15manera de tres, eh, tiene mejor
53:17desempeño. Eso lo vamos a ver. Ah. Pero
53:19además en el caso patológico, en que el
53:23conjunto ordenar ya venía ordenado,
53:26resulta que al elegir el primero, el del
53:28medio y el último, ah, justo está el del
53:30medio que da la casualidad que es la
53:32verdadera mediana y en ese caso la
53:34partición es la mejor posible,
53:36exactamente mitad y mitad, ¿ya? Así que
53:39lo que era un peor caso se reforma en un
53:40mejor caso. Eh, fantástico. Ya, de ahí
53:43viene la idea de hacer mediana de de
53:45tres. Ah, pero incluso si no fuera ese
53:48caso, ah, el caso en que viene ordenado,
53:50si el conjunto realmente fuera
53:51aleatorio, yo escojo tres elementos para
53:54azar y de ellos tomo la mediana, el
53:56resultado va a ser mejor que si yo
53:58hubiera elegido solo un elemento
54:00aleatorio. ¿Por qué? Porque la mediana
54:04de una pequeña muestra es un mejor
54:07estimador para la verdadera mediana que
54:09si yo tomo solo un elemento.
54:13Cuando uno quiere estimar un parámetro
54:14estadístico y y no lo puede hacer a
54:17través de un de un censo de todos los
54:20elementos del conjunto porque son
54:21muchos, lo que uno hace es que toma una
54:23pequeña muestra, calcula el parámetro de
54:26la muestra y usa eso como un estimador
54:28de del parámetro del conjunto completo.
54:31¿Qué es lo que estamos haciendo en este
54:32caso? Ah, si yo tuve una pequeña muestra
54:35de tamaño tres en este caso, pero podría
54:36haber sido un poquito más grande,
54:37incluso cinco, siete, siempre impar para
54:39que no sea problema en encontrar la
54:41mediana, ¿no es cierto? definir bien la
54:42mediana. Si yo tomo una pequeña muestra
54:45y saco la mediana de la pequeña muestra,
54:48esa va a ser el mientras más grande sea
54:52la pequeña muestra, eh, va a ser un
54:54mejor estimador de la verdadera mediana.
54:57Ya se va a ir aproximando en el límite.
55:00Si la pequeña muestra fuera el conjunto
55:02completo y yo saco su mediana, estaría
55:05encontrando la verdadera mediana, ¿no es
55:06cierto? ¿Qué es el mejor caso para
55:08Quicksort? porque queda exactamente
55:10balanceada la partición, mitad y mitad.
55:12¿Ya? Ahora, ¿qué tiene todo esto que ver
55:15con árboles de búsqueda binaria? Ah,
55:16porque eso es lo que estamos analizando
55:18aquí.
55:19Bueno, los árboles de de búsqueda
55:23binaria son en realidad quicksort
55:27disfrazado.
55:28Es el mismo algoritmo porque eh cuando
55:32yo escojo un elemento al azar y lo uso
55:34como pivote, es como estar el elemento
55:37al azar y usarlo como raíz.
55:39Y cuando yo hago la partición y dejo a
55:42la izquierda los menores, a la derecha
55:43los mayores, es como estar empujando
55:45hacia la izquierda de la raíz todos los
55:47elementos menores y a la derecha todos
55:49los mayores. Y cuando digo que en cada
55:51lado yo voy a hacer lo mismo
55:53recursivamente, quicksort, acá estoy
55:55diciendo que en cada lado yo voy a
55:57construir un árbol de la misma manera,
55:58recursivo, o sea, le voy a poner una
56:00raíz aleatoria y así y al final lo que
56:02termina resultando es un árbol de
56:03búsqueda binaria.
56:05Ah, de hecho, ese árbol de búsqueda
56:07binaria se llama eh cuando yo corro
56:11Quickslort eh y yo voy anotando cuál fue
56:15el pivote en cada caso, quién quedó a
56:16cada lado y así sucesivamente hacia
56:18abajo, lo que resulta es un árbol que es
56:20un árbol de búsqueda binaria que se
56:21llama el árbol de partición. Bueno,
56:24entonces hay una correspondencia uno a
56:26uno entre un árbol de partición y una
56:27ejecución de quicksort
56:30a estudiar un poquito más adelante. Así
56:32es que todo lo que se puede aplicar a
56:33Quickort se le puede aplicar a los
56:34árboles de búsqueda binaria. ¿Okay? En
56:37todo caso, este algoritmo que vamos a
56:39ver fue inventado independientemente,
56:42pero en realidad al final es lo mismo.
56:44¿Okay? Eh, así que eso lo que en el
56:47fondo lo que va a consistir esto es si
56:49vamos a elegir a la raíz de un árbol, no
56:53conformarnos con el primero que aparece,
56:55sino que esperar hasta que aparezcan
56:57tres. Y cuando aparecen tres, ahí yo
57:01elijo la mediana de ese de ese grupo de
57:03tres elementos. A él lo designo como
57:08raíz y los otros dos siguen su camino
57:11hacia los subárboles. Ya, eso es lo que
57:13vamos a hacer. Entonces,
57:16eh la idea es la siguiente idea. H
57:25eh para
57:28eh
57:32para elegir
57:35a la raíz
57:39de un subárbol.
57:45esperar
57:47hasta
57:50que ese subárbol
57:56tenga tres llaves
58:04y elegir
58:07como raíz
58:11a la mediana
58:16de
58:18esos tres datos.
58:23Esa esa es la idea. O sea, cuando
58:25aparece cuando aparece un
58:31elemento, no tomarlo al tiro como como
58:34raíz, sino que esperar. Ya. Esto esto
58:39hay como dos maneras de verlo. Ah.
58:41Supongamos que yo tengo primero hay una
58:44hoja vacía, entonces aparece un dato ya
58:48y
58:50entonces ahora eso sería eso, ¿no es
58:52cierto?
58:55Eh,
58:56ya, pero
59:00okay, dejémoslo así. Ya aparece el
59:02siguiente dato. Bueno, hay dos
59:03posibilidades, que ese siguiente dato
59:06caiga a la izquierda.
59:12o que caiga a la derecha, ¿no es cierto?
59:14Son simétricos, pero dibujemos los dos.
59:25Okay.
59:27Y después aparece el siguiente dato. Eh,
59:32este, supongamos que aquí cae a la
59:33izquierda.
59:36Izquierda, izquierda y más izquierda
59:38todavía
59:44o que cae a la derecha.
59:53Eh, perdón,
59:57se cae a la derecha. Entonces aquí esto
1:00:00sigue estando como estaba.
1:00:03Este otro cayó acá, ¿no es cierto?
1:00:08Ya. Y desde el árbol, si ahora nos vamos
1:00:11por el camino de abajo acá,
1:00:14puede que el el nuevo elemento que viene
1:00:16entrando caiga justo a la izquierda, ¿no
1:00:17es cierto?
1:00:21Si cae justo a la izquierda, entonces
1:00:24obtenemos ese de ahí, no hay para qué
1:00:26dibujarlo de nuevo, ¿no es cierto? Y si
1:00:28cae justo a la derecha
1:00:30va a ser esto.
1:00:41Okay. Bueno, eso sería si yo dejara
1:00:46a estos árboles evolucionar por su
1:00:48cuenta. Pero como estoy tratando de
1:00:52aplicar esta idea de que antes de
1:00:55comprometerme de que quién va a ser la
1:00:57raíz de un subárbol,
1:00:59eh yo eh me
1:01:03espero hasta que hay tres elementos ahí
1:01:06elijo la mediana y la mediana queda como
1:01:10raíz. Entonces, eso quiere decir que
1:01:14aquí pasa lo siguiente. En este si
1:01:18cuando resultó esto, eso es justo lo que
1:01:20yo quería, que la mediana de los tres
1:01:22quede como raíz y los otros uno a cada
1:01:24lado. Así que estamos bien ahí, ¿no es
1:01:25cierto?
1:01:26El
1:01:28problema está aquí y acá. Bueno, si yo
1:01:32llego a esta situación o llego a esta,
1:01:35yo ahora voy a hacer como que dir una
1:01:38pequeña rotación. No sé si ustedes se
1:01:40acuerdan los abeles para dejar como raíz
1:01:43al del medio y acá una pequeña rotación
1:01:45para dejar raíz al del medio. De modo
1:01:48que al final a través de esa pequeña
1:01:51rotación
1:01:52ya
1:01:57a través de una rotación
1:02:03yo llego a este y a través de una
1:02:05rotación yo llego a ese. O sea, al final
1:02:08de una manera u otra, yo termino siempre
1:02:12llegando a ese, ese es mi objetivo.
1:02:15¿Okay?
1:02:16Entonces, cuando yo llego a ese ese
1:02:20estado,
1:02:22al elemento de de arriba,
1:02:25yo ya lo considero que está en su lugar
1:02:27definitivo. Le pongo un tic ahí, por
1:02:29ejemplo. Ya, ese está en un lugar
1:02:32definitivo, pero eh los otros dos no.
1:02:37Los otros dos, cada uno sigue por su
1:02:39cuenta, ¿ya? O sea, este quedó en el
1:02:43subárbol izquierdo, este quedó en el
1:02:46subárbol derecho, pero ese subárbol
1:02:48izquierdo tiene un solo elemento a la
1:02:49fecha. El de la derecha todavía tiene
1:02:51solo un elemento. Por lo tanto, esos
1:02:54elementos que ustedes ven ahí no tienen
1:02:56ganado su derecho a ser raíz de esos de
1:02:59esos pequeños arbolitos. Tienen que
1:03:01esperar hasta que se forme un quórum de
1:03:03tamaño tres y ahí se va a elegir a quién
1:03:05va a ser la raíz de ese pequeño
1:03:07arbolito. ¿Ya? Entonces, lo que va a
1:03:10ocurrir es que después de un rato yo voy
1:03:14a tener una cosa así.
1:03:16Voy a tener aquí arriba un montón de de
1:03:20elementos que ya
1:03:25ya se ganaron su derecho a a estar en el
1:03:28lugar donde están y nadie los va a mover
1:03:30de ahí. Ya. En cambio, por aquí abajo,
1:03:35en lo que ya podríamos dar el borde,
1:03:41voy a tener
1:03:44elementos
1:03:47que están así, por ejemplo, ya
1:03:51otros que están así,
1:03:57otros que están así.
1:04:01etcétera, ya que son pequeños arbolitos
1:04:05que todavía están a la espera de que se
1:04:08junte el cuero suficiente para poder
1:04:10elegir a quién va a ser la raíz de ese
1:04:12pequeño arbolito. Okay. Eh, mientras
1:04:16tanto están ahí a la espera. Ellos no
1:04:18tienen todavía un titic verde. Ah, están
1:04:20esperando qué va a pasar en en el
1:04:22futuro. Y se fijan que con esto yo he
1:04:26generalizado mi concepto del borde,
1:04:28porque antes yo decía que el borde eran
1:04:30solo las hojas y ahora estoy diciendo
1:04:33que el borde son todos los pequeños
1:04:34arbolitos que todavía están a la espera
1:04:36de que se reúna el cuero suficiente. Ah,
1:04:39entonces eh por ejemplo este de aquí, a
1:04:42este todavía le falta harto para que
1:04:44haya quórum. Falta que llegue un segundo
1:04:46elemento, ¿no es cierto? Cuando va a
1:04:47pasar a ser de este tipo, de este otro.
1:04:49Incluso si estamos aquí, todavía le
1:04:50falta. Cuando llegue el tercero, recién
1:04:52ahí se va a poder determinar quién es la
1:04:54raíz. La raíz va a quedar en la parte de
1:04:56arriba, ah, por así decirlo, con un tic
1:04:58verde y y los dos restantes, este y este
1:05:03otro, van a quedar así en la forma de
1:05:05este, a la espera de que se junte el
1:05:07cuero. ¿Okay?
1:05:09Entonces, eh
1:05:13ahora vamos a hacer lo siguiente. Eh
1:05:17esto de estar dibujando todo el tiempo
1:05:18estos arbolitos, eh, es laborioso, ¿ya?
1:05:23Y además
1:05:25eh por ejemplo,
1:05:28aquí yo estoy distinguiendo si el si
1:05:30cuando había primero uno solo, el que
1:05:32llegó después cayó a su derecha o cayó a
1:05:34su izquierda. En realidad, distinguir
1:05:36entre este caso y el otro es oceoso.
1:05:39Pues no lo mismo si cayó a la derecha o
1:05:40si cayó a la izquierda. Cuando se junta
1:05:42el quórum de tres, ahí se va a decidir
1:05:44quién va a estar realmente como raíz y
1:05:46quién va a estar a cada lado, ¿no es
1:05:47cierto? Entonces, eh voy a simplificar
1:05:50el dibujo.
1:05:55Para simplificar
1:05:59el dibujo,
1:06:03cuando yo tenga esto en el borde,
1:06:07lo voy
1:06:09a representar así,
1:06:13como una hoja con un dato en su
1:06:14interior. Y cuando yo tenga
1:06:17esto
1:06:19en el borde
1:06:23o esto en el borde, está lo mismo.
1:06:30Esto yo voy aentar como una hoja con dos
1:06:33datos en su interior.
1:06:36Y voy a decir que esto es una hoja de
1:06:39tipo uno
1:06:42y esto es una hoja de tipo dos.
1:06:47Okay.
1:06:49Entonces,
1:06:52el efecto de una inserción
1:07:04va a ser que cuando yo tengo una hoja de
1:07:07tipo uno
1:07:10y cae justo un elemento en su interior,
1:07:14entonces cuando llega una cuando llega
1:07:16una
1:07:18una inserción
1:07:21que habría esta es una hoja de tipo uno.
1:07:23Cuando llega una inserción que habría
1:07:24caído aquí o acá,
1:07:27en realidad, bueno, pasa a ser este o
1:07:30este, pero pero en realidad lo estoy
1:07:32representando así. O sea, cuando tengo
1:07:34una hoja
1:07:36con un dato anterior de tipo uno y llega
1:07:39un nuevo dato, simplemente se transforma
1:07:41en una hoja de tipo dos.
1:07:43¿Ya?
1:07:45Y cuando tengo una hoja de tipo dos y
1:07:49llega un nuevo dato que cae ahí, que
1:07:51vendría a ser el caso en que esto cae
1:07:54aquí, aquí, aquí o aquí, aquí, aquí, ahí
1:07:58junto el quórum de tres, ahí yo decido
1:08:01quién va a ser raíz, ¿no es cierto? como
1:08:03aquí
1:08:06y los otros dos quedan uno a cada lado,
1:08:09pero al quedar uno a cada lado son hojas
1:08:11de tipo uno.
1:08:13Así es que esto va a quedar así.
1:08:16va a quedar
1:08:19este que ya por decirlo podría ponerle
1:08:22un tic verde, pero en realidad no hace
1:08:24falta ponerle tic verde ahora
1:08:26porque eh por el hecho de ser dibujado
1:08:29no interno se supone que ya tiene su
1:08:31derecho ganado y nadie lo va a mover de
1:08:33ahí. Ah, y un nivel más abajo quedan las
1:08:38dos hojas de tipo uno,
1:08:42ya que en el fondo significa que estamos
1:08:45volviendo acá e en esta especie de
1:08:48diagrama de transición, ¿no es cierto?
1:08:53Ahora, ¿cómo comenzó todo esto? Comenzó
1:08:55con una hoja, una verdadera hoja vacía.
1:08:59Eso era cuando tenía n = 0 elemento, ¿no
1:09:01es cierto? Y cuando
1:09:03apareció el primer dato, se transformó
1:09:06en una hoja de tipo uno y de para
1:09:08adelante nunca más vimos aparecer hojas
1:09:10de tipo cero. Ah, pero sí existió una
1:09:14hoja de tipo cero al inicio de los
1:09:16tiempos. Ah, entonces las hojas de tipo
1:09:18cero son trancientes, existen solo al
1:09:20inicio y después ya nunca más. Eh, pero
1:09:23son importantes para dar el puntap
1:09:25inicial al proceso. De ahí para adelante
1:09:27eh tenemos solo hojas de tipo uno y dos
1:09:30como hojas que están permanentes dentro
1:09:33del árbol. Ah, entonces ahora si yo
1:09:37fuera a dibujar el árbol, lo que yo
1:09:38tendría
1:09:40sería algo de esta forma.
1:09:44Aquí adentro tengo
1:09:53todos los datos que ya están en su lugar
1:09:57definitivo.
1:09:59Y acá
1:10:01tengo hojas
1:10:04que pueden ser de tipo uno, tipo dos,
1:10:09una mezcla, ¿no es cierto?
1:10:13Y estos están aquí en el borde. Así que
1:10:16con esto ah, bueno, eh
1:10:19inicialmente
1:10:24inicialmente lo que tengo es simplemente
1:10:27una hoja de tipo cero, nada más. Todo mi
1:10:29árbol es una hoja de tipo cero. Ya, pero
1:10:33con esto yo he vuelto a mi definición
1:10:34original del borde. El borde contiene
1:10:37las hojas, solo que en este caso las
1:10:39hojas ya no son espacios vacíos o
1:10:43punteros nulos, ¿no es cierto? Ahora
1:10:45pueden almacenar elementos, pueden
1:10:47almacenar cero, uno o dos elementos.
1:10:51Ya. Así que ese es mi nuevo concepto de
1:10:53hoja,
1:10:55lo cual me permite seguir hablando desde
1:10:57el de del borde tal como lo hacía antes.
1:11:00Okay. Ahora,
1:11:04hay otra cosa que cambia.
1:11:07¿Cuál es la probabilidad
1:11:15de que una inserción aleatoria
1:11:26caiga en una hoja dada
1:11:35según su tiempo.
1:11:42Bueno, la probabilidad de caer en una
1:11:45hoja de tipo cer
1:11:47es 1/ido por n + 1, ¿cierto? Es lo mismo
1:11:50que antes. Eso es cuando son hojas
1:11:52vacías la probabilidad es 1 parti por n
1:11:55+ 1 caer ahí. Pero, ¿cuál es la
1:11:58probabilidad
1:11:59de caer en una hoja que tiene un dato en
1:12:02su interior?
1:12:04Ya.
1:12:06Bueno, vamos a ver qué significa eso.
1:12:09Una hoja que tiene un dato en su
1:12:12interior es una abreviatura, digamos,
1:12:14para este pequeño arbolito.
1:12:17Y este pequeño arbolito tiene dos hojas,
1:12:19dos hojas en el sentido original, ¿no es
1:12:21cierto? ¿En dónde podría caer la
1:12:24probabilidad de caer aquí? es 1/ n + 1.
1:12:26La probabilidad de caer acá es 1/ido por
1:12:28n + 1. Por lo tanto, la suma es 2/ n +
1:12:311.
1:12:35La probabilidad de caer en una hoja dada
1:12:37de tipo 1 es 2 par n + 1.
1:12:42Y por el mismo razonamiento, la
1:12:44probabilidad de caer en una hoja dada de
1:12:47tipo 2
1:12:50es 3/ por n + 1.
1:12:54Porque una hoja de tipo dos
1:12:58aquí o aquí tiene tres posibles puntos
1:13:01de inserción, ¿ya?
1:13:05Así que las hojas ahora ya no son
1:13:11equobables.
1:13:16Ya tengo espacio. Las hojas ya no son
1:13:18equobables.
1:13:20Su probabilidad depende del tipo de hoja
1:13:22que sea.
1:13:24O sea, bueno, por,
1:13:28o sea, en general
1:13:33la probabilidad de caer en una hoja de,
1:13:37a ver,
1:13:40eh, déjenme dibujarlo mejor esto. La
1:13:44probabilidad de caer en una hoja,
1:13:47digamos, de tipo J.
1:13:50Ah, el J indicando que hay J puntitos en
1:13:53su interior es J + 1 parido por N + 1.
1:14:00Esa ya
1:14:02caso J es J puede ser 0 1 o 2, ¿no es
1:14:08cierto?
1:14:10Pero esto está pavimentando el camino
1:14:12para la generalización porque
1:14:16eh
1:14:18el número tres no no
1:14:22tiene nada demasiado especial comparado
1:14:24con otros números impares, ¿no es
1:14:25cierto? Yo podría tener mediana de
1:14:28cinco, mediana de siete. Esperar hasta
1:14:31que haya un cuerum de tamaño cinco para
1:14:33elegir a la raíz o cuerum de tamaño
1:14:35siete para elegir a la raíz. Y en ese
1:14:37caso yo tendría más hojas
1:14:40eh
1:14:42de este de diversos tipos, ¿no es
1:14:43cierto? No solamente tres tipos, tendría
1:14:46más. Bueno, okay. Sigamos adelante.
1:14:50Definamos
1:14:56a sub n k de tipo j.
1:15:02Número esperado
1:15:07de hojas
1:15:11de tipo J
1:15:16en el nivel K
1:15:22en un ABB
1:15:27con
1:15:29N llaves. es
1:15:33un ABB
1:15:34modificado, ¿no? En realidad ABB
1:15:39más mediana de tres.
1:15:45Okay.
1:15:47O sea, no es una B cualquiera, es una B
1:15:49donde yo estoy aplicando esta eurística
1:15:52ah para eh ir designando a la raíz de
1:15:56cada pequeño su árbol. Okay. Ya.
1:16:00Entonces, escribamos ecuaciones.
1:16:03¿Alcanzamos a escribir ecuaciones? Sí,
1:16:04parece que sí. Ya. Eh, ¿qué sería a sub
1:16:08n + 1
1:16:11coma k de tipo 0?
1:16:14Ya, supongamos que yo me concentro en
1:16:16las hojas de tamaño de tipo cero. Bueno,
1:16:19la después de una inserción las hojas de
1:16:21tipo cero.
1:16:23Esto quedó muy muy esquinudo
1:16:29ahí más redondo.
1:16:34Eso
1:16:36tipo cero son las mismas que habían
1:16:38antes. A sub n k de tipo cer, ¿no es
1:16:42cierto?
1:16:43menos las que pierdo, más las que gano.
1:16:45Cuando yo pierdo una hoja de tipo cero,
1:16:48yo pierdo una hoja de tipo cero
1:16:51cuando eh
1:16:55con la probabilidad de que justo eh una
1:16:58inserción caiga en una hoja de tipo cero
1:17:00que estaba en este nivel, ¿no es cierto?
1:17:02Y eso eh la probabilidad va a ser a sub
1:17:06n k de tipo 0
1:17:10partido por n + 1.
1:17:13Ya. Y con esa probabilidad yo pierdo
1:17:18eh, a ver, déjenme escribirlo de otra
1:17:19manera por compatri.
1:17:28Ya yo pierdo eh
1:17:33yo pierdo una hoja.
1:17:36Ah, ya. La probabilidad de caer en una
1:17:38hoja de tipo 1 dada es 1 parido por n +
1:17:411. Y eso hay que ponderarlo por el
1:17:44número de hojas de tipo cero que había
1:17:48en ese nivel. Ahí está. Okay. Lo escrib
1:17:50así. Y y eso son las hojas que yo
1:17:53pierdo. ¿Cuándo gano hoja de tipo cero?
1:17:54respuesta nunca. Ningún proceso genera
1:17:57hojas de tipo cero, solo las que había
1:17:59originalmente, que eran una. En
1:18:01realidad, esta ecuación es es eh es una
1:18:04ecuación general, pero si ustedes la la
1:18:07le ponen los datos iniciales, o sea, que
1:18:09inicialmente hay una solo objetivo uno,
1:18:11lo que está diciendo es que apenas
1:18:13aparece la primera inserción en esa hoja
1:18:14desaparece y no se vuelve a ver nunca
1:18:16más. Ah, así que un poquito ocioso
1:18:18escribirlo así, pero es coherente con lo
1:18:19que viene después. Eh, ¿qué pasa con la
1:18:22hoja de tipo un?
1:18:27La hoja de tipo uno que yo tengo en el
1:18:28nivel caso las que tenía antes,
1:18:33¿cierto? Menos las que pierdo más los
1:18:35que más las que gano. ¿Cuándo yo pierdo
1:18:38una hoja de tipo uno? Cuando cae una
1:18:40inserción justo en esa hoja de tipo uno,
1:18:43¿no es cierto? Y en ese caso yo pierdo
1:18:45una hoja. ¿Con qué probabilidad ocurre
1:18:47eso? Probabilidad 2 partid por n + 1.
1:18:49Porque las hojas de tipo 1 tienen
1:18:50probabilidad 2 partid por n + 1 de que
1:18:52caiga ahí.
1:18:53Y eso hay que ponderarlo por el número
1:18:55de hojas que hay de tipo uno.
1:18:59Eso es la la el número prado de hojas
1:19:01que yo pierdo. ¿Cuándo yo gano hojas de
1:19:04tipo uno? Yo tengo dos maneras de ganar
1:19:07hojas de tipo uno. Uno es cuando una
1:19:10hoja de tipo cero
1:19:13se transforma en una hoja de tipo uno y
1:19:15en ese gano, en ese caso, gano una hoja
1:19:17en el mismo nivel, ¿no es cierto?
1:19:19Entonces yo gano una hoja de tipo 1 con
1:19:23probabilidad 1/ido por n + 1 ponderado
1:19:26por el número
1:19:29de hojas de tipo cero que hay ahí.
1:19:33Y la otra forma que yo gano hojas de
1:19:35tipo uno
1:19:39es cuando eh aquí en esta vuelta aquí de
1:19:44aquí para acá ya cuando la inserción cae
1:19:47en una hoja de tipo dos que está en el
1:19:50nivel k - 1 y en ese caso yo gano dos
1:19:54hojas de tipo uno en el nivel K, ¿ya?
1:19:59Entonces ahí se hace un poquito más
1:20:01complicado, hay que escribirlo con
1:20:02cuidado.
1:20:04Entonces yo voy a ganar
1:20:06dos hojas de tipo uno, ¿no es cierto? Y
1:20:12y cuando yo caigo en una hoja de tipo
1:20:14dos y eso ocurre con probabilidad 3
1:20:17parido por n + 1, ponderado por el
1:20:20número de hojas de tipo dos que hay.
1:20:25¿Ya? ¿Y qué pasa con las hojas de tipo
1:20:27dos?
1:20:33en el nivel K. Ya. Bueno, las hojas de
1:20:36tipo dos en el nivel K que hay ahora son
1:20:40las que había antes,
1:20:42menos las que pierdo más las que gano.
1:20:46Cuando yo pierdo una hoja de tipo dos,
1:20:49yo pierdo una hoja de tipo dos cuando la
1:20:51inserción cae justo en esa hoja de tipo
1:20:53dos. Entonces yo pierdo una hoja con la
1:20:57probabilidad 2 par por n + 1, que es la
1:21:00probabilidad de caer, perdón, 3 3 no es
1:21:03cierto
1:21:063 parido por n + 1, que es la
1:21:07probabilidad de caer en una hoja de tipo
1:21:092 ponderado por el número de hojas de
1:21:13tipo dos
1:21:15que hay en ese nivel.
1:21:20Por otro lado, cuando yo gano una hoja
1:21:22de tipo dos, yo gano una hoja de tipo
1:21:26dos cuando se produce esta transición de
1:21:29hoja de tipo uno a tipo dos y queda en
1:21:32el mismo nivel, ¿no es cierto? Entonces
1:21:34yo gano una hoja de tipo dos cuando se
1:21:37produce una inización en una hoja de
1:21:39tipo uno que estaba en el mismo nivel.
1:21:43Entonces yo gano una hoja de tipo
1:21:49dos cuando cae una inserción en una hoja
1:21:52de tipo 1. Eso ocurre con probabilidad 2
1:21:55parido por n + 1
1:21:58eh ponderado por el número de hojas de
1:22:00tipo uno que hay en el mismo nivel.
1:22:04Ya. Ahora esto, ojo, esto me recuerda
1:22:08que yo cometí un error recién que fue
1:22:10aquí. Yo dije, hay que escribirlo con
1:22:12cuidado y al final no lo escribí con
1:22:14tanto cuidado. Aquí hay un error.
1:22:18¿Dónde está el error? Es correcto que yo
1:22:19gano dos hojas. Es correcto que 3 parid
1:22:22por n + 1 es la probabilidad de caer en
1:22:24una hoja de tipo dos. Pero esa hoja de
1:22:27tipo dos hay que ponderar por el número
1:22:28de hojas de tipo dos, pero las hojas de
1:22:30tipo dos que están un nivel más arriba,
1:22:34K - 1,
1:22:37¿cierto?
1:22:40Esa hoja de tipo dos tiene queado en el
1:22:42nivel k - 1 para que esta hoja de tipo 1
1:22:45aparezca en el nivel k, ¿ya? Así que voy
1:22:48a aprovechar de ponerle un destacador
1:22:49aquí para que eh ponemos por aquí
1:22:55para que ustedes noten que esto es un
1:22:59detalle super importante.
1:23:05Eh, ya vamos.
1:23:10Uh, 4 minutos. Ya creo que este es un
1:23:13buen momento para terminar. Ah, tenemos
1:23:15planteado nuestro problema. Aquí está el
1:23:17problema. Eh,
1:23:25ya quizás alcanzamos a decir que
1:23:32a sub,
1:23:34perdón, a sub
1:23:38de tipo cero es un delta de cronaker,
1:23:43¿cierto? Al inicio lo único que hay es
1:23:46una hoja de tipo cer a nivel uno, cuando
1:23:50hay cuando n es igual a 0. ¿Ya? ¿Y qué
1:23:53pasa con las otras hojas?
1:23:55A sub n k de tipo 1 es igual a a sub n k
1:24:03perdón, estamos hablando del cer0.
1:24:07Ya, cuando n es ig a 0, las hojas de
1:24:11tipo uno y de tipo 2 que existen son cer
1:24:17hoja de tipo uno ni tipo dos, solo hay
1:24:19una hoja de tipo cero. Esa es la
1:24:21condición inicial. ¿Ya? Y ya. Pues
1:24:25bueno, es un buen momento para parar
1:24:27porque ahora ya tenemos planteadas
1:24:29nuestras ecuaciones. Ahora lo que
1:24:32necesitamos
1:24:33es poder resolver este problema.
1:24:39Okay. Muy bien. Con eso concluimos la
1:24:43clase de de hoy día.
1:24:49Muchas gracias, profe.