Introducción: B-Tree es un árbol de búsqueda autoequilibrado. En la mayoría de los otros árboles de búsqueda autoequilibrados (como AVLy Red-Black Trees), se supone que todo está en la memoria principal. Para comprender el uso de B-Trees, debemos pensar en la enorme cantidad de datos que no caben en la memoria principal. Cuando el … Continue reading «Introducción de B-Tree – Part 1»
Recomendamos encarecidamente consultar las publicaciones a continuación como requisito previo para esto. Árbol dimensional K | Conjunto 1 (Buscar e insertar) K Árbol dimensional | Conjunto 2 (Buscar mínimo) En esta publicación se discute la eliminación. La operación es eliminar un punto dado de KD Tree. Al igual que la eliminación del árbol de búsqueda … Continue reading «Árbol dimensional K | Grupo 3 (Borrar)»
Todas las estructuras de datos discutidas aquí hasta ahora son no persistentes (o efímeras). Una estructura de datos persistente es una estructura de datos que siempre conserva la versión anterior de sí misma cuando se modifica. Se pueden considerar como ‘inmutables’ ya que las actualizaciones no están en su lugar . Una estructura de datos … Continue reading «Estructuras de datos persistentes»
Dada una string str que contiene pares de paréntesis equilibrados, la tarea es calcular la puntuación de la string dada según las reglas dadas: “()” tiene una puntuación de 1. “xy” tiene una puntuación de x + y, donde xey son pares individuales de paréntesis equilibrados. “(x)” tiene una puntuación el doble de x (es … Continue reading «Puntuación de paréntesis usando árbol»
Función hash Una función Hash es una función que asigna cualquier tipo de datos de tamaño arbitrario a valores de tamaño fijo. Los valores devueltos por la función se denominan valores hash o resúmenes. Hay muchas funciones hash populares como DJBX33A, MD5 y SHA-256. Esta publicación discutirá las características clave, la implementación, las ventajas y … Continue reading «Hashing de strings usando la función hash rodante polinomial»
Dada una array arr[] de N enteros. La tarea es hacer las siguientes operaciones: Agregue un valor X a todo el elemento del índice A al B donde 0 ≤ A ≤ B ≤ N-1 . Encuentre la suma del elemento del índice L a R donde 0 ≤ L ≤ R ≤ N-1 antes … Continue reading «Suma de rango y actualización en array: árbol de segmentos usando pila»
Dada una string S de longitud N, y Q consultas del siguiente tipo: Tipo 1: 1 i X Actualiza el i-ésimo carácter de la string con el carácter dado, X. Tipo 2: LR Cuenta el número de caracteres distintos en el rango dado [L, R]. Restricción: 1<=N<=500000 1<=Q<20000 |S|=N La string S contiene solo letras … Continue reading «Consultas de rango de strings para contar el número de caracteres distintos con actualizaciones»
Dada la string binaria str , la tarea es verificar si la string dada sigue la siguiente condición o no: La string comienza con un ‘1’ . Cada ‘1’ va seguido de una string vacía ( «» ), ‘1’ o «00» . Cada «00» va seguido de una string vacía ( «» ), ‘1’ . … Continue reading «Verifique si la string binaria dada sigue la condición dada o no»
Hemos discutido brevemente la tabla dispersa en Consulta mínima de rango (descomposición de raíz cuadrada y tabla dispersa) El concepto de tabla dispersa se usa para consultas rápidas en un conjunto de datos estáticos (los elementos no cambian). Hace un preprocesamiento para que las consultas puedan ser respondidas de manera eficiente. Problema de ejemplo 1: … Continue reading «Tabla dispersa»
En artículos anteriores del árbol de sufijos, creamos un árbol de sufijos para una string y luego consultamos ese árbol para verificar la substring , buscando todos los patrones , la substring repetida más larga y la array de sufijos construida (Todas las operaciones de tiempo lineal). Hay muchos otros problemas en los que están … Continue reading «Árbol de sufijos generalizados 1»