title: red black tree insert implementation - what is a sentinel?
body: <p>I got this code from <a href="http://web.mit.edu/~emin/www.old/source_code/cpp_trees/index.html" rel="nofollow">http://web.mit.edu/~emin/www.old/source_code/cpp_trees/index.html</a>
  and its constructor for a red black node is</p>
  
  <pre><code>RedBlackTree::RedBlackTree()
  {
    nil = new RedBlackTreeNode;
    nil-&gt;left = nil-&gt;right = nil-&gt;parent = nil;
    nil-&gt;red = 0;
    nil-&gt;key = MIN_INT;
    nil-&gt;storedEntry = NULL;
  
    root = new RedBlackTreeNode;
    root-&gt;parent = root-&gt;left = root-&gt;right = nil;
    root-&gt;key = MAX_INT;
    root-&gt;red=0;
    root-&gt;storedEntry = NULL;  
  }
  </code></pre>
  
  <p>What is nil and why is it initialized in the constructor? Can I just declare a nil node in my private data field and initialize it in my insert function?</p>