Categoría: Red Black Tree

Árbol de intervalos utilizando un contenedor basado en árboles GNU

Posted on by Rudeus Greyrat

Considere una situación en la que tenemos un conjunto de intervalos y necesitamos que las siguientes operaciones se implementen de manera eficiente:  Agregar un intervalo Eliminar un intervalo Dado un intervalo x, encuentre si x se superpone con cualquiera de los intervalos existentes. Un árbol de intervalos se puede implementar como un árbol de búsqueda … Continue reading «Árbol de intervalos utilizando un contenedor basado en árboles GNU»

Árbol rojo-negro | Serie 1 (Introducción)

Posted on by Rudeus Greyrat

Introducción: Un árbol rojo-negro es una especie de árbol de búsqueda binario autoequilibrado en el que cada Node tiene un bit adicional, y ese bit a menudo se interpreta como el color (rojo o negro). Estos colores se utilizan para garantizar que el árbol permanezca equilibrado durante las inserciones y eliminaciones. Aunque el equilibrio del … Continue reading «Árbol rojo-negro | Serie 1 (Introducción)»

Árbol rojo-negro | Juego 2 (insertar)

Posted on by Rudeus Greyrat

En la publicación anterior , discutimos la introducción a Red-Black Trees. En este post, se discute la inserción. En la inserción del árbol AVL , usamos la rotación como una herramienta para equilibrar después de la inserción. En el árbol rojo-negro, usamos dos herramientas para equilibrar.  Recolorear Rotación Recolorear es el cambio de color del … Continue reading «Árbol rojo-negro | Juego 2 (insertar)»

Árbol rojo negro vs árbol AVL

Posted on by Rudeus Greyrat

En esta publicación, compararemos Red-Black Tree y AVL Tree.  Árbol negro rojo :  Propiedades :   El autoequilibrio se proporciona pintando cada Node con dos colores (rojo o negro). Cuando se modifica el árbol, se reorganiza y pinta un nuevo árbol. Requiere 1 bit de información de color para cada Node en el árbol. Complejidad temporal: … Continue reading «Árbol rojo negro vs árbol AVL»

Árbol rojo-negro | Grupo 3 (Borrar)

Posted on by Rudeus Greyrat

Hemos discutido los siguientes temas sobre el árbol rojo-negro en publicaciones anteriores. Recomendamos encarecidamente hacer referencia a la siguiente publicación como requisito previo de esta publicación. Introducción al árbol rojo y negro Árbol rojo y  negro Insertar Inserción frente a eliminación:  al igual que la inserción, el cambio de color y las rotaciones se utilizan … Continue reading «Árbol rojo-negro | Grupo 3 (Borrar)»

Programa C para la inserción de árboles rojos y negros

Posted on by Rudeus Greyrat

El siguiente artículo es una extensión del artículo discutido aquí . En la inserción del árbol AVL , usamos la rotación como una herramienta para equilibrar después de que la inserción causara un desequilibrio. En Red-Black tree, usamos dos herramientas para equilibrar. Recolorear  Rotación Intentamos volver a colorear primero, si el cambio de color no … Continue reading «Programa C para la inserción de árboles rojos y negros»

Compruebe si un árbol binario dado tiene una altura equilibrada como un árbol rojo-negro

Posted on by Rudeus Greyrat

En un árbol rojo-negro , la altura máxima de un Node es como máximo el doble de la altura mínima ( las cuatro propiedades del árbol rojo-negro aseguran que esto siempre se cumpla). Dado un árbol de búsqueda binario, debemos verificar la siguiente propiedad.  Para cada Node, la longitud del camino más largo de hoja … Continue reading «Compruebe si un árbol binario dado tiene una altura equilibrada como un árbol rojo-negro»

Árbol negro rojo inclinado a la izquierda (inserción)

Posted on by Rudeus Greyrat

Prerrequisitos: árboles rojos y negros. Un árbol rojo y negro inclinado a la izquierda o (LLRB) , es una variante del árbol rojo y negro, que es mucho más fácil de implementar que el propio árbol rojo y negro y garantiza todas las operaciones de búsqueda, eliminación e inserción en tiempo O (logn). ¿Qué Nodes … Continue reading «Árbol negro rojo inclinado a la izquierda (inserción)»

Encuentre K para cada elemento de Array tal que al menos K prefijos sean ≥ K

Posted on by Rudeus Greyrat

Dada una array arr[] que consta de N enteros no negativos, la tarea es encontrar un entero K para cada índice tal que al menos K enteros en la array hasta ese índice sean mayores o iguales a K. Nota: considere la indexación basada en 1 Ejemplos: Entrada: arr[] = {3, 0, 6, 1, 5}  … Continue reading «Encuentre K para cada elemento de Array tal que al menos K prefijos sean ≥ K»

Estructura de datos del árbol de tango

Posted on by Rudeus Greyrat

Tango Tree es un algoritmo en línea . Es un tipo de árbol de búsqueda binaria. Es mejor que el árbol de búsqueda binaria equilibrada de peso fuera de línea, ya que logra una relación competitiva en comparación con la relación competitiva del árbol de búsqueda binaria equilibrada de peso fuera de línea. Solo se … Continue reading «Estructura de datos del árbol de tango»