Principios de Seguridad Informática

La seguridad informática​ es el área relacionada con la informática y la telemática que se enfoca en la protección de la infraestructura computacional y todo lo relacionado con esta y, especialmente, la información contenida en una computadora o circulante a través de las redes de computadoras.
Para ello existen una serie de estándares, protocolos, métodos, reglas, herramientas y leyes concebidas para minimizar los posibles riesgos a la infraestructura o a la información.
La ciberseguridad comprende software (bases de datos, metadatos, archivos), hardware, redes de computadoras y todo lo que la organización valore y signifique un riesgo si esta información confidencial llega a manos de otras personas, convirtiéndose, por ejemplo, en información privilegiada.
El objetivo de la seguridad informática es mantener la Integridad, Disponibilidad, Privacidad,
Control y Autenticidad de la información manejada por computadora.

Elementos

Autenticidad

Definir que la información requerida es válida y utilizable en tiempo, forma y distribución. Se debe estar seguro de las identidad del Receptor y Transmisor
Los factores de autenticación responde a la consigna de "algo que ..."
Se – Tengo – Soy
 Autenticacion Fuerte : utiliza dos factores

Integridad

Los componentes del sistema permanecen inalterados a menos que sean modificados por los usuarios autorizados.
Asegurar que el mensaje no fue modificado no solo en su trayecto, sino que también en su origen. Una opción es el uso del CRC, en donde se le agrega información al mensaje para saber si hubo alguna modificación en el mismo.
Se debe autenticar el mensaje por medio de algoritmos

Confidencialidad

Los componentes del sistema y datos transmitidos son accesibles deben ser vistos o interpretados solo por los destinatarios y usuarios autorizados.
Para esto existen algoritmos de cifrado, tales como el DES (Claves Simétricas) el cual necesita una clave privada, ya que el algoritmo es publico.
PKI – Claves Asimétricas.
RSA.

Data Encription Standard.

Disponibilidad

Los usuarios deben tener disponibles todos los componentes del sistema cuando así lo deseen.

Para ello:
Back Up
Planes de Contingengia (Disaster & Recovery)

No Rechazo

Evita que cualquier entidad que envió o recibió información alegue, que no lo hizo o sea  desconozcan en mensaje transmitido

Para poder demostrar el origen como también la recepción de un mensaje se recurre a:

• Certificados Digitales
• Autoridad Certificacion

Control de Acceso

Solo los usuarios autorizados deciden cuando y como permitir el acceso a la
información.

Auditoria

Determinar qué, cuándo, cómo y quién realiza acciones sobre el sistema.

Amenazas

Fraudes cometidos mediante manipulación de computadoras

Manipulación de datos de E/S

Daños a programas o datos almacenados

Distribución de virus

Espionaje

Acceso no autorizado

Distintos Tipos

Pasiva: simple observacion o monitoreo

Activa: accion directa con alteraciones

• Interrupcion
• Intercepcion 
• Modificacion
• Sustitucion y/o Reemplazo

Algoritmos y Protocolos

Encripcion o Cifrado

DES – Claves Simétricas

PKI – Claves Asimétricas

RSA

Autenticacion y Certificacion

Factores de Autenticacion

Autoridad Certificacion

Certificados Digitales

Protocolos

SET – Transaccion Segura Electronica

SSL – Secure socket layer

HTTPS

Comunicacion

Comunicación Segura

Servidor con SSL – Certificado Digital

Hand Shake: autenticacion Cliente-Servidor, informa algoritmos de cifrado y claves del MSJ.

Cliente Hello: envia algoritmos y nro aleatorio

Servidor Hello: presenta Cert. Digital con clave Publica y el algoritmo selecionado mas fuerte

Aprob. Cliente: verifica Cert. Digital, genera la Key Session, la envia al server encriptada con la Clave Publica.

Verificacion: ambos conocen la Key Session utilizada para encriptar los datos y comienza la transferencia de informacion.

Seguridad en redes.

Elementos de criptografía.

La criptografía asimétrica es el método criptográfico que usa un par de claves para el envío de mensajes. Las dos claves pertenecen a la misma persona que ha enviado el mensaje. Una clave es pública y se puede entregar a cualquier persona, la otra clave es privada y el propietario debe guardarla de modo que nadie tenga acceso a ella. Además, los métodos criptográficos garantizan que esa pareja de claves sólo se puede generar una vez, de modo que se puede asumir que no es posible que dos personas hayan obtenido casualmente la misma pareja de claves.
Si el remitente usa la clave pública del destinatario para cifrar el mensaje, una vez cifrado, sólo la clave privada del destinatario podrá descifrar este mensaje, ya que es el único que la conoce. Por tanto se logra laconfidencialidad del envío del mensaje, nadie salvo el destinatario puede descifrarlo.

La criptografía simétrica es un método criptográfico en el cual se usa una misma clave para cifrar y descifrar mensajes. Las dos partes que se comunican han de ponerse de acuerdo de antemano sobre la clave a usar. Una vez que ambas partes tienen acceso a esta clave, el remitente cifra un mensaje usando la clave, lo envía al destinatario, y éste lo descifra con la misma clave.

Firma electrónica y firma digital.

FIRMA DIGITAL:

Una firma digital es un mecanismo criptográfico que permite al receptor de un mensaje firmado digitalmente determinar la entidad originadora de dicho mensaje (autenticación de origen y no repudio), y confirmar que el mensaje no ha sido alterado desde que fue firmado por el originador (integridad)
La firma digital se aplica en aquellas áreas donde es importante poder verificar la autenticidad y la integridad de ciertos datos
Debe ser por PKI, se firma con una clave privada y se debe hacer online

FIRMA ELECTRONICA:

Es un concepto jurídico, equivalente electrónico al de la firma manuscrita, donde una persona acepta el contenido de un mensaje electrónico a través de cualquier medio electrónico válido.
Usos:
- Firma con un lápiz electrónico al usar una tarjeta de crédito o débito en una tienda.
- Usando usuario y contraseña.
- Usando una tarjeta de coordenadas.
Se trabaja en forma offline, primero debe pasar por un algoritmo de encripcion.

IP v6

Durante la primera década de operación de Internet basado en TCP/IP, a fines de los 80, se hizo evidente que se necesitaba desarrollar métodos para conservar el espacio de direcciones. A principios de los 90, incluso después de la introducción del re-diseño de redes sin clase, se hizo claro que no sería suficiente para prevenir el agotamiento de las direcciones IPv4 y que se necesitaban cambios adicionales. A comienzos de 1992, circulaban varias propuestas de sistemas y a finales de 1992, la IETF anunció una convocatoria para white papers (RFC 1550) y la creación de los grupos de trabajo de "IP de próxima generación" ("IP Next Generation") o (IPng).

IPng fue propuesto por el Internet Engineering Task Force (IETF) el 25 de julio de 1994, con la formación de varios grupos de trabajo IPng. Hasta 1996, se publicaron varios RFC definiendo IPv6, empezando con el RFC 2460.

La discusión técnica, el desarrollo e introducción de IPv6 no estuvo exenta de controversia. El diseño fue duramente criticado por la falta de interoperabilidad con IPv4 y otros aspectos por el ingeniero D. J. Bernstein, entre otros.

Incidentalmente, IPng (IP Next Generation) no pudo usar la versión número 5 (IPv5) como sucesor de IPv4, ya que ésta había sido asignada a un protocolo experimental orientado al flujo de streaming que intentaba soportar voz, video y audio.

Se espera ampliamente que IPv6 sea soportado en conjunto con IPv4 en el futuro cercano. Los nodos solo-IPv4 no son capaces de comunicarse directamente con los nodos IPv6, y necesitarán ayuda de un intermediario. 

Restricciones de actual IPv4

• Rango de direcciones IP insuficiente
• Limitaciones por el campo de Direccion:
• Estructura de 2: Red – Host
• Proliferación de redes
• Uso creciente TCP/IP
• Asignacion de direccion UNICA por dispositivo
• Tablas de enrutamiento de gran tamaño
•  Protocolo complicado con un procesamiento  lento en los enrutadores
• No posee funcionalidad para asegurar seguridad.
• Necesidad de Nuevos Tipos de Servicios.
• Complicado para trabajar con IP Móvil.

IP v6

• Aumenta el rango de direcciones IP.
• Simplifica el formato de la cabecera.
• Mejor soporte para Extensiones y Opciones.
• Etiquetas para distinguir flujos.
• Introducen opciones para seguridad 
• Espacio de Direcciones Ampliado: 128 bits
• Asignacion dinámica de direcciones
• Facilidad de asignación de recursos:
• Reemplaza tipo de servicio
• Habilita etiquetado de paquetes
• Permite tratamiento en tiempo real

Cabecera IP v6

• Solo 8 campos vs 12 en IPv4.
• Eliminan campos como Fragmentación, TTL, etc.
• Tamaño es de 40 bytes fijos

Cabeceras de Extension IP v6

• Cabecera de Opciones “salto a salto”
• Cabecera de Información de encaminado.
• Cabecera de Fragmentación.
• Cabecera de Autenticación.
• Cabecera de Encapsulado de carga.
• Cabecera de Opciones de destino (para el destino).
• Cabecera de Encriptación.

Todas las cabeceras son analizadas en el extremo receptor, exceptuando Opciones “salto a salto”, que posee información que se utiliza en cada salto y por la utilizan por los enrutadores. 

Direcciones IP v6

Unidistribucion  (Unicast)

Paquete Unicast se entrega a una sola interfaz, similar a IPv4 actual.

Monodistribucion (Anycast)

Paquete Aniycast se entrega a una de las interfaces indicadas, la mas cercana. Se puede asi crear ambitos de redundancia, varias maquinas generan el mismo trafico

 Multidristribucion (Multicast)

Paquete Multicast  se entrega a todas las interfaces indicadas, la mas cercana. Se generan aplicaciones de broadcasting

Direcciones Especiales IP v6

Dirección de auto-retorno o Loopback 

(todos ceros y 1 uno). Interfaz “virtual”, pues son paquetes que no salen de la máquina que los emite; permite loop  para verificar la correcta inicialización del protocolo (dentro de una determinada máquina). física.

Dirección no especificada (Todos cero) 

No se asigna a ningún nodo, se emplea para indicar la ausencia de dirección ::<dirección IPv4>. 

Direcciones IPv6 compatibles con IPv4 y permiten la retransmisión de tráfico IPv6 sobre infraestructuras IPv4 de forma transparente ::FFFF:<dirección IPv4>) 

Representación automática de direcciones IPv4 sobre IPv6 

Permite que los nodos que sólo soportan IPv4, puedan seguir trabajando en redes IPv6. Se denominan “direcciones IPv6 mapeadas desde IPv4

Comparación IPv4 - IP v6

IP v4 vs IP v6

Ipv4: Direcciones de 4 bytes
Ipv6: Direcciones de 16 bytes

Ipv4: Ipsec es opcional
Ipv6: Ipsec es nativo del protocolo

Ipv4: No hay indicador de Flujo para garantizar QoS
Ipv6: Incluido en la cabecera IPv6 y examinado en los enrutadores

Ipv4: La fragmentación se realiza en los enrutadores y en el extremo emisor
Ipv6: La fragmentación se realiza extremo-extremo

Ipv4: El encabezado incluye Checksum
Ipv6: El encabezado no incluye Checksum

Ipv4: La cabecera incluye opciones Ipv6: Las opciones se incluyen en cabeceras separadas Ipv4: Configuración de direcciones manual o usando DHCP Ipv6: Configuración automática. No requiere DHCP o configuración manual

Transición a IP v6

Sistemas Dobles o Especiales

Ejecutan los dos protocolos, IPv4 e IPv6.

Ventajas:

Pueden convivir ambos protocolos 

Evita problemas con los mecanismos de traducción.

Desventajas:

Gestión de dos redes paralelas.

Dificultad en el desarrollo de las aplicaciones.

Túneles IPv6 sobre IPv4:

Conectan redes IPv6 a IPv4 y viceversa.

Ventajas:

Administración mas sencilla.

Existe experiencia en administración de IPv4

Sistemas y aplicaciones mas simples.

Desventajas:

Complejidad en el enrutamiento.

Mecanismos de Traducción

Permite la comunicación entre IPv6 e IPv4.

Cola

Una fila o cola es una colección ordenada de elementos homogéneos en la que “hay” restricciones de acceso, los elementos ingresan por un extremo denominado fondo de la cola y salen por otro denominado frente.

La Cola tiene un comportamiento FIFO (First In First Out). Así el primer elemento que se incorpora a la estructura es el primero a ser eliminado.

Una Cola es aplicable cuando se desea tratar los elementos en el mismo orden estricto en el que entraron.

Cola Estática Circular:
Es una estructura de comportamiento FIFO y en una aplicación estática circular se utiliza un array con la particularidad que su crecimiento y decrecimiento se realiza en el mismo sentido reutilizando de ser posible los elementos a partir del primero si se llegó al último del array, trabajando entonces en forma circular.
Puede guardar como máximo 1 elemento menos del máximo que tiene definido el array.

Condiciones: Vacía: frente=fondo
Llena: próximo de fondo=frente

Para poder diferenciar Vacía de Llena optamos por inutilizar un elemento del array

Especificación TAD

Cola 
  usa Booleanos, Posiciones, Elementos
  tipos cola

operaciones
  colaVacia: -> cola
  CrearCola() -> colaVacia
  Empty(cola) -> bool
  Peek(cola) -> elem
  Insert(cola,elem) -> cola
  Remove(cola) -> cola

ecuaciones [Dados C:Cola; e,f,g:elem]
  Empty(colaVacia) = Verdadero ; 
  Empty(CrearCola()) = Verdadero
  Empty(Insert(C,e)) = Falso
  Peek(colaVacia) => error ;  
  Remove(colaVacia) => error   
  Remove(Insert(colaVacia,e)) = colaVacia
  Remove(Insert(Insert(colaVacia,f),g)) = Insert(Remove(Insert(colaVacia,f)),g)

FinEspecificación

Pilas

Una pila o stack es una colección ordenada de elementos homogéneos en la que “hay” restricciones de acceso, los elementos solo pueden ser ingresados o retirados por un solo extremo, denominado top de la pila.

La Pila tiene un comportamiento LIFO (Last In First Out). Así el último elemento que se incorpora a la estructura, es el único que se puede consultar y es el primero a ser eliminado.

Una Pila es aplicable cuando se desea tratar a los elementos en el orden estrictamente inverso al que entraron.

Ej: utilizar ctrl Z

Pila dinámica: Tiene restricciones de ingreso y egreso de elementos pudiéndolo hacer solamente por un extremo que indica el puntero Top. Al ser dinámica se implementa sobre una lista de nodos, no tiene límite teórico de crecimiento y no hay necesidad de control que llego al máximo de capacidad.

Pila estática: Es una estructura de comportamiento LIFO y al ser estática se implementa sobre un array con la particularidad que se maneja la posición con un puntero Top. Crece y decrece por medio de este puntero indicando el último ingresado y siendo el punto de extracción del primero. Cant. max elementos del array.

Especificacion TAD
Pila
  usa Booleanos, Elementos
  tipos pila

operaciones
  pilaVacia: -> pila;
  CrearPila() -> pilaVacia
  Push(pila,elem) -> pila
  Pop(pila) -> pila
  Empty(pila) -> bool
  Peek(pila) -> elem

ecuaciones [Dados S:Pila; e:elem]
  Empty(pilaVacia) = Verdadero;
  Empty(CrearPila()) = Verdadero;
  Empty(Push(S,e)) = Falso
  Peek(pilaVacia) => error ;
  Peek(Push(S,e)) = e
  Pop(pilaVacia) => error ;
  Pop(Push(S,e)) = S

FinEspecificacion

Cuerpo de una pila

Sobre un vector

MaxPila = n //(Máximo valor del array, máximo posible de la pila)
Stack {
  cuerpo = array[1..MaxPila] de elem
  top = [0..MaxPila]
}

Sobre una Lista de nodos

Stack {
  cuerpo = lista (colección de nodos)
  top = puntNodo
}

CrearPila (crea una pila vacía)

Sobre un vector

CrearPila (): pila {
  S->Top = 0
  return S
}

Sobre una Lista de nodos

CrearPila (): pila {
  S->Top = CrearLista()
  return S
}

Peek (lee el tope de la pila)

Sobre un vector

Peek (S:pila) {
  if (Empty(s))
    "error"
  else
    reutrn S->cuerpo[S->top]
  end-if
}

Sobre una Lista de nodos

Peek (S:pila) {
  if (Empty(s))
    "error"
  else
    reutrn Contenido(S->top)
  end-if
}

Push (inserta elemento en pila)

Sobre un vector

Push (S:pila, e:elemento) {
  if (Full(S))
    "error"
  else
    S->top = S->top+1
    S->cuerpo[S->top] = e
  end-if
}

Sobre una Lista de nodos

Push (S:pila, e:elemento) {
  if (Empty(S))
    S->Top = PrimerElemLista(S->Top,e)
  else
    InsAntes(S->top,e)
    S->top = Anterior(S->top) 
  end-if
}

Pop (remueve elemento de la pila)

Sobre un vector

Pop (S:pila):elementos {
  if (Empty(S))
    "error"
  else
    x = S->cuerpo[S->top]
    S->top = S->top-1
    return x
  end-if
}

Sobre una Lista de nodos

Pop (S:pila):elementos {
  if (Empty(S))
    "error"
  else
    p = Siguiente(S->top)
    X = Borrar(S->top)
    S->top = p
    return x
  end-if
}

Empty (devuelve si la pila se encuentra vacía (True o False)

Sobre un vector

Empty (S:pila):boolean {
  if (Siguiente(S->top) == null)
    return true
  else
    return false
  end-if
}

Sobre una Lista de nodos

Empty (S:pila):boolean {
  if (EsListaVacia[S->top])
    return true
  else
    return false
  end-if
}

Full (devuelve si la pila se encuentra llena  (True o False)

Full (S:pila):boolean {
  if (S->top == MaxPila)
    return true
  else
    return false
  end-if
}

Listas

La lista enlazada es un TDA que nos permite almacenar datos de una forma organizada, al igual que los vectores pero, a diferencia de estos, esta estructura es dinámica, por lo que no tenemos que saber "a priori" los elementos que puede contener.

Los elementos de una lista, suelen recibir también el nombre de nodos de la lista.

Es un conjunto ordenado de elementos homogéneos en la que no hay restricciones de acceso, cualquier elemento es igualmente accesible en un momento dado. 

La introducción y eliminación de elementos puede realizarse en cualquier posición de la misma. 

Se clasifica a la Lista dentro de los contenedores como una secuencia. Cada elemento de una estructura secuencial tan sólo tiene relación con un anterior y un siguiente. 

Las listas por su encadenamiento pueden ser simplemente encadenadas (navegación en una sola dirección) o doblemente encadenadas (navegación en ambas direcciones). 

Además cada uno de estos tipos puede estar implementado en forma lineal o circular. Siendo la primera sin encadenamiento del último con el primero y la segunda con un encadenamiento del último con el primero, dándole la característica de navegación continuada. 

Listas Simples: 

struct lista {
    gint dato;
    lista *siguiente;
};

Lineales: Cada nodo, contiene un único apuntador hacia el siguiente nodo, por lo cual hace de él una estructura muy eficiente, ya que el último de la lista apunta hacia null, por ello, es fácil hacer recorridos directos.

Circulares: Este tipo de lista, es sólo una extensión de las listas simplemente enlazada, con la diferencia que el último elemento se enlaza al primer elemento de la lista, lo cual permite el recorrido en forma de anillo 

Listas Dobles:

struct lista {
    gint dato;
    lista *anterior;
    lista *siguiente;
};

Lineales: Esta lista se caracteriza por que sus nodos contienen dos punteros, uno hacia el nodo siguiente y otro hacia el nodo anterior. 

Circulares: Quizá este tipo de lista, sea la más compleja, ya que es la combinación de la lista circular y las doblemente enlazadas, ya que es una lista doblemente enlazada donde el primer elemento se conecta con el último y viceversa.

Árboles AVL

Un árbol AVL es un árbol binario de búsqueda que cumple con la condición de que la diferencia entre las alturas de los subárboles de cada uno de sus nodos es, como mucho 1.

La denominación de árbol AVL viene dada por los creadores de tal estructura (Adelson-Velskii y Landis).

Recordamos que un árbol binario de búsqueda es un árbol binario en el cual cada nodo cumple con que todos los nodos de su subárbol izquierdo son menores que la raíz y todos los nodos del subárbol derecho son mayores que la raíz. El tiempo de las operaciones sobre un árbol binario de búsqueda es de "O(log n)" promedio, pero el peor caso es O(n), donde n es el número de elementos.

La propiedad de equilibrio que debe cumplir un árbol para ser AVL asegura que la profundidad del árbol sea O(log(n)), por lo que las operaciones sobre estas estructuras no deberán recorrer mucho para hallar el elemento deseado. Como se verá, el tiempo de ejecución de las operaciónes sobre estos árboles es, a lo sumo O(log(n)) en el peor caso, donde n es la cantidad de elementos del árbol.

Sin embargo, y como era de esperarse, esta misma propiedad de equilibrio de los árboles AVL implica una dificultad a la hora de insertar o eliminar elementos: estas operaciones pueden no conservar dicha propiedad.

Características básicas

• La propiedad de balanceo garantiza que la altura del árbol sea de O(log n).
• En cada nodo del árbol se guarda información de la altura.
• La altura del árbol vacío es -1. 
• Al realizar operaciones de inserción o eliminación se debe actualizar la información de altura de los nodos y recuperar la propiedad de balanceo si fuera necesario, es decir, si hubiera sido destruida.

Cambios en altura

En inserción (dH > 0), si un hijo (y) incrementa su altura, el padre (x) también la incrementa si su factor de equilibrio era -1 o 0 (hijo izquierdo) o bien 0 o +1 (hijo derecho)

En borrado (dH < 0), si un hijo (y) decrementa su altura, el padre (x) también la decrementa si su factor de equilibrio era -1 (hijo izquierdo) o +1 (hijo derecho)

Rotaciones

Tras una operación de inserción o borrado, se recorren los ascendientes, recalculando sus factores de equilibrio y teniendo en cuenta el cambio en altura del subárbol.

Es posible que en el recorrido el factor de equilibrio de algún nodo pasa a valer +2 ó -2 (desequilibrado).

En ese caso se aplica una determinada rotación que restablece el equilibrio del nodo (aunque es posible que cambie la altura del nodo).

En un árbol AVL se necesitan 2 tipos de rotaciones (simples y dobles), en un sentido u otro (izquierdas y derechas).

Teniendo en cuenta los distintos ajustes de factores de equilibrio y posibles resultados respecto al cambio de altura, existen seis casos a considerar.

Rotación 2|1 (Simple derecha).

Rotación 2|0 (Simple derecha).

Rotación 2|-1 (Doble derecha).

Rotación -2|-1 (Simple izquierda).

Rotación -2|0 (Simple izquierda).

Rotación -2|1 (Doble izquierda).

Arboles binarios

Un árbol es un conjunto de elementos finitos (pueden ser homogéneos o heterogéneos) denominados nodos y un conjunto finitos de líneas que enlazan los nodos que se denominan ramas, tiene un nodo inicial el cual no depende de ningún otro denominado raíz, el resto son hijos del primer nodo y los nodos hijos que no posean descendencia se denominan hojas.

Una estructura de datos de árbol se puede definir de forma recursiva (localmente) como una colección de nodos (a partir de un nodo raíz), donde cada nodo es una estructura de datos con un valor, junto con una lista de referencias a los nodos (los hijos) , con la condición de que ninguna referencia esté duplicada ni que ningún nodo apunte a la raíz.

Vocabulario y definiciones

• Nodo: Un nodo es una parte fundamental de un árbol. Puede tener un nombre, que llamamos la “clave”. Un nodo también puede tener información adicional. Llamamos a esta información adicional la “carga útil”. Aunque la información de carga útil no es central para muchos algoritmos de árboles, a menudo es crítica en aplicaciones que usan árboles.
• Arista: Una arista es otra parte fundamental de un árbol. Una arista conecta dos nodos para mostrar que hay una relación entre ellos. Cada nodo (excepto la raíz) está conectado por exactamente una arista entrante desde otro nodo. Cada nodo puede tener varias aristas salientes.
• Raíz: La raíz del árbol es el único nodo en el árbol que no tiene aristas entrantes. Suele ser el nodo de acceso al arbol.
• Ruta: Una ruta es una lista ordenada de nodos que están conectados por aristas. Por ejemplo, Mamíferos → Carnívoros → Félidos → Felis → Domestica, es una ruta.
• Hijos: El conjunto de c nodos que tienen aristas entrantes desde el mismo nodo se dice que son hijos de ese nodo.
• Padre: Un nodo es el padre de todos los nodos con los que se conecta mediante aristas salientes. 
• Hermanos: Se dice que los nodos del árbol que son hijos del mismo padre son hermanos. 
• Subárbol: Un subárbol es un conjunto de nodos y aristas compuesto por un padre y todos los descendientes de ese padre.
• Nodo hoja: Un nodo hoja es un nodo que no tiene hijos. También se puede decir que es aquel nodo cuyos hijos son NULL.
• Nivel: El nivel de un nodo n es el número de aristas en la ruta desde el nodo raíz hasta n. 
• Altura: La altura de un árbol es igual al máximo nivel de cualquier nodo en el árbol. 

Árboles equilibrados

• Las búsquedas son más eficientes cuando el árbol está equilibrado
• Un árbol equilibrado es aquel en el que las ramas izquierda y derecha de cada nodo tienen aproximadamente la misma altura (el árbol lleno sería el árbol equilibrado perfecto con todos los nodos con subárboles izq y dch de la misma altura)
• Si los nodos que se van insertando en el árbol aparecen en orden aleatorio el árbol tenderá a ser equilibrado

Árboles “degenerados”

• El caso peor ocurre cuando el árbol está “degenerado”, es decir, sigue siendo un árbol pero su estructura es equivalente a una lista enlazada (todos los nodos sólo tienen un hijo)
• Si los nodos del árbol que se van insertando en el árbol aparecen con un orden determinado el árbol tenderá a ser degenerado.

Árbol des-balanceado

* Los datos en la realidad suelen tener un cierto grado de orden por lo que para que los árboles BB sean eficientes es necesario hacer reequilibrados ⇒ árboles AVL

Definamos un árbol binario (AB)

struct Nodo
  int dato;
  struct Nodo *nodoIzq;
  struct Nodo *nodoDer;
end

Árbol Binario de Búsqueda(ABB)

Es aquel que dado un nodo, todos los datos del subárbol izquierdo son menores, mientras que todos los del subárbol derecho son mayores. 

Operaciones en árboles ABB

Insertar un nodo en el árbol 

• Se compara la clave a insertar con la raíz del árbol
• Si el árbol es NULO insertamos una hoja con la clave en esa posición
• Si clave < valor de la raíz la búsqueda continúa por el subárbol izquierdo
• Si clave > valor de la raíz la búsqueda continúa por el subárbol derecho
• Si clave = valor (claves repetidas) no se hace nada. Este funcionamiento podría ser distinto: reemplazar el antiguo con el nuevo, lanzar un error, permitir duplicados, etc.

InsertarABB(Arbol, valor)
  if (Arbol == null)
    ConstruirArbol(null, null, valor, Arbol)
  else
    if (valor < Arbol->dato)
      InsertarABB(Arbol->nodoIzq, valor)
    else if (valor > Arbol->dato)
      InsertarABB(Arbol->nodoDer, valor)
    else 
      return true
    endif
  endif
end

Buscar un nodo específico

• Se compara la clave a buscar con la raíz del árbol.
• Si el árbol es NULO la búsqueda acaba sin éxito.
• Si clave = valor de la raíz la búsqueda acaba con éxito.
• Si clave < valor de la raíz la búsqueda continúa por el subárbol izquierdo.
• Si clave > valor de la raíz la búsqueda continúa por el subárbol derecho.

BuscaABB (Arbol, valor)
  if (Arbol == null)
    return null
  else
    if (valor == Arbol->dato)
      return Arbol
    else if (valor < Arbol->dato)
      BuscaABB(Arbol->nodoIzq, valor)
    else 
      BuscaABB(Arbol->nodoDer, valor)
    endif
  endif
end

Borrado

• Se busca en el árbol la posición del nodo a eliminar 
• Si es un nodo hoja ⇒ se actualiza el puntero del padre a null y se borra el nodo 
• Si es un nodo con un solo hijo ⇒ se actualiza el puntero del padre para que apunte al hijo y se borra el nodo
• Si es un nodo con dos hijos
• Se intercambia el nodo con el mayor de su subárbol izquierdo (nodo anterior en el orden) o con el menor de su subarbol derecho (nodo posterior en el orden) y se borra el nodo.
• El mayor de su subárbol izquierdo se caracteriza por ser un nodo sin hijos o con un hijo a la derecha (si tuviera un hijo a la izquierda ya no sería el mayor). Por lo tanto es un nodo sencillo de borrar
• El menor de su subárbol derecho se caracteriza por ser un nodo sin hijos o con un hijo a la izquierda (si tuviera un hijo a la derecha ya no sería el menor). Por lo tanto es un nodo sencillo de borrar
• Al substituir un nodo por su anterior o su posterior la propiedad de árbol binario de búsqueda se sigue cumpliendo

EliminarABB(Arbol, valor)
  if (Arbol == null)
    return false     // Si Arbol es VACIO, el valor no existe y se devuelve false
  elseif (valor < Arbol->dato) // Si el valor es menor mandamos borrar en subárbol izq
    EliminarABB(Arbol->nodoIzq, valor)
  elseif (valor>Arbol->dato) // Si el valor es mayor mandamos borrar en subárbol dch
    EliminarABB(Arbol->nodoDer, valor)
  else // Si el valor es igual borramos el nodo
    aux == Arbol
    if (Arbol->nodoDer == null) // Si no tiene hijo dch lo sustituimos por el izq
      Arbol = Arbol->nodoIzq // (incluye el caso de los dos hijos vacios)
    elseif (Arbol->nodoIzq == null) // Si no tiene hijo izq lo sustituimos por el dch
      Arbol = Arbol->nodoDer // Si tiene dos hijos llamamos a reemplazar
    else 
      reemplazar (aux, Arbol->nodoIzq); // pasando el nodo a eliminar y su subarbol izq
    return true // Se devuelve true porque el valor existe
  endif
end 


reemplazar(Arbol, nodoDel)
  if (nodoDel->nodoDer <> null)
    reemplazar(nodoDel->nodoDer) // Bajamos por la rama derecha
  else 
    Arbol->dato == nodoDel->dato // reemplazamos los campos de información
Arbol == nodoDel // Marcamos el nodo sobre el que se hará un dispose
nodoDel == nodoDel->nodoIzq // y reenlazamos la estructura “saltando” al nodo que 
  endif                                 // se va a eliminar

end

Búsqueda binaria

La Búsqueda binaria divide el conjunto o subconjuntos ordenados en tres. Uno unitario para comparar, si es el buscado finaliza la búsqueda, de lo contrario continúa la búsqueda en el conjunto de los menores al compararlo si el buscado es menor o en el conjunto de los mayores si el buscado es mayor. Esto elimina gran cantidad de elementos a comparar.

El método se mejora cuanto más parejos sean los conjuntos de menores y mayores.

La búsqueda binaria es computada en el peor de los casos en un tiempo logarítmico, realizando "O(log n)" comparaciones, donde n es el número de elementos del arreglo y log es el logaritmo. La búsqueda binaria requiere solamente O(1) en espacio, es decir, que el espacio requerido por el algoritmo es el mismo para cualquier cantidad de elementos.

Búsqueda binaria

Aunque estructuras de datos especializadas en la búsqueda rápidas como las tablas hash pueden ser más eficientes, la búsqueda binaria se aplica a un amplio rango de problemas de búsqueda.

La forma implícita es aquella en la cual la estructura que lo soporta está definida de esta forma. Este es el caso del Árbol Binario Ordenado (ABO) también denominado Árbol de Búsqueda Binaria (ABB) y es más eficiente cuanto más parejos son sus subárboles, tal el caso de árbol AVL.

La forma explícita es cuando la estructura que soporta al conjunto ordenado es lineal y es el algoritmo el que explicita la búsqueda binaria. Así se busca el elemento del medio, si es el buscado finaliza la búsqueda, de lo contrario si el buscado es menos se hace los mismo en el subconjunto del primer elemento al anterior al medio y si el buscado es mayor se hace lo mismo en el subconjunto del siguiente al medio hasta el último.

Recorrido de un árbol binario

Siendo el árbol

Árbol binario

Pre-Order (Raíz, izquierda, derecha)

El recorrido previo al pedido (raíz) es atravesar el nodo, luego el subárbol izquierdo del nodo y luego el subárbol derecho del nodo.

Por lo tanto, el recorrido previo al pedido del árbol anterior será:

1 2 4 5 3 6 7

Pre-Order

preorden(nodo)
  si nodo == nulo entonces retorna
  imprime nodo.valor
  preorden(nodo.izquierda)
  preorden(nodo.derecha)

In-Order (Izquierda, Raíz, Derecha)

En orden (transversal) está atravesando el subárbol izquierdo del nodo, luego el nodo y luego el subárbol derecho del nodo.

Así que el recorrido en orden del árbol anterior será:

4 2 5 1 6 3 7

In-Order

inorden(nodo)
  si nodo == nulo entonces retorna
  inorden(nodo.izquierda)
  imprime nodo.valor
  inorden(nodo.derecha)

Post-Order (Izquierda, Derecha, Raíz)

El recorrido posterior al pedido (raíz) recorre el subárbol izquierdo del nodo, luego el subárbol derecho y luego el nodo.

Por lo tanto, el recorrido posterior al pedido del árbol anterior será:

4 5 2 6 7 3 1

Post-Order

postorden(nodo)
  si nodo == nulo entonces retorna
  postorden(nodo.izquierda)
  postorden(nodo.derecha)
  imprime nodo.valor