rslt ← {larg) (op ##.redblack) rarg                 ⍝ Red-black trees.

     T∆ ← T ∪ avl (key val)     ⍝ tree ⍺ with key=val ⍵.
     T∆ ← T ~ avl key           ⍝ tree ⍺ without key ⍵.
     T∆ ← T ⍎ avl key           ⍝ value for key ⍵ in tree ⍺.
    fmt ←   ⍕ avl T             ⍝ format of tree ⍵.
    vec ←   ∊ avl T             ⍝ enlist of tree ⍵.
    chk ←   ? avl T             ⍝ stats for tree ⍵: ok size mean_depth height.

See →BST←

In  contrast  with the notes for →sbst←, →splay← and →avl←, when discussing red-
blacktrees, it is convenient to show null subtrees (nulls) explicitly.

    AVL/Splay diagram           Equivalent Red-black diagram
    -----------------           ----------------------------
            E                             E
           / \                           / \
          /   \                         /   \
         /     \                       /     \
        B       F                     B       F
       / \                           / \     / \
      /   \                         /   \   ∘   ∘
     /     \                       /     \
    A       C                     A       C
             \                   / \     / \
              D                 ∘   ∘   ∘   D
                                           / \
                                          ∘   ∘

Defn:  A  red-black tree is a binary search tree (→BST←) with the properties (or
"restrictions" or "rules"):

[C] Every node is coloured either <red> or [black],
[I] Only internal nodes (other than the root or nulls) may be <red>,
[R] Both children of a <red> node are [black],
[B] The path from a node to any leaf contains the same number of [black] nodes.

Red  nodes  are  annotated <N> and black nodes [N]. The following tree satisfies
rules C-B:
               ·
              [E]
              / \
             /   \
            /     \
          <B>     [F]
          / \     / \
         /   \  [∘] [∘]
        /     \
      [A]     [C]
      / \     / \
    [∘] [∘] [∘] <D>
                / \
              [∘] [∘]

Rules  R  and  B  keep the tree in reasonable balance; to construct a worst case
(greatest height/size ratio), we could take an all-black (and therefore, by rule
B, perfectly balanced) tree and increase its height by injecting red nodes (only
alternately by rule R) all down one side.
                 ·
                [b]
                / \
               /   \                Height 4
              /     \               Size   6 (excluding nulls).
             /       \
            /         \
           /           \            In general, a red-black tree with ⍵ non-
          /             \           null nodes has height at most 2×2⍟⍵+1.
        [b]             <r>
        / \             / \
       /   \           /   \
      /     \         /     \
    [∘]     [∘]     [b]     [b]
                    / \     / \
                  [∘] [∘] [∘] <r>
                              / \
                            [∘] [∘]

Red-black  trees are implemented here using a recursive triple with 0 represent-
ing the null tree:

    (key val) red (lft rgt)

where:

    key : numeric scalar or character vector
    val : any array value
    red : colour of node 0=black, 1=red *
    lft : left subtree or 0 (null).
    rgt : right subtree or 0 (null)

* The  choice  of  0  for black means that a structure assignment of a null node
  shows it as black:

        inf col(lft rgt)←⍺      ⍝ (possibly null) node colour and subs.

Insertion
---------
Three generations of node are of interest:

    G grandparent
    P parent
    C child

New node C is inserted in the normal fashion (see →BST←) and coloured red <C>.

There are 4 cases: [ins#] [insB] [insRR] [insRB].
Case [insRB] has 2 subcases: [insRBo] [insRBi].

If <C> is the root: recolour it [black].                                [ins#]
·
        <C>     →   [C]                             <C> → [C]
        / \         / \
      [∘] [∘]     [∘] [∘]

Otherwise, <C> has a parent:

If <C>'s parent [P] is black: no change.                                [insB]
·
        [P]     →       [P]                         (no change)
        /               /
      <C>             <C>
      / \             / \
    [∘] [∘]         [∘] [∘]

Otherwise, <C>'s parent <P> is red.                                     [insR]

This  means  that, from rule I, <P> cannot be the root and so must itself have a
parent G, which is <C>'s grandparent.
·
           G
          /
        <P>
        /
      <C>
      / \
    [∘] [∘]

Rule [R] ensures that [G] must be black as its child <P> is red.
·
          [G]
          /
        <P>
        /
      <C>
      / \
    [∘] [∘]

Call <P>'s possibly null sibling U (C's Uncle).
·
          [G]
          / \
        <P>  U
        /
      <C>
      / \
    [∘] [∘]
                                        ¯
If <U> is red, change the colours of G, P and U.                        [insRR]
·
          [G]       →       <G>                     [G] → <G>
          / \               / \                     <P> → [P]
        <P> <U>           [P] [U]                   <U> → [U]
        / \               / \
      <C>  S            <C>  S
      / \               / \
    [∘] [∘]           [∘] [∘]

    In this case, <G> becomes the new <red> node and is
    handled  recursively  as  if _it_ had been inserted.
    In  other  words, the algorithm next looks at <G>'s
    parent  and  grandparent  to  determine  if further
    balancing is necessary, and so on.

Otherwise, [U] is black.                                                [inaRB]

If <C> is <P>'s outer child, swap colours and rotate G-P.               [insRBo]
                ¯¯¯¯¯
          [G]       →       [P]                     [G] → <G>
          / \               / \                     <P> → [P]
        <P> [U]           <C> <G>                       ⌽ G-P
        / \                   / \
      <C> [S]               [S] [U]

Otherwise <C> is inner child, rotate P-C and proceed as in [insRBo].    [insRBi]
                 ¯¯¯¯¯
          [G]       →       [G]                     ⌽ P-C
          / \               / \                       [insRBo]
        <P> [U]           <C> [U]
        / \               / \
       S  <C>           <P>  q
          / \           / \
         p   q         S   p

All possibilities are covered:
                                                          [ins]
    C is the root:          [ins#]                       / \
    C's parent black:       [insB]                 [insR]   [insB]
    C's uncle red:          [insRR]                   / \
    C is P's inner child:   [insRBi]           [insRR]   [insRB]
    Otherwise:              [insRBo]                     / \
                                                 [insRBi]   [insRBo]
Removal
-------
To remove a node from a red-black tree, there are three phases:

[loc] Locate X, the node to be deleted.
[rep] Repaint the removed node's child.
[bal] Rebalance the tree by absorbing any "double-black" nodes.

[loc]----------------------------------------------------------------------[loc]

Search the tree for the node to be deleted in the normal way (→BST←):

    If the node is a leaf (only null subtrees),                         [loc0]
        replace it with a null:
·
           X    =>      [∘]
          / \
        [∘] [∘]

    Otherwise, if the node has only a single (non-null) child,          [loc1]
        replace the node with its child:
·
            X   =>  C               X   =>  C
           / \                     / \
         [∘]  C                   C  [∘]

    Otherwise (the node has two non-null children),                     [loc2]
        exchange the node key=value with that of its right (say) successor node,
        which  by  definition  does not have a left (say) child, then remove the
        successor as in [loc0] or [loc1] above:

             target node X:      X  ~ X     =>     X∆ ~ X    =>     X∆
                                / \               / \              / \
                               A   B             A   B            A   B
                                  / \               /                /
                                ...               ...              ...
                                /                 /                /
    X's right successor:       X∆                X                X  ~ X
                              / \               / \              / \
                            [∘]  C            [∘]  C           [∘]  C

All possibilities are covered:

    Both subtrees null:     [loc0]
    One subtree null:       [loc1]
    Neither sutree null:    [loc2]

On deletion of X, it may be necessary to repaint X's child C:

[rep]----------------------------------------------------------------------[rep]

Repaint the removed node's child.

If X was red, no more need be done:                                     [repR]
·
        <X>     =>      [C]
          \
          [C]

Otherwise, if [X]'s child C is red, paint it black:                     [repBR]
·
        [X]     =>      [C]
          \
          <C>

Otherwise, repaint [C] double-black.                                    [repBB]
·
        [X]     =>      [[C]]
          \
          [C]

In all cases, if we count double-black as 2, rule B continues to hold.

All possibilities are covered:
                                                      [rep]
    X red:      [repR]                               / \
    C red:      [repBR]                        [repR]   [repB]
    C black:    [repBB]                                 / \
                                                 [repBR]   [repBB]
(
    In some treatments,  the double-black node is described as a separate "black
    token", which is associated with the node. It amounts to the same thing:
·
        [X]     =>      [[C]]       <= double-black node.
          \
          [C]


        [X]     =>      [C] []      <= black node with associated black token.
          \
          [C]

    In a particular implementation, the choice probably depends on how a null is
    represented.  As  we use a scalar 0 for null, there is no structure in which
    to  keep the double-blackness property, so a separate black token is prefer-
    able.  However, the double brackets look more pleasing in diagrams, where we
    will continue to use them ...
)

[bal]----------------------------------------------------------------------[bal]

Rebalance the tree by absorbing any double-black nodes [[N]].

Notice how each of the transformations below preserves rules [C] [I] [R] & [B].
In particular:

    The colour of the root of the subtree remains unchanged for rule R.

    Apart from the root case [bal#], the  number of black nodes (square brack-
    ets) from the root of the subtree downwards remains unchanged for rule B.

In  the  following diagrams, (N) means that the colour of N is immaterial to the
transformation.

If [[N]] is the root, repaint it black:                                 [bal#]
·
        [[N]]   =>  [N]
         / \        / \

    (this maintains rule B by decrementing the black count on every path).

Otherwise, N has a parent and a (possibly null) sibling.

If N's sibling S is red,
    Swap the colours of P and S and rotate P left.                      [balR]
    N's new sibling is black, so proceed from [balB].
·
        [P]         =>     [S]                      [P] → <P>
        / \                / \                      <S> → [S]
       /   \              /   \                         ⌽ P-S
    [[N]]  <S>          <P>   [f]                         [balB]
           / \          / \
          /   \        /   \
        [n]   [f]   [[N]]  [n]

    Note that, after the transformation, [[N]]'s parent <P> is red.
    This means that [balB] will, at worst,  produce a singly-black
    parent and so complete the rebalance. In particular, it is not
    necessary  to check for double-blackness on return of [balR]'s
    call to [balB].

Otherwise N's sibling is black.                                         [balB]

If both nephews are black,
    paint sibling S red and blacken parent P.                           [balBbb]
·
        (P)     =>    [(P)]                         (P) → [(P)] *
        / \            / \                        [[N]] →  [N]
       /   \          /   \                         [S] →  <S>
    [[N]]  [S]      [N]  <S>
           / \           / \
         [n] [f]       [n] [f]

    * (P) => [(P)] means "blacken",
      red goes to black      <P> → [P]
      black to double-black  [P] → [[P]]

Otherwise, if the far nephew f is red,
    Move N's extra brackets to the far nephew and rotate P-S.           [balB_r]
·
        (P)         =>       (S)                    (S) → (P) *
        / \                  / \                    (P) → [P]
       /   \                /   \                 [[N]] → [N]
      /     \              /     \                  <f> → [f]
   [[N]]    [S]          [P]     [f]                    ⌽ P-S
             / \         / \     / \
           (n) <f>     [N] (n) [a] [b]
·   ·   ·      / \
             [a] [b]

    * (P) → (S) means that P's colour is transferred to S.

Otherwise, the far nephew f is black (and the near one must be red),
    Swap the colours of S and l and rotate S right.                     [balBrb]
    Then proceed as in [balB_r].
·
        (P)         =>     (P)                      [S] → <S>
        / \                / \                      <n> → [n]
       /   \              /   \                         ⌽ S-n
    [[N]]  [S]         [[N]]  [n]                         [balB_r]
           / \                / \
         <n> [f]            [a] <S>
         / \                    / \
       [a] [b]                [b] [f]

All possibilities are covered:                            [bal]
                                                          / \
    [[N]] is the root:  [bal#]                      [balR]   [balB]
    N's sibling red:    [balR]      [1]                      / \
    Both nephews black: [balBbb]    [2]              [balB_r]   [balB_b]
    Far nephew red:     [balB_r]                                / \
    Otherwise           [balBrb]                        [balBrb]   [balBbb]

[1] If N has a parent, it must have a (possibly null) sibling.

[2] As N is double-black,  its parent must have had at least two black
    nodes in each subtree (rule B). Therefore, N's sibling is not null
    and so has two (possibly null) nephews.

Technical notes:

Insertion  and removal require information about the node's parent, grandparent,
uncle  or  nephews. In a language with pointers, we might arrange that each node
include  a  pointer  to  its  parent,  although  this would increase complexity.
Similarly,  we  could use namespaces to implement nodes and include a ref to the
parent space.

We  choose  instead, to have the subject node's (grand) parent do the processing
by returning a path (vector of directions) to the child in question. The (grand)
parent  can then check the length of this path to see if it must accommodate any
changes.  Any node that decides that no further attention is required, returns a
path  that is long enough to be ignored by all ancestors. (0 0 0) will always do
the trick.

References:

[1] http://en.wikipedia.org/wiki/Red-black_tree
[2] Internet: search for "red black tree"
[3] "Paint It Black/Long Long While", Jagger/Richards, Decca F12395 (1966).

Examples:

⍝ derive red-black tree functions:

    put ← ∪ redblack            ⍝ tree ⍺ with key=val ⍵.
    rem ← ~ redblack            ⍝ tree ⍺ without key ⍵.
    get ← ⍎ redblack            ⍝ value for key ⍺ from tree ⍵.
    fmt ← ⍕ redblack            ⍝ format of tree ⍵.
    vec ← ~ redblack            ⍝ enlist of tree ⍵.
    chk ← ? redblack            ⍝ stats for tree ⍵: ok size mean_depth height.

    tt ← 0                      ⍝ null tree

    tt ← tt put 'one' 1         ⍝ single node tree: (key val) red (lft rgt)

    fmt tt                      ⍝ root is [black]
       ┌[∘]
[one=1]┤
       └[∘]

    tt ← tt put 'two'   2       ⍝ insert second node

    fmt tt                      ⍝ new node is <red>
       ┌[∘]
[one=1]┤
       │       ┌[∘]
       └<two=2>┤
               └[∘]

    tt ← tt put 'three' 3       ⍝ insert third node.

    fmt tt
                 ┌[∘]
         ┌<one=1>┤
         │       └[∘]
[three=3]┤
         │       ┌[∘]
         └<two=2>┤
                 └[∘]

    tt ← tt put foldl ('four' 4) ('five' 5) ('six' 6) ('seven' 7)

    fmt tt
                           ┌[∘]
                  ┌[five=5]┤
                  │        └[∘]
         ┌<four=4>┤
         │        │                 ┌[∘]
         │        │         ┌<one=1>┤
         │        │         │       └[∘]
         │        └[seven=7]┤
         │                  │       ┌[∘]
         │                  └<six=6>┤
         │                          └[∘]
[three=3]┤
         │       ┌[∘]
         └[two=2]┤
                 └[∘]

    chk tt                      ⍝ tree stats.
1 7 2 4

    ⍪ fmt¨ 0 put foldl¨ 1↓¨,\0,⍳6               ⍝ successive inserts 1 2 .. 6
┌───────────────────────────┐
│[∘]                        │
├───────────────────────────┤
│     ┌[∘]                  │
│[1=1]┤                     │
│     └[∘]                  │
├───────────────────────────┤
│     ┌[∘]                  │
│[1=1]┤                     │
│     │     ┌[∘]            │
│     └<2=2>┤               │
│           └[∘]            │
├───────────────────────────┤
│           ┌[∘]            │
│     ┌<1=1>┤               │
│     │     └[∘]            │
│[2=2]┤                     │
│     │     ┌[∘]            │
│     └<3=3>┤               │
│           └[∘]            │
├───────────────────────────┤
│           ┌[∘]            │
│     ┌[1=1]┤               │
│     │     └[∘]            │
│[2=2]┤                     │
│     │     ┌[∘]            │
│     └[3=3]┤               │
│           │     ┌[∘]      │
│           └<4=4>┤         │
│                 └[∘]      │
├───────────────────────────┤
│           ┌[∘]            │
│     ┌[1=1]┤               │
│     │     └[∘]            │
│[2=2]┤                     │
│     │           ┌[∘]      │
│     │     ┌<3=3>┤         │
│     │     │     └[∘]      │
│     └[4=4]┤               │
│           │     ┌[∘]      │
│           └<5=5>┤         │
│                 └[∘]      │
├───────────────────────────┤
│           ┌[∘]            │
│     ┌[1=1]┤               │
│     │     └[∘]            │
│[2=2]┤                     │
│     │           ┌[∘]      │
│     │     ┌[3=3]┤         │
│     │     │     └[∘]      │
│     └<4=4>┤               │
│           │     ┌[∘]      │
│           └[5=5]┤         │
│                 │     ┌[∘]│
│                 └<6=6>┤   │
│                       └[∘]│
└───────────────────────────┘

    tt ← 0 put foldl ⍳6                         ⍝ 6 nodes, ascending order.

    ⍪ fmt¨(⊂tt)rem foldl¨1↓¨,\0,⍳6              ⍝ successive removals 1 2 .. 6
┌───────────────────────────┐
│           ┌[∘]            │
│     ┌[1=1]┤               │
│     │     └[∘]            │
│[2=2]┤                     │
│     │           ┌[∘]      │
│     │     ┌[3=3]┤         │
│     │     │     └[∘]      │
│     └<4=4>┤               │
│           │     ┌[∘]      │
│           └[5=5]┤         │
│                 │     ┌[∘]│
│                 └<6=6>┤   │
│                       └[∘]│
├───────────────────────────┤
│           ┌[∘]            │
│     ┌[2=2]┤               │
│     │     │     ┌[∘]      │
│     │     └<3=3>┤         │
│     │           └[∘]      │
│[4=4]┤                     │
│     │     ┌[∘]            │
│     └[5=5]┤               │
│           │     ┌[∘]      │
│           └<6=6>┤         │
│                 └[∘]      │
├───────────────────────────┤
│           ┌[∘]            │
│     ┌[3=3]┤               │
│     │     └[∘]            │
│[4=4]┤                     │
│     │     ┌[∘]            │
│     └[5=5]┤               │
│           │     ┌[∘]      │
│           └<6=6>┤         │
│                 └[∘]      │
├───────────────────────────┤
│           ┌[∘]            │
│     ┌[4=4]┤               │
│     │     └[∘]            │
│[5=5]┤                     │
│     │     ┌[∘]            │
│     └[6=6]┤               │
│           └[∘]            │
├───────────────────────────┤
│     ┌[∘]                  │
│[5=5]┤                     │
│     │     ┌[∘]            │
│     └<6=6>┤               │
│           └[∘]            │
├───────────────────────────┤
│     ┌[∘]                  │
│[6=6]┤                     │
│     └[∘]                  │
├───────────────────────────┤
│[∘]                        │
└───────────────────────────┘

See also: BST sbst avl splay foldl alists

Back to: contents

Back to: Workspaces