Fichas
Anaydis - Search
Fichas del conjunto (11)
- 1Caracteristicas del ArrayBasedBusqueda: O(log2 (N))
Insercion: O(N) - 2Que es la busqueda por interpolacion?La busqueda por interpolacion es un metodo de busqueda que mejora sobre la busqueda binaria. Ayuda a determinar mejor la posicion del elemento con una lista ordenada
- 3Codigo del put del array MapPrimero de todo crea un index que se fija si esta la key en la lista.(si ya esta cambia el valor del value) Si el index es = -1. Hago al index = -index - 1
Añado valores nulos a las keys y las values.
Luego hago un fori donde el i = size++; i > index ; i--
Y aca hago 2 sets tanto para la keys como los values. Con parametros i e key/values. get(i-1).
Fuera de este fori hago keys.set(index, key). Y retorno con un values.set index value - 4Codigo del find del arraymapPrimero si el low > high retorno -(low + 1).
Defino un middle
Hago una comparacion para ver si mi key esta a la derecha izquierda o si es el middle.
Si es == 0 retorno middle
Si es < 0 return find(key , low , middle-1)
Si > 0 return find(middle+1 , high) - 5Codigo del remove del arraymapPrimero veo el index del key. Si esta en la lista. Hago un fori desde el index+1 hasta el final
en el que hago set tanto para keys como para values. Con parametros (i-1 , keys/valuest.get(i)) - 6Codigo del put del RandomizedTreeMapPrimero hago un Math.Random
y veo que me toca hacer. Igualo el head tanto al rootput o al put.
Hay 2 Puts ~put ~rootPut
el put ve si esta el nodo vacio si lo esta hago size++ y return un nuevo nodo.
Sino hago una comparacion entre la key que queres meter y el nodo en el que estamos acutalemnte.
Si el cmp dio
< 0 node.Left = put(node.Left,key,value)
> 0 node.Right=put(node.Right,key,value)
==0 node.value = value
Y return node.
El rootPut hago lo mismo que el put pero cambia lo que hago segun el cmp.
Si cmp dio
< 0 node.Left=rootput(node.getLeft) y retorno RotateRight(node)
>0 node.Right=rootput(node.getRight) y return RotateLeft(node)
==0 node.value = value
return node - 7Codigo del RotateLeft y RotateRight en RandomizedTreeMapRotateLeft
defino un result = node.getRight
node.Right = result.getLeft
result.Left = node
return result
RotateRight
defino un result = node.getLeft
node.Left = result.getRight
result.Right = node
return resutl - 8Codigo del find del RandomizedTreeMapVeo si el node es distinto de null
Defino un cmp entre la key el node.getKey
Si el cmp dio
== 0 return node
< 0 return find(node.Left , key)
> 0 return find(node.Right , key) - 9Diferencia entre la key del RwayTrie y el randomizedTreeMapEl Rwaytrie tiene un String como llave
- 10Como es el put del RWayTrieHay 2 puts
Primero 1 que suma 1 size y defino head = put()
El put de verdad hace lo siguiente
Me fijo si mi nodo esta vacio si esta vacio hago node = new Nodetrie.
Si el level es igual al key.length
Hago node.value = value y return node
fuera de este if
Defino un char c = key.charAt(level)
node.next[c] = put(node.next[c],key,value, level+1)
return node - 11Como es el find del RWayTrieVeo si el node == null
Veo si el (level ==key.length) return node
defino un char c = key.charAt(level)
y retorno(node.next[c] , key , level+1 )
Información
- Descripción
- Quinto Grado Anaydis parcial 1 Fichas sobre Anaydis - Search, creado por Pokcron g el 22/11/2021.
- Creado por
- Pokcron g
- Visitas
- 13
- Valoración