Este artículo es la continuación de los siguientes cuatro artículos: Construcción del árbol de sufijos de Ukkonen – Parte 1 Construcción del árbol de sufijos de Ukkonen – Parte 2 Construcción del árbol de sufijos de Ukkonen – Parte 3 Construcción del árbol de sufijos de Ukkonen – Parte 4 Lea la Parte 1 , … Continue reading «Construcción del árbol de sufijos de Ukkonen – Parte 5»
Considere una situación en la que tenemos un conjunto de intervalos y necesitamos que las siguientes operaciones se implementen de manera eficiente. 1) Agregar un intervalo 2) Eliminar un intervalo 3) Dado un intervalo x, encuentre si x se superpone con alguno de los intervalos existentes. Árbol de intervalos: la idea es aumentar un árbol de … Continue reading «Árbol de intervalos – Part 1»
Tries es un árbol que almacena strings. El número máximo de hijos de un Node es igual al tamaño del alfabeto. Trie admite operaciones de búsqueda, inserción y eliminación en tiempo O(L), donde L es la longitud de la clave. Hashing : – En hashing, convertimos la clave en un valor pequeño y el valor se … Continue reading «Ventajas de la estructura de datos Trie»
Los quadtrees son árboles que se utilizan para almacenar de manera eficiente datos de puntos en un espacio bidimensional. En este árbol, cada Node tiene como máximo cuatro hijos. Podemos construir un quadtree a partir de un área bidimensional siguiendo los siguientes pasos: Divide el espacio bidimensional actual en cuatro cajas. Si una caja contiene … Continue reading «Árbol cuádruple»
Dado un diccionario de palabras y una string de entrada, encuentre el prefijo más largo de la string que también es una palabra en el diccionario. Ejemplos: Let the dictionary contains the following words: {are, area, base, cat, cater, children, basement} Below are some input/output examples: ————————————– Input String Output ————————————– caterer cater basemexy base … Continue reading «Coincidencia de prefijo más larga: una solución basada en Trie en Java»
Prerrequisitos: Casco convexo de Graham Scan , Orientación . Dado un conjunto de N puntos en un plano de coordenadas, la tarea es encontrar la distancia máxima entre dos puntos cualesquiera en el conjunto de planos dado. Ejemplos: Entrada: n = 4, Puntos: (0, 3), (3, 0), (0, 0), (1, 1) Salida: Distancia máxima = … Continue reading «Distancia máxima entre dos puntos en el plano de coordenadas utilizando el método del calibrador giratorio»
Dada una lista enlazada como entrada. La tarea es codificar la lista enlazada dada utilizando la codificación de longitud de ejecución . Es decir, reemplazar un bloque de caracteres contiguos por el carácter seguido de su cuenta. Por ejemplo, en la codificación de longitud de ejecución, «a->a->a->a->a» se reemplazará por «a->5». Nota : para los Nodes … Continue reading «Programa para implementar la codificación de longitud de ejecución usando listas enlazadas»
Un árbol n-ario en informática es una colección de Nodes normalmente representados jerárquicamente de la siguiente manera. El árbol comienza en el Node raíz. Cada Node del árbol contiene una lista de referencias a sus Nodes secundarios. El número de hijos que tiene un Node es menor o igual que n. Una representación típica del … Continue reading «Representación del árbol del hijo izquierdo y del hermano derecho»
Dados N números y Q consultas, cada consulta consta de L y R. La tarea es escribir un programa que imprima el recuento de números que divide todos los números en el rango dado LR. Ejemplos: Input : a = {3, 4, 2, 2, 4, 6} Q = 2 L = 1 R = 4 L … Continue reading «Contar elementos que dividen todos los números en el rango LR»
El árbol de segmentos se introdujo en una publicación anterior con un ejemplo de problema de suma de rangos. Hemos utilizado el mismo problema de «Suma del rango dado» para explicar la propagación perezosa CPP /* A recursive function to update the nodes which have the given index in their range. The following are parameters … Continue reading «Propagación perezosa en el árbol de segmentos»