CS251: Week of March 8th

  1. (2-4) Trees
  2. Red-Black Trees

2-23-04: (2-4) Trees

I. Characteristics of (2-4) Trees
  • Each node can have up to 4 children, and at most 3 keys
  • Searchable keys are matched to each piece of data, and used to order the tree
  • All children must have same depth, or tree is unbalanced

II. Operations of a (2-4) Tree

A. Search

  1. Start from root
  2. If key being searched ("searchKey") < first key in the current node (K[first]), descend into the leftmost child
  3. If searchKey > K[last], descend into rightmost child
  4. Otherwise, compare with remaining keys, descending as appropriate
  5. Once descended to node in lower level, check keys for a match
  6. If no match, repeat 2-5

B. Insert

  1. Insert key at lowest available node
  2. Nodes with 1-2 keys will just receive a new key
  3. 3-key Nodes must be split to accept a new key:
    • Considering all 4 key values, move one of the middle keys (#2 or #3, arbitrarily) up to the parent node
    • Repeat upwards if this causes parent to have 4 keys
  4. If root overflows (has > 3 keys), split root into 3 nodes, and create 2 levels (one parent, two children)

    Time complexity:

  • Searching for location to insert: O(log n)
  • Balancing tree (worst case): O(log n)
  • Splitting root & creating new level, if necessary: O(1)
  • Total insertion operation: O(log n + log n + 1) = O(log n)

C. Delete

Deletion consists of fusing nodes, if necessary

  1. If key is in leaf node with > 1 key, just remove the key to be deleted
  2. If key is in an internal node:
    • Find, using In-Order traversal, the key that precedes the one to be removed
    • Swap this replacement key upwards, and remove it from its old location
  3. If key is in a leaf node with 1 key:
    • Rotate keys: pull one key from parent down into leaf
    • Pull a key to the parent as replacement, from one of the other children
  4. If key is in a leaf node with 1 key & all siblings have only 1 key:
    • Pull a key down from the parent, and fuse together the leaves that were on either side of this parent key
    • If the parent had only one key, the fusion process will continue upward

Back to Top

2-25-04: Red-Black Trees

 I. Properties of Red-Black Trees

Red-Black Trees adhere to 2 main conditions:

  • There can be no 2 consecutive Red edges
  • The number of black nodes from the root to each leaf must be the same

II. Insertion

There are 3 possible cases for insertion into a Red-Black Tree:

A. Case 1
No Conflicts

  • Leaf nodes have empty children; the edges connecting these empty children are always black
  • A new node is always added with a red edge
  • If a new node is added with a red edge, and its parent has a black edge, there is no conflict

B. Case 2
Two consecutive Red Edges -- Sibing Node of first Red Edge is BLACK

Reorganize Nodes

  • Find X,Y,Z:
  • Z = Parent node before the 2 consecutive Red edges
  • Y = Node between both Red edges (parent edge & child edge both red)
  • X = Child node after the 2 red edges
  • Find A,B,C:
  • Use In-Order traversal methodology to determine which nodes (of X/Y/Z) will be re-labelled A,B,&C.

Rearrange Nodes

  • Reconnect B with Black edge
  • Connect A & C as B's children with Red edges
  • Have A & C's children connected with Black edges

C. Case 3
Two consecutive Red Edges -- Sibing Node of first Red Edge is RED

Recolor Edges

  • Assume that the node owning the first Red edge is labelled N
  • Reset the Red edge of N's sibling as Black
  • Also, recolor N's Red edge itself as Black
  • Recolor the incoming edge of N's parent as Red

II. Deletion

There is never a conflict when deleting leaf nodes with red edges...
If the node to delete is not a leaf, we must substitute a value from lower in the tree -- the value is determined by In-Order traversal (whichever value directly precedes the one to be removed)

A. Case 1
Leaf node with Red connection -- No conflicts; just remove

B. Case 2
Internal Node

  • Find In-Order predecessor & substitute
  • Remove node of the predecessor that was swapped in

B. Case 3
Leaf node with Black connection

  • Remove node as normal, but mark the connecting edge as "Double Black"
  • Rectify the Double Black (DB) situation, as in the following cases:


  • DOUBLE BLACK Case 1:

    • Sibling to DB edge is BLACK, with 1-2 RED children
    • Order & Rotate
    • Define Nodes X,Y,Z:
    • Z = Parent of DB edge
    • Y = Sibling to DB edge
    • X = One of the Red children of Y
    • Determine Nodes A,B,C by traversing X,Y,Z In-Order
    • Re-Organize A,B,C as usual

  • DOUBLE BLACK Case 2:

    • Sibling to DB edge is BLACK, with 2 BLACK children
    • Recolor
    • Add a Black edge to the connecting edge of DB parent (making this DB, if necessary)
    • Make connecting edge of DB sibling Red
    • Continue upward, if another DB situation was created

  • DOUBLE BLACK Case 3:

    • Sibling to DB edge is RED
    • Shift
    • Move the sibling of the DB edge up a level (connect it between the node above the DB's parent and DB's parent)
    • A new sibling will now be connected as the sibling to the DB edge, and it should have a Black edge.
    • Handle the new situation (Case 1 or 2), as above
 --- Diagrams to Come ---

Back to Top
Written by JJHW for Purdue CS251
Revised: 03/30/04.