Warum ist ein selbstreferenzierender Sentinel in einem rot-schwarzen Baum einfacher als nach NULL zu suchen?

Question

Ich versuche, rot-schwarz Baum Datenstruktur zu implementieren und stolperte this Beispiel von Apple Open Source-Projekt. Dies ist der Code für die Erstellung eines Baumes:

/* 
* Create a red black tree struct using the specified compare routine. 
* Allocates and returns the initialized (empty) tree. 
*/ 
struct rbtree * 
rbcreate(compar) 
    int (*compar)__P((const void *, const void*)); 
{ 
    struct rbtree *tree; 

    tree = (struct rbtree *) emalloc(sizeof(*tree)); 
    tree->compar = compar; 

    /* 
    * We use a self-referencing sentinel node called nil to simplify the 
    * code by avoiding the need to check for NULL pointers. 
    */ 
    tree->nil.left = tree->nil.right = tree->nil.parent = &tree->nil; 
    tree->nil.color = black; 
    tree->nil.data = NULL; 

    /* 
    * Similarly, the fake root node keeps us from having to worry 
    * about splitting the root. 
    */ 
    tree->root.left = tree->root.right = tree->root.parent = &tree->nil; 
    tree->root.color = black; 
    tree->root.data = NULL; 

    return(tree); 
} 

Ich frage mich, was die Argumentation ist die Sentinel-Lymphknoten statt hinter mit den Kindern, die auf NULL zeigen. Auf jeden Fall müssen wir überprüfen, soweit ich es verstehe.

Auch ich verstehe nicht, warum wir gefälschte Wurzel brauchen und wie die Wurzel in der Theorie sogar gespalten werden kann?

Answer 1

Angenommen, Sie möchten eine der Haupteigenschaften des RB-Baums überprüfen, dass keine benachbarten roten Knoten vorhanden sind.

Mit NULL Darstellung, sieht es wie folgt aus:

node->color == black || (node->left == NULL || node->left->color == black) && (node->right == NULL || node->right->color == black)

Sentinel Darstellung ermöglicht es prägnanter ausdrücken:

node->color == black || node->left->color == black && node->right->color == black

Gleiche Vereinfachung gilt für die tatsächlichen Kontrollen im Baum Operationen.

Ähnliche Geschichte mit der falschen Wurzel. Es stellt sicher, dass der Baum niemals leer ist, und eliminiert somit einen Sonderfall aus der Baumeinfügeroutine. (Keine Ahnung was sie mit spucken gemeint haben.)