Descripción general de las estructuras de datos | Conjunto 2 (Árbol binario, BST, Heap y Hash)

Hemos discutido la descripción general de Array, Linked List, Queue y Stack . En este artículo se analizan las siguientes estructuras de datos. 

5. Árbol binario  
6. Árbol de búsqueda  
binaria 7. Montón binario  
9. Hashing 

Árbol binario 
A diferencia de las arrays, las listas vinculadas, la pila y las colas, que son estructuras de datos lineales, los árboles son estructuras de datos jerárquicas. 
Un árbol binario es una estructura de datos de árbol en la que cada Node tiene como máximo dos hijos, a los que se hace referencia como el hijo izquierdo y el hijo derecho. Se implementa principalmente mediante enlaces. 

Representación de árbol binario: un árbol se representa mediante un puntero al Node superior del árbol. Si el árbol está vacío, el valor de la raíz es NULL. Un Node de árbol binario contiene las siguientes partes. 
1. Datos 
2. Puntero al hijo izquierdo 
3. Puntero al hijo derecho 

Un árbol binario se puede recorrer de dos maneras: 
Primer recorrido en profundidad: en orden (raíz izquierda-derecha), en orden previo (raíz-izquierda-derecha) y en orden posterior (raíz izquierda-derecha) Recorrido primero  en amplitud: recorrido en
orden de nivel 

Propiedades del árbol binario: 

The maximum number of nodes at level ‘l’ = 2l.

Maximum number of nodes = 2h + 1 – 1.
Here h is height of a tree. Height is considered 
as the maximum number of edges on a path from root to leaf.

Minimum possible height =  ceil(Log2(n+1)) - 1  

In Binary tree, number of leaf nodes is always one 
more than nodes with two children.

Time Complexity of Tree Traversal: O(n)

Operación básica en el árbol binario:

• Insertar un elemento.
• Eliminación de un elemento.
• Buscando un elemento.
• Atravesando un elemento. 

Operación auxiliar en árbol binario:

• Encontrar la altura del árbol.
• Encuentra el nivel del árbol.
• Encontrar el tamaño de todo el árbol.

Aplicaciones del árbol binario:

• Los árboles de codificación de Huffman se utilizan en algoritmos de compresión de datos.
• Priority Queue es otra aplicación de árbol binario que se utiliza para buscar el máximo o el mínimo en la complejidad del tiempo O (logn).
• En los compiladores, se utilizan árboles de expresión, que es una aplicación de árbol binario.

Recorridos de árboles binarios:

• Recorrido de pedido anticipado: aquí, el recorrido es: raíz – hijo izquierdo – hijo derecho. Significa que primero se recorre el Node raíz, luego su hijo izquierdo y finalmente el hijo derecho.
• Recorrido en orden: Aquí, el recorrido es: hijo izquierdo – raíz – hijo derecho. Significa que primero se recorre el hijo izquierdo, luego su Node raíz y finalmente el hijo derecho.
• Recorrido posterior al orden: aquí, el recorrido es: hijo izquierdo – hijo derecho – raíz. Significa que primero se recorre el hijo izquierdo, luego el hijo derecho y finalmente su Node raíz.
   

Ejemplos: Una razón para usar árboles binarios o árboles, en general, es para las cosas que forman una jerarquía. Son útiles en estructuras de archivos donde cada archivo se encuentra en un directorio particular y existe una jerarquía específica asociada con archivos y directorios. Otro ejemplo en el que los árboles son útiles es el almacenamiento de objetos jerárquicos como JavaScript Document Object Model que considera la página HTML como un árbol con etiquetas anidadas como relaciones padre-hijo. 

Árbol de búsqueda binaria 

Binary Search Tree (BST) es un árbol cuya función principal es buscar un elemento específico.
El árbol de búsqueda binario es un árbol binario con las siguientes propiedades adicionales: 
1. El subárbol izquierdo de un Node contiene solo Nodes con claves menores que la clave del Node. 
2. El subárbol derecho de un Node contiene solo Nodes con claves mayores que la clave del Node. 
3. El subárbol izquierdo y derecho también debe ser un árbol de búsqueda binaria. 

Declaración de árbol de búsqueda binaria

struct BinarySearchTree{
int data;
struct BinarySearchTree* left;
struct BinarySearchTree* right;
};

Dado que es un árbol binario, su declaración es similar al árbol binario.

Operaciones primarias de BST:

• Encontrar el elemento mínimo o máximo.
• Eliminación de un elemento en particular del árbol.
• Insertar un elemento particular en el árbol.

Operaciones BST auxiliares:

• Hallar el k-ésimo elemento más pequeño.
• Para identificar si el árbol binario dado es un BST o no.
   

Complejidades de tiempo: 

Search :  O(h)
Insertion : O(h)
Deletion : O(h)
Extra Space : O(n) for pointers

h: Height of BST
n: Number of nodes in BST

If Binary Search Tree is Height Balanced, 
then h = O(Log n) 

Self-Balancing BSTs such as AVL Tree, Red-Black
Tree and Splay Tree make sure that height of BST 
remains O(Log n)

BST proporciona acceso/búsqueda moderados (más rápido que la lista enlazada y más lento que las arrays). 
BST proporciona una inserción/eliminación moderada (más rápida que Arrays y más lenta que Linked Lists). 

Ejemplos: su uso principal es en aplicaciones de búsqueda donde los datos ingresan/salen constantemente y los datos deben imprimirse en orden. Por ejemplo, en la implementación en sitios web de comercio electrónico donde se agrega un nuevo producto o el producto se agota y todos los productos se enumeran en orden. 

Montón binario 
Un montón binario es un árbol binario con las siguientes propiedades. 
1) Es un árbol completo (Todos los niveles están completamente llenos, excepto posiblemente el último nivel y el último nivel tiene todas las claves tan a la izquierda como sea posible). Esta propiedad de Binary Heap los hace aptos para almacenarse en una array. 
2) Un montón binario es un montón mínimo o un montón máximo. En un montón binario mínimo, la clave en la raíz debe ser mínima entre todas las claves presentes en el montón binario. La misma propiedad debe ser recursivamente verdadera para todos los Nodes en Binary Tree. Max Binary Heap es similar a Min Heap. Se implementa principalmente mediante una array. 
 

Get Minimum in Min Heap: O(1) [Or Get Max in Max Heap]
Extract Minimum Min Heap: O(Log n) [Or Extract Max in Max Heap]
Decrease Key in Min Heap: O(Log n)  [Or Decrease Key in Max Heap]
Insert: O(Log n) 
Delete: O(Log n)

Ejemplo: Se utiliza para implementar colas de prioridad eficientes, que a su vez se utilizan para programar procesos en los sistemas operativos. Las colas de prioridad también se utilizan en los algoritmos gráficos de Dijkstra y Prim. 
La estructura de datos Heap se puede usar para encontrar de manera eficiente los k elementos más pequeños (o más grandes) en una array, fusionando k arrays ordenadas, la mediana de un flujo, etc. 
Heap es una estructura de datos especial y no se puede usar para buscar un elemento en particular. elemento. 
 

Hashing: Hashing es una técnica popular para almacenar y recuperar datos lo más rápido posible. La razón principal detrás del uso de hashing es que brinda resultados óptimos ya que realiza búsquedas óptimas.

¿Por qué usar Hashing? : 

Si observa cuidadosamente, en un árbol de búsqueda binario equilibrado, si intentamos buscar, insertar o eliminar cualquier elemento, entonces la complejidad de tiempo para el mismo es O (logn). Ahora puede haber una situación en la que nuestras aplicaciones quieran hacer las mismas operaciones de una manera más rápida, es decir, de una manera más optimizada y aquí entra en juego el hashing. En hashing, todas las operaciones anteriores se pueden realizar en O(1), es decir, en tiempo constante. Es importante comprender que la complejidad de tiempo del peor de los casos para el hash sigue siendo O(n), pero la complejidad de tiempo del caso promedio es O(1).

Función hash: una función que convierte un número de teléfono grande dado en un pequeño valor entero práctico. El valor entero asignado se utiliza como índice en la tabla hash. Entonces, en términos simples, podemos decir que una función hash se usa para transformar una clave dada en un índice de ranura específico. Su trabajo principal es mapear todas y cada una de las claves posibles en un índice de ranura único. Si cada clave se asigna a un índice de ranura único, la función hash se conoce como función hash perfecta. Es muy difícil crear una función hash perfecta, pero nuestro trabajo como programadores es crear dicha función hash con la ayuda de la cual el número de colisiones sea el menor posible. La colisión se discute más adelante.
Una buena función hash debe tener las siguientes propiedades:
1) Eficientemente computable. 
2) Deben distribuir uniformemente las llaves (Cada posición de la mesa tiene la misma probabilidad para cada llave). 3) Debe minimizar las colisiones 4) Debe tener un factor de carga alto (número de elementos en la tabla dividido por el tamaño de la tabla).                                                      

Por ejemplo, para los números de teléfono, una función hash incorrecta es tomar los primeros tres dígitos. Una mejor función es considerar los últimos tres dígitos. Tenga en cuenta que esta puede no ser la mejor función hash. Puede haber mejores maneras. 

Tabla hash: una array que almacena punteros a registros correspondientes a un número de teléfono determinado. Una entrada en la tabla hash es NIL si ningún número de teléfono existente tiene un valor de función hash igual al índice de la entrada. En términos simples, podemos decir que la tabla hash es una generalización de array. La tabla hash brinda la funcionalidad en la que se almacena una colección de datos de tal manera que es fácil encontrar esos elementos más adelante si es necesario. Esto hace que la búsqueda de un elemento sea muy eficiente.

Manejo de colisiones: dado que una función hash nos proporciona un número pequeño para una clave que es un entero grande o una string, existe la posibilidad de que dos claves den como resultado el mismo valor. La situación en la que una clave recién insertada se asigna a un espacio ya ocupado en la tabla hash se denomina colisión y debe manejarse mediante alguna técnica de manejo de colisiones. Las siguientes son las formas de manejar las colisiones: 

Enstringmiento: la idea es hacer que cada celda de la tabla hash apunte a una lista enlazada de registros que tienen el mismo valor de función hash. El enstringmiento es simple pero requiere memoria adicional fuera de la tabla. 
Direccionamiento abierto: en el direccionamiento abierto, todos los elementos se almacenan en la propia tabla hash. Cada entrada de la tabla contiene un registro o NIL. Al buscar un elemento, examinamos uno por uno los espacios de la tabla hasta que se encuentra el elemento deseado o está claro que el elemento no está en la tabla. 
 

Space : O(n)
Search    : O(1) [Average]    O(n) [Worst case]
Insertion : O(1) [Average]    O(n) [Worst Case]
Deletion  : O(1) [Average]    O(n) [Worst Case]

Hashing parece mejor que BST para todas las operaciones. Pero en hashing, los elementos no están ordenados y en BST los elementos se almacenan de manera ordenada. Además, BST es fácil de implementar, pero las funciones hash a veces pueden ser muy complejas de generar. En BST, también podemos encontrar de manera eficiente el piso y el techo de los valores. 

Ejemplo: el hash se puede utilizar para eliminar duplicados de un conjunto de elementos. También se puede utilizar para encontrar la frecuencia de todos los elementos. Por ejemplo, en los navegadores web, podemos verificar las URL visitadas mediante hashing. En los firewalls, podemos usar hashing para detectar spam. Necesitamos hash de direcciones IP. Hashing se puede usar en cualquier situación en la que desee buscar(), insertar() y eliminar() en tiempo O (1). 

Este artículo es una contribución de Abhiraj Smit . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.