recategorized by
3,704 views
3 votes
3 votes

Which one of the following property is correct for a red-black tree?

  1. Every simple path from anode to a descendant leaf contains the same number of black nodes.
  2. If a node is red, then one children is red and another is black.
  3. If a node is red, then both its children are red.
  4. Every leaf node (sentinel node) is red.
recategorized by

2 Answers

5 votes
5 votes
  • Every node is either red or black.
  • The root and leaves are black.
  • If a node is red, then its parent is black.
  • All simple paths from any node x to a descendant leaf have the same number of black nodes = black-height(x )
  • There are no two adjacent red nodes (A red node cannot have a red parent or red child).

option A is correct.

3 votes
3 votes

option A

A red-black tree is a balanced binary search tree with the following properties:

  1. Every node is colored red or black.
  2. Every leaf is a NIL node, and is colored black.
  3. If a node is red, then both its children are black.
  4. Every simple path from a node to a descendant leaf contains the same number of black nodes.
Answer:

Related questions

3 votes
3 votes
2 answers
1
gatecse asked Dec 17, 2017
1,216 views
The $in$-$order$ and $pre$-$order$ traversal of a binary tree are $\text{d b e a f c g}$ and $\text{a b d e c f g}$ respectively.The $post$-$order$ traversal of a binary ...
2 votes
2 votes
2 answers
2
gatecse asked Dec 17, 2017
1,233 views
A strictly binary tree with $10$ leavescannot have more than $19$ nodeshas exactly $19$ nodeshas exactly $17$ nodeshas exactly $20$ nodes
1 votes
1 votes
1 answer
3
gatecse asked Dec 17, 2017
870 views
The minimum number of stacks needed to implement a queue is$3$$1$$2$$4$
1 votes
1 votes
1 answer
4