CODEWITHSUNDEEP
c++binary-search-treered-black-tree
user3871143
user3871143

Reputation:

red black tree insert implementation - what is a sentinel?

I got this code from http://web.mit.edu/~emin/www.old/source_code/cpp_trees/index.html and its constructor for a red black node is

RedBlackTree::RedBlackTree()
{
  nil = new RedBlackTreeNode;
  nil->left = nil->right = nil->parent = nil;
  nil->red = 0;
  nil->key = MIN_INT;
  nil->storedEntry = NULL;

  root = new RedBlackTreeNode;
  root->parent = root->left = root->right = nil;
  root->key = MAX_INT;
  root->red=0;
  root->storedEntry = NULL;  
}

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?

Upvotes: 3

Views: 3496

Answers (2)

sp2danny
sp2danny

Reputation: 7644

a sentinel is an empty node, it's used instead of nullptr,
because it removes the need for special handling of all the
corner-cases, ie last node, first node etc.

Upvotes: 2

Camron_Godbout
Camron_Godbout

Reputation: 1633

It is basically a place holder.

From the codes README: /* A sentinel is used for root and for nil. These sentinels are created when RedBlackTreeCreate is caled. root->left should always point to the node which is the root of the tree. nil points to a node which should always be black but has aribtrary children and parent and no key or info. The point of using these sentinels is so that the root and nil nodes do not require special cases in the code */

From wikipedia red-black tree

1.A node is either red or black.

2.The root is black. (This rule is sometimes omitted. Since the root can always be changed from red to black, but not necessarily vice-versa, this rule has little effect on analysis.)

3.All leaves (NIL) are black. (All leaves are same color as the root.)

4.Every red node must have two black child nodes.

5.Every path from a given node to any of its descendant leaves contains the same number of black nodes.

Upvotes: 3

Related Questions