A redâ€“black tree is a data structure which is a type of self-balancing binary search tree.

__RED-BLACK
TREES__

A
redâ€“black tree is a data
structure which is a
type of self-balancing binary
search tree.

Balance
is preserved by painting each node of the tree with one of two colors
(typically called 'red' and 'black') in a way that satisfies certain
properties, which collectively constrain how unbalanced the tree can become in
the worst case. When the tree is modified, the new tree is subsequently
rearranged and repainted to restore the coloring properties. The properties are
designed in such a way that this rearranging and recoloring can be performed
efficiently.

A binary
search tree is a red-black tree if:

1. Every
node is either red or black

2. Every
leaf (nil) is 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

Black-height
of a node x, bh(x), is the number of black nodes on any path from x to a leaf,
not counting x

**Inserting in Red-Black Tree**

Â·
Color the node Red

Â·
Insert as in a regular BST

Â·
If have parent is red

__Case 1__

Â·
x is node of interest, x's uncle is Red

Â· Decrease x's black height by one

__Case 2__

Â·
x's uncle is Black, x is a Right child

Â·
Transform to case 3

__Case 3__

Â·
x's uncle is Black, x is a Left child

Â·
Terminal case, tree is Red-Black tree

Â·
Insertion takes O(lg(n)) time

Â·
Requires at most two rotations

__Example:__

**Deleting in a Red-Black Tree**

Â·
Find node to delete

Â·
Delete node as in a regular BST

Â·
Node to be deleted will have at most one child

Â·
If we delete a Red node tree still is a Red-Black
tree

Â·
Assume we delete a black node

Â·
Let x be the child of deleted node

Â·
If x is red, color it black and stop

Â·
If x is black mark it double black and apply the
following:

__Case 1__

Â·
x's sibling is red

Â·
x stays at same black height. Transforms to case 2b
then terminates.

__Case 2a__

Â·
x's sibling is black

Â·
x's parent is black

Â·
Decreases x black height by one

__Case 2b__

Â·
x's sibling is black

Â·
x's parent is red

Terminal
case, tree is Red-Black treep

__Case 3__

Â·
x's sibling is black

Â·
x's parent is either

Â·
x's sibling's left child is red

Â·
x's sibling's right child is black

Â· x stays at same black height

Â·
Transforms to case 4

__Case 4__

Â·
x's sibling is black

Â·
x's parent is either

Â·
x's sibling's left child is either

Â·
x's sibling's right child is red

Â·
Terminal case, tree is Red-Black tree.

Â·
Delete time is O(lg(n)).

Â·
At most three rotations are done.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Programming and Data structures : Advanced Non-Linear Data Structures : Redâ€“black tree |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright Â© 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.