Árboles AVL / rojo-negro

Inserta 1–31 claves enteras signadas en base 10 de −9999 a 9999, usando como máximo 512 caracteres. Comas o espacios separan las claves; las entradas vacías entre comas y las comas finales no son válidas. Se aceptan ceros a la izquierda y un signo más opcional. Se rechazan puntos decimales, exponentes, notación hexadecimal y números parciales. Las claves duplicadas se leen pero se omiten: el árbol representa un conjunto.

Paso muestra una operación real: acoplar un nodo nuevo, una rotación simple a izquierda o derecha, un grupo de cambios de color, una inserción terminada o un duplicado omitido. Una rotación doble tiene dos fotogramas de rotación separados. Los recuentos de rotaciones cuentan rotaciones individuales; los de recoloreo cuentan grupos que cambian de color de verdad, incluida restaurar una raíz negra. Claves leídas incluye la clave actual desde su fotograma de inserción. El recuento de claves únicas excluye duplicados.

Las rotaciones conservan el orden de búsqueda binaria: todas las claves del subárbol izquierdo son menores, todas las del derecho mayores. Inorden lista las claves de izquierda a derecha. El equilibrio AVL es altura izquierda menos altura derecha, entre −1 y 1 tras cada inserción terminada. Aquí un subárbol vacío tiene altura 0 y una hoja altura 1.

La variante rojo-negro usa la reparación clásica de inserción, no la variante left-leaning. La raíz y las hojas NIL omitidas son negras; los nodos rojos no tienen hijos rojos; todo camino de un nodo a una hoja NIL tiene el mismo recuento de nodos negros. La tabla de nodos cuenta el nodo actual si es negro y cuenta la hoja NIL final; NIL solo tiene por tanto altura negra 1. Un guion indica alturas negras desiguales durante la reparación. Las letras de color complementan los colores de los nodos.

Las instantáneas intermedias pueden violar temporalmente el equilibrio o las propiedades rojo-negro. El resumen las confirma solo en fronteras de inserción terminada o duplicado. Los contornos marcan nodos afectados; un contorno discontinuo marca la antigua raíz de subárbol de una rotación. Su hijo promovido y cualquier raíz de subárbol movida se nombran bajo la acción.

Iniciar reanuda una traza pausada y reinicia una terminada. Atrás y Paso permiten recorrer las operaciones en ambos sentidos. Borrar borra la traza y conserva las entradas. Cambiar las claves o el tipo borra el resultado. El ejemplo de reparación elige rojo–negro; los demás mantienen el tipo. Intro inserta una línea; Ctrl/Comando+Intro ejecuta. Las entradas sin procesar, incluso incompletas, la selección, la velocidad, los detalles y el paso actual se guardan localmente. Recargar o volver dentro de la aplicación restaura un paso válido en pausa; nunca reanuda automáticamente. Los árboles grandes se desplazan sin reducir etiquetas. La inserción equilibrada es O(log n); las instantáneas independientes y el dibujo añaden trabajo en este visualizador acotado.

Fuentes: MIT 6.006 (2011), lecture 6, AVL trees; MIT 6.046 (2005), lecture 10, red–black trees.

La operación actual y el árbol se muestran primero. Los detalles del proceso incluyen contadores y claves ordenadas; los detalles de nodos abren la tabla con desplazamiento local. Pausa aparece solo durante la reproducción. El contador de pasos desaparece al terminar.

El almacenamiento local admite hasta 100000 caracteres serializados. Por encima se conserva la copia anterior; descarga todas las claves antes de recargar o salir de la página. La navegación interna conserva el borrador actual. Una traza admite hasta 31 claves y 512 caracteres; los borradores mayores siguen editables pero no se ejecutan. Las entradas antiguas siguen siendo legibles; las versiones anteriores no guardaban pasos.