Sentinel node

Sentinel node

A sentinel node is a programming idiom used to speed up some operations on linked lists and trees. It refers to a special type of object that represents the end of a data structure. Linked list data structures may use a sentinel object to indicate the end of a list. Similarly, a tree data structure can use a sentinel to indicate a node without children. It is not always necessary to use a sentinel node. Often null is used instead.

Example

Below is an example of a sentinel node in a binary tree implementation, from [http://www.eternallyconfuzzled.com/tuts/andersson.html] (which is about AA trees):

struct jsw_node { int data; int level; struct jsw_node *link [2] ;};

struct jsw_node *nil;

int jsw_init ( void ){ nil = malloc ( sizeof *nil ); if ( nil = NULL ) return 0;

nil->level = 0; nil->link [0] = nil->link [1] = nil;

return 1;}

As nodes that would normally link to NULL now link to "nil" (including nil itself), it removes the need for an expensive branch operation to check for NULL. NULL itself is known as a "sentinel value", a different approach to the same problem.

Sentinel nodes are often used when implementing linked lists.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • sentinel node — n the first lymph node to receive lymphatic drainage from the site of a primary tumor <studies concluded that sentinel node biopsy can predict whether axillary node metastasis is present (Lecia M. Apantaku)> <the use of sentinel nodes… …   Medical dictionary

  • Sentinel-Node-Szintigraphie — Wächterlymphknoten (auch Sentinel Lymphknoten, von engl. sentinel für „Wächter“) ist ein Konzept in der Erkennung (Diagnose) und Behandlung (Therapie) bestimmter bösartiger Tumoren (Krebs), insbesondere Brustkrebs (Mammakarzinom), schwarzer… …   Deutsch Wikipedia

  • sentinel node biopsy — biopsy of a sentinel node to assess for malignancy; if it does not contain malignant cells, this usually eliminates the need for removal of more distal nodes. Called also intraoperative lymphatic mapping …   Medical dictionary

  • Sentinel lymph node — The sentinel lymph node is the hypothetical first lymph node or group of nodes reached by metastasizing cancer cells from a tumor.PhysiologyThe spread of some forms of cancer usually follows an orderly progression, spreading first to regional… …   Wikipedia

  • Node, sentinel lymph — The first lymph node ( gland ) to receive lymphatic drainage from a tumor. Which lymph node is the sentinel node for a given tumor is determined by injecting around the tumor a tracer substance that will travel through the lymphatic system to the …   Medical dictionary

  • Sentinel lymph node — The first lymph node ( gland ) to receive lymphatic drainage from a tumor. Which lymph node is the sentinel node in a given case is determined by injecting around the tumor a tracer substance that will travel through the lymphatic system to the… …   Medical dictionary

  • Sentinel-lymph-node biopsy — Examination of the first lymph node ( gland ) that receives lymphatic drainage from a tumor to learn whether that node does or does not have tumor cells within it. Which lymph node is the sentinel node for a given tumor is determined by injecting …   Medical dictionary

  • sentinel lymph node biopsy — Removal and examination of the sentinel node(s) (the first lymph node(s) to which cancer cells are likely to spread from a primary tumor). To identify the sentinel lymph node(s), the surgeon injects a radioactive substance, blue dye, or both near …   English dictionary of cancer terms

  • Sentinel-Lymphknoten — Wächterlymphknoten (auch Sentinel Lymphknoten, von engl. sentinel für „Wächter“) ist ein Konzept in der Erkennung (Diagnose) und Behandlung (Therapie) bestimmter bösartiger Tumoren (Krebs), insbesondere Brustkrebs (Mammakarzinom), schwarzer… …   Deutsch Wikipedia

  • sentinel lymph node — the first lymph node to show evidence of metastasis of a malignant tumour (e.g. breast cancer) via the lymphatic system. Absence of cancer cells in the sentinel node indicates that more distal lymph nodes will also be free of metastasis …   Medical dictionary

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”