Data Structures Interview Questions
Pg : 1 , 2,
3, 4,
5, 6,
7, 8,
9, 10,
11, 12,
13, 14
RED BLACK TREE
A red–black tree is a binary search tree where
each node has a color attribute, the value of which is either red or
black. In addition to the ordinary requirements imposed on binary search
trees, the following requirements apply to red–black trees:
 A node is either red or black.
 The root is black. All leaves are the same
color as the root.
 Both children of every red node are black.
 Every simple path from
a given node to any of its descendant leaves contains the same
number of black nodes.
 Redblack trees are binary search trees with
each node colored red or black and satisfying the following
properties:
 Root property: The root is black.
 External property: All external nodes are
black.
 Internal property: The children of red nodes
are black.
 Depth property: All external nodes have the
same black depth. The black depth is the number of black ancestors
minus one, or the number of black links from the root to the node.
 From a combinatorial point of view, a
redblack tree is an extended binary tree (every node has two
children or is a leaf) which satisfies the following properties.
 Every node is colored either red or black.
 Every leaf node is colored black.
 If a node is red, then both of its children
are black.
 Every path from the root to a leaf contains
the same number of black nodes. This number is called the
blackheight of the tree.


