En la publicación anterior , presentamos B-Tree. También discutimos las funciones de búsqueda() y poligonal(). En esta publicación, se analiza la operación insert(). Siempre se inserta una nueva clave en el Node hoja. Sea k la llave a insertar. Al igual que BST, comenzamos desde la raíz y avanzamos hacia abajo hasta llegar a un … Continue reading «Insertar operación en B-Tree – Part 1»
Un árbol de búsqueda ternario es una estructura de datos trie especial donde los Nodes secundarios de un trie estándar se ordenan como un árbol de búsqueda binario. Representación de árboles de búsqueda ternarios: a diferencia de la estructura de datos trie (estándar) donde cada Node contiene 26 punteros para sus hijos, cada Node en … Continue reading «Árbol de búsqueda ternario – Part 1»
Dada una array arr[0 . . . n-1] . Necesitamos encontrar eficientemente el valor mínimo y máximo desde el índice qs (inicio de consulta) hasta qe (final de consulta) donde 0 <= qs <= qe <= n-1. Nos dan varias consultas. Ejemplos: Input : arr[] = {1, 8, 5, 9, 6, 14, 2, 4, 3, … Continue reading «Consultas de rango mínimo-máximo en array»
Árbol: – Un gráfico conexo sin ningún circuito se llama árbol. En otras palabras, un árbol es un grafo no dirigido G que satisface cualquiera de las siguientes condiciones equivalentes: Dos vértices cualesquiera de G pueden estar conectados por un único camino simple. G es acíclico y se forma un ciclo simple si se agrega … Continue reading «Algunos teoremas básicos sobre árboles»
Dada una array arr de tamaño N . La tarea es encontrar el k-ésimo elemento más pequeño en el subarreglo (l a r, ambos inclusive). Nota : Las consultas son de tipo consulta (l, r, k) 1 <= k <= r-l+1 Puede haber múltiples consultas. Ejemplos: Entrada: arr = {3, 2, 5, 4, 7, 1, … Continue reading «K-ésimo elemento más pequeño en un subarreglo»
Dada una array arr[] que consta de N enteros, la tarea es encontrar el XOR bit a bit máximo de todos los pares posibles en la array dada . Ejemplos: Entrada: arr[] = {25, 10, 2, 8, 5, 3} Salida: 28 Explicación: El resultado máximo es 5^25 = 28. Entrada: arr[] = {1, 2, 3, … Continue reading «XOR máximo de dos números en una array | conjunto 2»
N Nodes dados en un plano 2-D representado como (x i , y i ) . Se dice que los Nodes están conectados si la distancia de Manhattan entre ellos es 1 . Puede conectar dos Nodes que no están conectados a costa de la distancia euclidiana entre ellos. La tarea es conectar el gráfico … Continue reading «Gráfico de costo mínimo»
Dada una array arr[] , la tarea es encontrar las sub-arrays más pequeñas con GCD igual a 1 . Si no existe tal subarreglo, imprima -1 . Ejemplos: Entrada: arr[] = {2, 6, 3} Salida: 3 {2, 6, 3} es el único subarreglo con GCD = 1. Entrada: arr[] = {2, 2, 2} Salida: -1 … Continue reading «El subarreglo más pequeño con GCD como 1 | Árbol de segmentos»
Dada una array de n números, la tarea es responder a las siguientes consultas: kthSmallest(start, end, k) : Find the Kth smallest number in the range from array index ‘start’ to ‘end’. Ejemplos: Input : arr[] = {3, 2, 5, 1, 8, 9| Query 1: start = 2, end = 5, k = 2 Query … Continue reading «Combinar clasificación de árbol para estadísticas de orden de rango»
Dada una string de texto y una string de patrón, encuentre todas las ocurrencias del patrón en la string. Ya se han discutido algunos algoritmos de búsqueda de patrones ( KMP , Rabin-Karp , Naive Algorithm , Finite Automata ) que se pueden usar para esta verificación. Aquí discutiremos el algoritmo basado en el árbol … Continue reading «Aplicación de árbol de sufijos 2: búsqueda de todos los patrones»