En programación de computadoras, un nodo centinela es un nodo específicamente designado que se usa con listas y árboles vinculados como un terminador de ruta transversal. Este tipo de nodo no contiene ni hace referencia a ningún dato gestionado por la estructura de datos.
Beneficios
Los centinelas se utilizan como una alternativa al uso NULL
como terminador de ruta para obtener uno o más de los siguientes beneficios:
- Velocidad de operaciones ligeramente aumentada
- Mayor solidez de la estructura de datos (posiblemente)
Inconvenientes
- Complejidad algorítmica y tamaño de código ligeramente aumentados.
- Si se accede a la estructura de datos al mismo tiempo (lo que significa que todos los nodos a los que se accede deben estar protegidos al menos para "solo lectura" ), para una implementación basada en centinela, el nodo centinela debe estar protegido para "lectura-escritura" por un mutex . Este mutex adicional en bastantes escenarios de uso puede causar una degradación severa del rendimiento. [1] Una forma de evitarlo es proteger la estructura de la lista como un todo para "lectura-escritura", mientras que en la versión con
NULL
esto es suficiente proteger la estructura de datos como un todo para "sólo lectura" (si una operación de actualización no seguirá). - El concepto centinela no es útil para el registro de la estructura de datos en disco.
Ejemplos de
Buscar en una lista vinculada
A continuación se muestran dos versiones de una subrutina (implementada en el lenguaje de programación C ) para buscar una clave de búsqueda determinada en una lista enlazada individualmente . El primero usa el valor centinela NULL
y el segundo un (puntero al) nodo centinela Sentinel
, como indicador de fin de lista. Las declaraciones de la estructura de datos de la lista enlazada individualmente y los resultados de ambas subrutinas son los mismos.
struct sll_node { // un nodo de la lista enlazada individualmente struct sll_node * next ; // indicador de fin de lista o -> siguiente clave int del nodo ; } sll , * primero ;
Primera versión que usa NULL como indicador de fin de lista
// inicialización globalprimero = NULO ; // antes de la primera inserción (no se muestra)struct sll_node * Buscar ( struct sll_node * primero , int clave_búsqueda ) { struct sll_node * nodo ; para ( nodo = primero ; nodo ! = NULO ; nodo = nodo -> siguiente ) { if ( nodo -> clave == clave_búsqueda ) nodo de retorno ; // encontró } // clave_búsqueda no está incluida en la lista: return NULL ;}
El for
bucle contiene dos pruebas (líneas amarillas) por iteración:
node != NULL;
if (node->key == search_key)
.
Segunda versión usando un ganglio centinela
El puntero disponible globalmente sentinel
a la estructura de datos preparada deliberadamente Sentinel
se utiliza como indicador de fin de lista.
// variable globalsll_node Sentinel , * sentinel = & Sentinel ;// inicialización globalcentinela -> siguiente = centinela ;primero = centinela ; // antes de la primera inserción (no se muestra)
Tenga en cuenta que el puntero centinela siempre debe mantenerse al final de la lista. Esto tiene que ser mantenido por las funciones de inserción y eliminación. Sin embargo, es aproximadamente el mismo esfuerzo que cuando se usa un puntero NULL.
struct sll_node * SearchWithSentinelnode ( struct sll_node * primero , int clave_búsqueda ) { struct sll_node * nodo ; // Preparar el “nodo” Sentinel para la búsqueda: sentinel -> key = search_key ; para ( nodo = primero ; nodo -> clave ! = clave_búsqueda ; nodo = nodo -> siguiente ) {} // Post-procesamiento: if ( nodo ! = Centinela ) return nodo ; // encontrado // clave_búsqueda no está contenida en la lista: return NULL ; }
El for
bucle contiene solo una prueba (línea amarilla) por iteración:
node->key != search_key;
.
Implementación en Python de una lista circular doblemente enlazada
Las implementaciones de listas vinculadas, especialmente una de una lista circular, doblemente vinculada, se pueden simplificar notablemente utilizando un nodo centinela para demarcar el principio y el final de la lista.
- La lista comienza con un solo nodo, el nodo centinela que tiene los punteros siguiente y anterior apuntando a sí mismo. Esta condición determina si la lista está vacía.
- En una lista no vacía, el siguiente puntero del nodo centinela da la cabeza de la lista, y el puntero anterior da la cola de la lista.
A continuación se muestra una implementación de Python de una lista circular doblemente enlazada:
class Node : def __init__ ( self , data , next = None , prev = None ): self . datos = datos propios . siguiente = siguiente yo . prev = prev def __repr__ ( self ) -> str : return f 'Node (data = { self . data } )'class LinkedList : def __init__ ( self ): self . _sentinel = Nodo ( datos = Ninguno ) self . _sentinel . siguiente = yo . _sentinel self . _sentinel . prev = self . _centinela def pop_left ( self ) -> Nodo : return self . remove_by_ref ( self . _sentinel . siguiente ) def pop ( self ) -> Node : return self . remove_by_ref ( self . _sentinel . prev ) def append_nodeleft ( self , nodo ): self . add_node ( self . _sentinel , nodo ) def append_node ( self , nodo ): self . agregar_nodo ( self . _sentinel . prev , nodo ) def append_left ( self , datos ): nodo = Nodo ( datos = datos ) self . append_nodeleft ( nodo ) def append ( self , datos ): nodo = Nodo ( datos = datos ) self . append_node ( nodo ) def remove_by_ref ( self , node ) -> Node : si el nodo es self . _sentinel : aumento de excepción ( 'nunca se puede eliminar el centinela.' ) del nodo . prev . siguiente = nodo . siguiente nodo . siguiente . prev = nodo . nodo anterior . prev = Ninguno nodo . siguiente = Ninguno devuelve el nodo def add_node ( self , curnode , newnode ): newnode . siguiente = curnode . siguiente newnode . prev = curnode curnode . siguiente . prev = newnode curnode . siguiente = newnode def búsqueda ( yo , valor ): yo . _sentinel . datos = valor nodo = uno mismo . _sentinel . siguiente while nodo . datos ! = valor : nodo = nodo . siguiente yo . _sentinel . datos = Ninguno si el nodo es propio . _sentinel : return None return node def __iter__ ( self ): nodo = self . _sentinel . siguiente mientras que el nodo no es uno mismo . _sentinel : nodo de rendimiento . nodo de datos = nodo . Siguiente def reviter ( self ): nodo = self . _sentinel . prev mientras que el nodo no es uno mismo . _sentinel : nodo de rendimiento . nodo de datos = nodo . anterior
Observe cómo el add_node()
método toma el nodo que será desplazado por el nuevo nodo en el parámetro curnode
. Para agregar a la izquierda, este es el encabezado de una lista no vacía, mientras que para agregar a la derecha, es la cola. Pero debido a cómo se configura el enlace para hacer referencia al centinela, el código también funciona para listas vacías, donde curnode
estará el nodo centinela.
Buscar en un árbol binario
Declaraciones generales, similar al árbol de búsqueda binaria del artículo :
struct bst_node { // un nodo del árbol de búsqueda binario struct bst_node * child [ 2 ]; // cada uno: -> clave int del indicador de fin de ruta o nodo ; } ; struct bst { // árbol de búsqueda binaria struct bst_node * root ; // -> indicador de nodo o fin de ruta } * BST ;
El puntero disponible globalmente sentinel
a la estructura de datos única preparada deliberadamente Sentinel = *sentinel
se utiliza para indicar la ausencia de un niño.
// variable globalbst_node Sentinel , * sentinel = & Sentinel ;// inicialización globalCentinela . niño [ 0 ] = Centinela . niño [ 1 ] = centinela ;BST -> raíz = centinela ; // antes de la primera inserción (no se muestra)
Tenga en cuenta que el puntero centinela siempre tiene que representar cada hoja del árbol. Esto tiene que ser mantenido por las funciones de inserción y eliminación. Sin embargo, es aproximadamente el mismo esfuerzo que cuando se usa un puntero NULL.
struct bst_node * SearchWithSentinelnode ( struct bst * bst , int search_key ) { struct bst_node * nodo ; // Prepara el "nodo" Sentinel para la búsqueda: centinela -> clave = clave_búsqueda ; para ( nodo = bst -> raíz ;;) { si ( clave_búsqueda == nodo -> clave ) romper ; si clave_búsqueda < nodo -> clave : nodo = nodo -> hijo [ 0 ]; // ve a la izquierda demás nodo = nodo -> hijo [ 1 ]; // ve a la derecha } // Postprocesamiento: si ( nodo ! = centinela ) nodo de retorno ; // encontró // clave_búsqueda no está contenida en el árbol: return NULL ;}
- Observaciones
- Con el uso de SearchWithSentinelnode, la búsqueda pierde la propiedad R / O. Esto significa que en aplicaciones con concurrencia tiene que estar protegido por un mutex , un esfuerzo que normalmente excede los ahorros del centinela.
- SearchWithSentinelnode no admite la tolerancia de duplicados.
- Tiene que haber exactamente un "nodo" para ser utilizado como centinela, pero puede haber muchísimos indicadores hacia él.
Ver también
Referencias
- ^ Ignatchenko, Sergey (1998), "Implementaciones de STL y seguridad de subprocesos", Informe de C ++