TEMA 1: INTRODUCCION (NO ENTRA EN
EXAMEN)
//NO TODOS LOS LENGUAJES INICIALIZAN LOS VALORES, JAVA LO HACE POR
DEFECTO
//OJO CON LOS == DE OBJETOS
1. UML
+ -> Se usa para indicar que es pblico (CONSTANTES)
- -> Se usa para indicar que es privado. No tiene get ni set (ATRIBUTOS)
# -> Se usa para indicar que es protegido
NOMBRE de la Clase
- Nombre Atributos
+ Constantes
+ Metodo(valor:int, index:bool): Boolean
- Metodo2()
2. NORMAS DE ESTILO
Clases la 1 letra con mayusculas
Atributos y mtodos la 1 letra miniscula
Mtodos compuestos separados por _ y con Mayuscula la 1 de la 2 palabra
Constantes TODO en maysculas
Comentar con JavaDoc
3. PILAS
Mtodos siempre con complejidad O(1) y NUNCA varia aunque haya diferente
implementacin
Mtodos
o Size(), is_Empty(), top(), push(valor), pop()
Implementacin
o Arrays
Posicin la indicas con un tope que esta indicando a la 1
posicin vacia
Errores en la diapositiva
Pop()-> 9 deberia estar fuera
Errores en el cdigo
Top()-> return s[top-1]
Push()-> falta else para println()
o Lista enlazada
Trabaja con punteros
// BUSCAR LA IMAGEN DE LA PILA (no la veo en la diapositiva)
???-> se traduce en -top:int size:int s: float[]
La clase FloatNode tiene los atributos privados pero con get y set por lo tanto
es como si fueran pblicos. NO ES UNA BUENA IMPLEMENTACION
//ES MUCHO MAS EFICIENTE LINKEDLIST QUE ARRAY LIST SI HAY QUE ESTAR
BORRANDO E INSERTANDO
4. COLAS
Toda implementacin tiene que tener O(1) para eso lo que debe de hacer es
tener una referencia a cabecera y final (tanto para esttico como dinmico)
5. LISTAS
Estructura de datos mas compleja con infinitas operaciones.
FloatArrayList
o Elementos necesarios: size, lastelement, array
TEMA 2 ARBOLES
//RECUERDA POSITION<E> solo tiene getValue()
Metodos bsicos
Size
isEmpty
Iterator -> para recorrer
Metodos de acceso
Position <E> root
Position <E> parent (Position <E>)
Position<E> children(Position <E>)
Metodos de consulta
isLeaf(Position<E>)
isInternal
isRoot
Metodos de actualizacin
replace (position <E>)
Recorrido de arboles -> NO SE PUEDE RECORRER EN INORDEN
PARA RECORRER EN ANCHURA HACE FALTA UNA COLA
RECORRIDO EN PROFUNDIDAD ES EL MISMO CODIGO QUE LA COLA PERO CON UNA PILA.
TEMA 2B- Arboles Binarios
TEMA 3- TABLAS HASH
Funcin hash crea un cdigo hash, que es un numero entero y lo proyecta respecto al tamao
de la tabla (modulo tamao tabla).
El cdigo hash es nico pero el cdigo dispersado si se puede crear repetido provocando
colisiones, que tienen que ser el minimo.
DIAPOSITIVA 20 ENTRA EN EXAMEN -> Ejercicio siguiente
Inserta en una tabla hash de 13 elementos quiero insertar las entradas <18,A> <41,Y> <22,C>
<44,D> <59,E>
1. Elegir funcin hash h(x) = x mod 13
2. <18,A> h(18) = 18 mod 13 = 5 -> se inserta en la posicin 5
0 1 2 3 4 5 6 7 8 9 10 11 12
<13,A>
3. Coges el siguiente valor <41,Y> =2
0 1 2 3 4 5 6 7 8 9 10 11 12
<41,Y> <13,A>
4. Coges el siguiente <44,D> = 5
0 1 2 3 4 5 6 7 8 9 10 11 12
<41,Y> <13,A> <44,D>
Como es una lista no hay problema la lista tiene 2 atributos uno dupla, punturo a siguiente y
primero estar 13,A en el segundo elemento estar 44,D
El 75% para direccionamieto con listas (encabezamiento abierto) y el 50% en direccionamiento
abierto para mantener el rendimiento optimo. El % es de elementos no de posiciones.
Clustering secundario: series largas de posiciones ocupadas incrementan el tiempo medio de
bsqueda
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
algo algo Algo algo
H(k,i) = h(k) + c1*i + c2*i2 siendo c1 = 0 y c2 = 1 k = x y h(k) = 3
Para i = 0 -> h(k,i) = 3 + 0 = 3
Para i = 1 -> 3 +1^1 = 4
Para i = 2 -> 3 + 2^2 = 7
Para I = 3 -> 3 + 3^2=12
Para I = 4 -> 3 + 4^2 = 19 -> 3
NO SE PUEDE AADIR EL NUMERO CLUSTERING SECUNDARIO
5. AVL
6. Diccionarios ordenados
//Ejercicio de borra todos los elementos que tienen una misma clave
7. Arboles binario bsqeda
Ejercicios
8. Arboles rojo-negro
La altura se mide en funcin de los nodos que sean negros.
Los punteros a null cuentan como negros.
La raz es nodo negro
Los hijos de un nodo rojo son negros
Todas las hojas tienen la misma profundidad negra
Nunca hay 2 rojos seguidos
Al insertar un nodo, salvo la raz (negro) son ROJOS, eso es lo que provoca desequilibrios, 2
rojos seguidos y se llama desequilibrio doblerojo.
DOBLE ROJO
Los nodos involucrados son el insertado, el padre, el abuelo, los hermanos y los tios.
1. Hay que mirar al tio
a. Es rojo
2. pintar padre y tio de negro y el abuelo de rojo, SALVO LA RAIZ QUE SIEMPRE
ES NEGRA
b. Es negro
2. Reestructuracin trinodo: es decir como si fuera un avl, OJO que al rotar
solo modificas los valores, el color de los nodos es b negro y a y c de rojo.
//ESCANEAR EJERCICIO DE ARBOLES ROJO NEGRO
BORRADOS EN UN ARN
Se hace igual que los ABB lo que pasa es que tambin pueden producirse problemas.
Si borro un nodo rojo no pasa nada
Si borro un nodo negro con un nico hijo rojo, el valor de ese nodo rojo pasa a ser el
valor del nodo negro
Si borro un nodo negro con 2 hijos. Hay que asignar un doble negro. 3 situaciones Para
saber el caso mirar a los sobrinos.
o Caso 1: el hermano del doble negro, si es negro y tiene un hijo rojo
Aplicar reestructuracin trinodo (sobrino,hermano y abuelo)
A y c de negro
B el color del abuelo
El del doble negro es simple negro
o Caso 2: el hermano es negro y sus 2 hijos son negros
Recoloreado de r como negro e y como rojjo
Si X es rojo se ilumina de rojo
o Caso 3: el hermano es rojo
Si y es el h_der de x, z es el h_der de y
Si y es el h_izq de x, z es el h_izq de y
Colorear y de negro y x de rojo
//ESCANEAR HOJA 1 DEL CUADERNILLO -> mirar tambin la web de las diapositivas
