CODEWITHSUNDEEP
algorithmbinary-search-treered-black-treeclrs
Ralph
Ralph

Reputation: 3029

What is considered a leaf in red black trees?

I am studying red black trees from CLRS. I have 2 questions about the part where properties of red-black trees are discussed. The passage from CLRS is as follows:

A red-black tree is a binary tree that satisfies the following red-black properties:

  1. Every node is either red or black

  2. The root is black

  3. Every leaf(NIL) is black

  4. If a node is red, then both its children are black

  5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes

First of all, it says a red-black tree is a binary tree. Why didn't they say a red-black tree is a binary search tree. I thought the whole purpose of a red-black tree is to maintain the balance in a search tree to insure logN operations. Second, why is the leaf in a red-black tree the NIL?

In regular binary trees, we're used to this:

               4
         5            7
    3        2     Nil Nil
 Nil Nil  Nil Nil

In this case, 3, 2, and 7 are the leaves. Why are the leaves depicted as the Nil's in CLRS?

Upvotes: 1

Views: 1541

Answers (1)

Óscar López
Óscar López

Reputation: 236114

In the book, they refer to a red-black tree as a binary search tree, it's right at the beginning of the chapter.

Also in the chapter, they indicate that nodes labeled as nilare actual nodes (called sentinels), with the same fields as an ordinary node but with a color field with fixed value "black" (the other fields can be set to arbitrary values); these nodes always appear as leafs in the tree. So it's different from the usual BST where a leaf is a node whose left subtree and right subtree are both nil.

Upvotes: 1

Related Questions