La complejidad de tiempo del peor de los casos de las operaciones del árbol de búsqueda binaria (BST) como buscar, eliminar, insertar es O(n). El peor caso ocurre cuando el árbol está sesgado. Podemos obtener la complejidad de tiempo del peor de los casos como O (Logn) con AVL y Red-Black Trees. ¿Podemos hacerlo mejor que … Continue reading «Árbol de juego | Grupo 1 (Buscar)»
La principal aplicación de Binary Heap es implementar una cola de prioridad. Binomial Heap es una extensión de Binary Heap que proporciona operaciones de unión o fusión más rápidas con otras operaciones proporcionadas por Binary Heap. Un montón binomial es una colección de árboles binomiales ¿Qué es un árbol binomial? Un Árbol Binomial de orden … Continue reading «Montón binomial»
Algoritmo de Tarjan :el algoritmo de Tarjan es un algoritmo de gráfico eficiente que se utiliza para encontrar el SCC del componente fuertemente conectado en un gráfico dirigido mediante el uso de solo unrecorrido DFSen complejidad de tiempo lineal. Laboral: Realice un recorrido DFS sobre los Nodes para que los subárboles de los componentes fuertemente … Continue reading «Comparación entre el algoritmo de Tarjan y Kosaraju»
Requisitos previos: estructura de datos basada en políticas , técnica de ventana deslizante . Dada una array de enteros arr[] y un entero K , la tarea es encontrar la mediana de cada ventana de tamaño K comenzando desde la izquierda y moviéndose hacia la derecha una posición cada vez. Ejemplos: Entrada: arr[] = {-1, … Continue reading «Mediana de ventana deslizante en una array | conjunto 2»
Prerrequisito: Introducción a las Redes Sociales En las redes sociales, la red es de 2 tipos: red sin firmar y red firmada. En la red sin firmar, no hay señales entre ningún Node, y en la red firmada, siempre hay una señal entre 2 Nodes, ya sea + o -. El signo ‘+’ indica amistad … Continue reading «Redes Firmadas en Redes Sociales»
Gap Buffer es una estructura de datos utilizada para editar y almacenar texto de manera eficiente que se está editando actualmente . También es similar a una array, pero se introduce un espacio en la array para manejar múltiples cambios en el cursor . Supongamos que un espacio es otra array que contiene espacios vacíos. … Continue reading «Estructura de datos del búfer de espacios»
¿Podemos buscar en una lista enlazada ordenada mejor que en tiempo O(n)? El tiempo de búsqueda en el peor de los casos para una lista enlazada ordenada es O (n), ya que solo podemos recorrer la lista de forma lineal y no podemos omitir Nodes durante la búsqueda. Para un árbol de búsqueda binario equilibrado, … Continue reading «Omitir lista | Serie 1 (Introducción)»
Dada una array ‘a[]’ y un número de consultas q. Cada consulta se puede representar mediante l, r, x. Su tarea es imprimir el número de elementos menores o iguales a x en el subarreglo representado por l a r. Ejemplos: Input : arr[] = {2, 3, 4, 5} q = 2 0 3 5 … Continue reading «Número de elementos menores o iguales a un número dado en un subarreglo dado»
Considere una array A[] de enteros y los siguientes dos tipos de consultas. update(l, r, x) : Agrega x a todos los valores de A[l] a A[r] (ambos inclusive). printArray() : Imprime la array modificada actual. Ejemplos: Input : A [] { 10, 5, 20, 40 } update(0, 1, 10) printArray() update(1, 3, 20) update(2, … Continue reading «Array de diferencias | Consulta de actualización de rango en O(1)»
La clasificación cartesiana es una clasificación adaptable, ya que clasifica los datos más rápido si los datos están parcialmente ordenados. De hecho, hay muy pocos algoritmos de clasificación que hagan uso de este hecho. Por ejemplo, considere la array {5, 10, 40, 30, 28}. Los datos de entrada también se ordenan parcialmente, ya que solo … Continue reading «Clasificación de árboles cartesianos»