爲什麼紅黑樹中的自引用標記比檢查NULL更簡單？

我試圖實現紅黑樹數據結構，並遇到來自Apple Open Source項目的this示例。這是創建樹的代碼：我想知道什麼是具有前哨淋巴結而不是孩子指着NULL背後的推理爲什麼紅黑樹中的自引用標記比檢查NULL更簡單？

/* 
* 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); 
}

。無論如何我們必須按照我的理解來檢查。

另外我不明白爲什麼我們需要假根，以及根在理論上如何分裂？

來源

2017-07-19 Yos

如果我沒有記錯，一個常見的技巧是將「rb-flag」放入一個通常爲0的子指針的最小位（由於字對齊的地址）。這節省了每個節點的一個字節甚至一個字。在這種情況下，與0進行比較可能不得不掩蓋這一點 - 與自身比較沒有。但是，這只是猜測...... – Scheff

@Scheff：這可能是，但這裏引用的代碼似乎會存儲一個單獨的顏色成員。 – doynax

對不起，我甚至沒有讀過代碼 - 我的錯...... – Scheff

假設您想檢查RB樹的一個主要屬性，即沒有相鄰的紅色節點。

用NULL表示，它看起來像這樣：

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

哨兵表示允許更簡明地表達出來：

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

同樣簡化應用於實際檢查樹操作。

與假根類似的故事。它確保樹永遠不會是空的，從而消除樹插入例程中的特殊情況。（不知道它們是什麼意思）

來源

2017-07-19 14:33:08

除了減少鏈接數據結構中使用標記而不是NULL的特殊情況外，還允許代碼推測性地跟隨鏈，從而使優化器更具有迴旋餘地在重新排序。 – doynax

爲什麼紅黑樹中的自引用標記比檢查NULL更簡單？

回答

相關問題