Dado un libro de palabras. Suponga que tiene suficiente memoria principal para acomodar todas las palabras. Diseñe una estructura de datos para encontrar las K palabras máximas que ocurren. La estructura de datos debe ser dinámica para que se puedan agregar nuevas palabras. Una solución simple es usar Hashing . Hash todas las palabras una por … Continue reading «Encuentra las k palabras más frecuentes de un archivo»
R-tree es una estructura de datos de árbol utilizada para almacenar índices de datos espaciales de manera eficiente. Los árboles R son muy útiles para consultas y almacenamiento de datos espaciales. Algunas de las aplicaciones de la vida real se mencionan a continuación: Indexación de información multidimensional. Manejo de coordenadas geoespaciales. Implementación de mapas virtuales. … Continue reading «Introducción al árbol R»
En la publicación anterior sobre trie , describimos cómo insertar y buscar un Node en trie. Aquí hay un algoritmo sobre cómo eliminar un Node de trie. Durante la operación de eliminación, eliminamos la clave de forma ascendente utilizando la recursividad. Las siguientes son condiciones posibles al eliminar la clave de trie, Es posible que … Continue reading «prueba | (Borrar)»
Dada una array de N (siempre una potencia de 2) elementos y Q consultas. Cada consulta consta de dos elementos, un índice y un valor … Necesitamos escribir un programa que asigne un valor a un índice e imprima el único elemento que queda después de realizar las siguientes operaciones para cada consulta: En pasos … Continue reading «Elemento sobrante después de realizar operaciones alternas Bitwise OR y Bitwise XOR en pares adyacentes»
Consideremos el siguiente problema para comprender el árbol indexado binario. Tenemos una array arr[0 . . . n-1]. Nos gustaría 1 Calcular la suma de los primeros i elementos. 2 Modificar el valor de un elemento especificado de la array arr[i] = x donde 0 <= i <= n-1. Una solución sencillaes ejecutar un ciclo de … Continue reading «Árbol indexado binario o árbol Fenwick»
Hemos discutido la inserción de AVL en la publicación anterior . En esta publicación, seguiremos un enfoque similar para la eliminación. Pasos a seguir para su eliminación . Para asegurarnos de que el árbol dado siga siendo AVL después de cada eliminación, debemos aumentar la operación de eliminación BST estándar para realizar un reequilibrio. Las … Continue reading «Árbol AVL | Juego 2 (Eliminación)»
Requisitos previos: BIT , DFS Dado un árbol enraizado T, con ‘n’ Nodes, cada Node tiene un color indicado por la array color[](color[i] denota el color del i-ésimo Node en forma de número entero). Responder a las consultas ‘Q’ del siguiente tipo: distintiva u – Imprime el número de Nodes de distintos colores bajo el … Continue reading «Consultar la cantidad de colores distintos en un subárbol de un árbol de colores usando BIT»
Nos dan 2*N – 1 enteros. Necesitamos verificar si es posible construir un árbol de segmentos de consulta de rango mínimo para una array de N enteros distintos a partir de estos enteros. Si es así, debemos generar la array de árbol de segmentos. N se da como una potencia de 2. Un árbol de … Continue reading «Reconstrucción del árbol de segmentos»
La programación dinámica (DP) es una técnica para resolver problemas dividiéndolos en subproblemas superpuestos que siguen la subestructura óptima. Hay varios problemas que usan DP como suma de subconjunto, mochila, cambio de moneda, etc. DP también se puede aplicar en árboles para resolver algunos problemas específicos. Requisito previo: DFS Dado un árbol con N Nodes … Continue reading «Programación dinámica en árboles | Serie 1»
Dada una string S de longitud N y una array 2D de strings Q[][] que consta de M consultas del siguiente tipo: Consulta («U», «I», «X»): actualice el carácter en el índice I con el carácter X . Query(“S”, “L”, “R”): Imprime la suma de los cuadrados de la posición de los caracteres en la … Continue reading «Consultas para calcular la suma de los cuadrados de los valores ASCII de los caracteres de una substring con actualizaciones»