Can We Draw A Reb Black Tree With With 7 Black Nodes And 10 Red Nodes

Data Structures and Algorithms

8.two Red-Blackness Trees

A red-black tree is a binary search tree with one extra aspect for each node: the colour, which is either red or black. Nosotros also demand to go along rail of the parent of each node, and so that a scarlet-blackness tree's node structure would be:

        struct t_red_black_node {     enum { reddish, black } color;     void *item;     struct t_red_black_node *left,                      *right,                      *parent;     }

For the purpose of this discussion, the NULL nodes which cease the tree are considered to be the leaves and are coloured black.

Definition of a ruby-red-black tree

A red-black tree is a binary search tree which has the following red-black backdrop:

Every node is either red or blackness.
Every leafage (NULL) is black.
If a node is ruddy, then both its children are black.
Every simple path from a node to a descendant leaf contains the same number of black nodes.

implies that on whatsoever path from the root to a leaf, ruby-red nodes must non be adjacent.
Withal, whatsoever number of black nodes may appear in a sequence.

	A basic ruby-red-black tree
	Basic red-black tree with the sentinel nodes added. Implementations of the red-black tree algorithms volition usually include the sentinel nodes equally a convenient means of flagging that you have reached a leaf node. They are the Nix black nodes of property 2.

The number of blackness nodes on any path from, but not including, a node 10 to a leafage is called the black-height of a node, denoted bh(x). We can prove the following lemma:

Lemma

A red-blackness tree with n internal nodes has summit at most 2log(due north+one).
(For a proof, see Cormen, p 264)

This demonstrates why the red-black tree is a expert search tree: it tin can always be searched in O(log n) time.

As with heaps, additions and deletions from red-black trees destroy the red-black property, so we demand to restore information technology. To do this we need to await at some operations on cherry-blackness copse.

Rotations

A rotation is a local performance in a search tree that preserves in-order traversal key ordering.

Note that in both trees, an in-order traversal yields:

A ten B y C

The left_rotate operation may be encoded:

left_rotate( Tree T, node 10 ) {     node y;     y = x->right;     /* Turn y's left sub-tree into ten's right sub-tree */     x->right = y->left;     if ( y->left != NULL )         y->left->parent = 10;     /* y'southward new parent was x's parent */     y->parent = x->parent;     /* Set the parent to point to y instead of 10 */     /* First run into whether we're at the root */     if ( x->parent == Cipher ) T->root = y;     else         if ( 10 == (x->parent)->left )             /* x was on the left of its parent */             x->parent->left = y;         else             /* x must have been on the right */             10->parent->right = y;     /* Finally, put x on y'southward left */     y->left = x;     x->parent = y;     }

Insertion

Insertion is somewhat circuitous and involves a number of cases. Notation that we start by inserting the new node, ten, in the tree but every bit we would for any other binary tree, using the tree_insert role. This new node is labelled red, and possibly destroys the red-black property. The main loop moves upwards the tree, restoring the red-blackness property.

rb_insert( Tree T, node x ) {     /* Insert in the tree in the usual way */     tree_insert( T, x );     /* Now restore the red-black property */     ten->color = red;     while ( (ten != T->root) && (x->parent->color == red) ) {        if ( ten->parent == x->parent->parent->left ) {            /* If x'south parent is a left, y is x'southward right 'uncle' */            y = x->parent->parent->right;            if ( y->colour == red ) {                /* case ane - change the colours */                ten->parent->color = blackness;                y->colour = black;                ten->parent->parent->color = red;                /* Move 10 up the tree */                ten = x->parent->parent;                }            else {                /* y is a black node */                if ( x == x->parent->right ) {                    /* and x is to the correct */                     /* example ii - motility x up and rotate */                    x = x->parent;                    left_rotate( T, x );                    }                /* case 3 */                x->parent->color = blackness;                x->parent->parent->colour = red;                right_rotate( T, x->parent->parent );                }            }        else {            /* repeat the "if" office with right and left               exchanged */            }        }     /* Colour the root black */     T->root->colour = black;     }

Hither's an example of the insertion operation.

Animation

Cherry-red-Black Tree Animation
This animation was written by Linda Luo, Mervyn Ng, Anita Lee, John Morris and Woi Ang.

Please e-mail comments to:

Examination of the lawmaking reveals only one loop. In that loop, the node at the root of the sub-tree whose reddish-black property nosotros are trying to restore, x, may exist moved up the tree at least i level in each iteration of the loop. Since the tree originally has O(log due north) top, there are O(log n) iterations. The tree_insert routine also has O(log northward) complexity, so overall the rb_insert routine also has O(log northward) complication.

Key terms

Red-black trees: Trees which remain counterbalanced - and thus guarantee O(logn) search times - in a dynamic surround. Or more importantly, since any tree can be re-balanced - but at considerable cost - can exist re-balanced in O(logn) time.