Buy GNU books!
|[ < ]||[ > ]||[ << ]||[ Up ]||[ >> ]||[Top]||[Contents]||[Index]||[ ? ]|
The steps for insertion into a red-black tree are similar to those for insertion into an AVL tree:
Red-black node colors don't need to be updated in the way that AVL balance factors do, so there is no separate step for updating colors.
Here's the outline of the function, expressed as code:
struct rb_node *pa[RB_MAX_HEIGHT]; /* Nodes on stack. */ unsigned char da[RB_MAX_HEIGHT]; /* Directions moved from stack nodes. */ int k; /* Stack height. */ struct rb_node *p; /* Traverses tree looking for insertion point. */ struct rb_node *n; /* Newly inserted node. */ assert (tree != NULL && item != NULL);
See also: [ Cormen 1990], section 14.3; [ Sedgewick 1998], program 13.6.
7.4.1 Step 1: Search 7.4.2 Step 2: Insert 7.4.3 Step 3: Rebalance 7.4.4 Symmetric Case 7.4.5 Aside: Initial Black Insertion
|webmaster donations bookstore||delorie software privacy|
|Copyright © 2003 by The Free Software Foundation||Updated Jun 2003|