Estructura de Datos.md

Estructura de Datos

Tipo de Dato Abstracto (ADT)

• Es como se va organizar la informacion
• Ejemplo: una lista, un arbol....

Estructura de Dato (DS)

• Como implementar un determinado ADT.
• Con nodos conectados, o con un arreglo.

Ejemplos de ADT

Cola (QUEUE)

• Un conjunto de datos donde uno precede a otro.
• El primero que entra sale (FIFO)
  • First in First Out
• metodos: enqueue(push) y dequeue(shift)
• Representaciones en Estrucutra de datos:
  • Arrays
  • Lista Anidada

Pila (STACK)

• Last in First Out (LIFO)
  • Ponemos uno arriba del otro y siempre sacamos el de arriba
• metodos: push y un pop.
• Representacion en Estructura de datos:
  • Arrays
  • linked lists

Arbol (TREE)

• Puede ser un ADT o un DS (como esta construido, y com o se usa).
• Representar un arbol en arreglo
  • [5, 2, 6, 1, 3, undefined, 8 ]
• operaciones:
  • insert (logn)
  • search (logn)
  • traversal
    • depth first (profundidad primero):
      • in-order: izquierda, raiz, derecha
      • pre-order: raiz, izquierda derecha
      • post-order: izquierda, derecha , raiz
    • breadth-first
• Distintas ADT:
  • binary tree
    • solo tenemos uno a la izquierda, y otro derecha.
  • heap:
    • Arriba del arbol esta el mayor o el menor
    • Sirve cuando queremos tener acceso rapido al menor o al mayor
  • tries:
    • ir guardando las letras como nodos para guardar palabras
  • Árboles "degenrados"
    • no estan bien balanceados
    • puede terminar siendo una lista
    • O(n) en vez de O(logn)

Map/Dictionary/Object

• operaciones:
  • insert O(1)
  • acces O(1)
• representacion: Hash Table
• Javascript new Map()

SET

• tipo de lista
• los valores en la lista tienen que ser unicos
• new Set()
• agregar y acceder son constantes

GRAPH

• Nodos conectados
• Nodos son llamados vertices
• directos o indirectos:
  • directos es por default hacia una direccions (podemos especificar dos)
  • indirectos es direccion doble.
• Social Network
  • Facebook: Amigos (indirecto)
  • Linkedn: grados de separacion entre personas
  • Twitter: Followers(directo)

Ejemplos DS

Arrays

• Arreglo de tamaño fijo
• Mismo tipo de datos
• No es igual al Array(JS)

Linked List

• Nodos conectados uno atras del otro
• cada nodo un next
• puede ser conexión doble(previous) o simple
• Trakear la head (opcionalmente tail)

Hash Table

• Tipicamente arreglo de "buckets"
• cada bucket tiene adentro una linked-list
• Ingreso un key, pasa por una función hasheadora y lo guardo en el bucket de su output
• Normalmente O(1) pero por colisiones puede terminar siendo O(n) en el peor caso.