En programación informática, un nodo centinela es un nodo específicamente designado que se utiliza con listas enlazadas y árboles como finalizador de ruta de recorrido. Este tipo de nodo no contiene ni hace referencia a ningún dato administrado por la estructura de datos.
Los centinelas se utilizan como alternativa al uso NULLcomo terminador de ruta para obtener uno o más de los siguientes beneficios:
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 dada en una lista enlazada simple . La primera utiliza el valor centinela NULL y la segunda un (puntero al) nodo centinela Sentinelcomo indicador de fin de lista. Las declaraciones de la estructura de datos de la lista enlazada simple y los resultados de ambas subrutinas son los mismos.
struct sll_node { // un nodo de la lista enlazada simple struct sll_node * next ; // indicador de fin de lista o -> siguiente nodo int key ; } sll , * first ; // inicialización globalprimero = NULL ; // antes de la primera inserción (no se muestra) struct sll_node * Buscar ( struct sll_node * primero , int clave_de_búsqueda ) { estructura sll_node * nodo ; para ( nodo = primero ; nodo != NULL ; nodo = nodo -> siguiente ) { si ( nodo -> clave == clave_búsqueda ) nodo de retorno ; // encontrado } // search_key no está contenida en la lista: devuelve NULL ; }El forbucle contiene dos pruebas (líneas amarillas) por iteración:
node != NULL;if (node->key == search_key).El puntero disponible globalmente sentinela la estructura de datos preparada deliberadamente Sentinelse utiliza como indicador de final de lista.
// variable globalsll_node Centinela , * centinela = & Centinela ; // 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 debe mantenerse mediante las funciones de inserción y eliminación. Sin embargo, implica aproximadamente el mismo esfuerzo que cuando se utiliza un puntero NULL.
struct sll_node * SearchWithSentinelnode ( struct sll_node * first , int search_key ) { struct sll_node * node ; // Preparar el “nodo” Sentinel para la búsqueda: sentinel -> key = search_key ; for ( node = first ; node -> key != search_key ; node = node -> next ) {} // Posprocesamiento: if ( node != sentinel ) return node ; // encontrado // search_key no está contenida en la lista: return NULL ; } El forbucle contiene solo una prueba (línea amarilla) por iteración:
node->key != search_key;.Las implementaciones de listas enlazadas, especialmente las de una lista circular doblemente enlazada, se pueden simplificar notablemente utilizando un nodo centinela para demarcar el principio y el final de la lista.
A continuación se muestra una implementación en Python de una lista circular doblemente enlazada:
clase Nodo : def __init__ ( self , data , next = None , prev = None ): self . data = data self . next = next self . prev = prev def __repr__ ( self ) -> str : return f 'Nodo(datos= { self . datos } )'clase LinkedList : def __init__ ( self ): self . _sentinel = Node ( data = None ) self . _sentinel . next = self . _sentinel self . _sentinel . prev = self . _sentinel def pop_left ( self ) - > Nodo : return self.remove_by_ref ( self._sentinel.next ) def pop ( self ) - > Nodo : 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.add_node ( self._sentinel.prev , nodo ) def append_left ( self , data ) : nodo = Nodo ( data = data ) self.append_nodeleft ( nodo ) def append ( self , data ) : nodo = Nodo ( data = data ) self.append_node ( nodo ) def remove_by_ref ( self , node ) - > Node : si node es self._sentinel : genera una excepción ( ' Nunca se puede eliminar sentinel . ' ) node.prev.next = node.next node.next.prev = node.prev node.prev = None node.next = None devolver node def add_node ( self , curnode , newnode ) : newnode.next = curnode.next newnode.prev = curnode curnode.next.prev = newnode curnode.next = newnode def búsqueda ( self , valor ): self . _sentinel . datos = valor nodo = self . _sentinel . siguiente mientras nodo . datos != valor : nodo = nodo . siguiente self . _sentinel . datos = Ninguno si nodo es self . _sentinel : devolver Ninguno devolver nodo def __iter__ ( self ): nodo = self . _sentinel . next mientras nodo no sea self . _sentinel : rendimiento nodo . datos nodo = nodo . next def reviter ( self ) : nodo = self._sentinel.prev mientras nodo no sea self._sentinel : rendimiento nodo.datos nodo = nodo.prev 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 curnodeserá el nodo centinela.
Declaraciones generales, similares al artículo Árbol binario de búsqueda :
struct bst_node { // un nodo del árbol de búsqueda binario struct bst_node * child [ 2 ]; // cada uno: ->nodo o indicador de fin de ruta int key ; } ; struct bst { // árbol de búsqueda binaria struct bst_node * root ; // ->nodo o indicador de fin de ruta } * BST ; El puntero sentinel disponible globalmente a la única estructura de datos preparada deliberadamente Sentinel = *sentinelse utiliza para indicar la ausencia de un niño.
// variable globalbst_node Centinela , * centinela = & Centinela ; // inicialización globalCentinela . niño [ 0 ] = Centinela . niño [ 1 ] = centinela ; BST -> root = sentinel ; // antes de la primera inserción (no se muestra) Tenga en cuenta que el puntero centinela siempre debe representar cada hoja del árbol. Esto debe ser mantenido por las funciones de inserción y eliminación. Sin embargo, implica aproximadamente el mismo esfuerzo que cuando se utiliza un puntero NULL.
estructura bst_node * SearchWithSentinelnode ( estructura bst * bst , int clave_búsqueda ) { estructura bst_node * nodo ; // Preparar el “nodo” Sentinel para la búsqueda: centinela -> clave = clave_de_búsqueda ; para ( nodo = bst -> raíz ;;) { si ( clave_búsqueda == nodo -> clave ) romper ; si search_key < nodo -> clave : nodo = nodo -> hijo [ 0 ]; // ir a la izquierda demás nodo = nodo -> hijo [ 1 ]; // ir a la derecha } // Posprocesamiento: si ( nodo != centinela ) nodo de retorno ; // encontrado // search_key no está contenida en el árbol: devuelve NULL ; }