Red-Black Trees: Insertion

Source

This is a post on inserting nodes into a tree. It is part of a series of posts starting with this post.

Insertion

Because we need to maintain the Red-Black Properties inserting a node into a Red-Black Tree is similar to inserting a node into a Binary Search Tree, but it involves a second function that restores the Red-Black properties if needed.

The Inserter

class Inserter:
    """Insert a node into the tree

    Args:
      tree: Red-Black-Tree to insert nodes into
    """
    def __init__(self, tree: rb_tree.RedBlackTree) -> None:
        self._tree = None
        self.tree = tree
        self._rotate: Rotator = None
        return

The Tree Properties

@property
def tree(self) -> rb_tree.RedBlackTree:
    """The tree we're inserting nodes into"""
    return self._tree

@tree.setter
def tree(self, sapling: rb_tree.RedBlackTree) -> None:
    """stores the tree, resets other objects that used the prior tree"""
    self._tree = sapling
    self._rotate = None
    return

The Rotator

@property
def rotate(self) -> Rotator:
    """A rotator for inserts"""
    if self._rotate is None:
        self._rotate = Rotator(tree=self.tree)
    return self._rotate

Insert

The Pseudocode

\begin{algorithm}
\caption{RBInsert}
\begin{algorithmic}
\INPUT The Tree and the Node to insert
\PROCEDURE{RBInsert}{\textit{T}, \textit{z}}

\STATE \textit{y} $\gets$ \textit{T}.\textsc{NIL}
\STATE \textit{x} $\gets$ \textit{T}.root

\WHILE {\textit{x} $\neq$ \textit{T}.\textsc{NIL}}
  \STATE \textit{y} $\gets$ \textit{x}

  \IF {\textit{z}.key < \textit{x}.key}
    \STATE \textit{x} $\gets$ \textit{x}.left
  \ELSE
    \STATE \textit{x} $\gets$ \textit{x}.right
  \ENDIF
\ENDWHILE

\STATE \textit{z}.parent $\gets$ \textit{y}

\IF {\textit{y} = \textit{T}.\textsc{NIL}}
  \STATE \textit{T}.root $\gets$ \textit{z}
\ELIF {\textit{z}.key < \textit{y}.key}
  \STATE \textit{y}.left $\gets$ \textit{z}
\ELSE
  \STATE \textit{y}.right $\gets$ \textit{z}
\ENDIF

\STATE \textit{z}.left $\gets$ \textit{T}.\textsc{NIL}
\STATE \textit{z}.right $\gets$ \textit{T}.\textsc{NIL}
\STATE \textit{z}.color $\gets$ \textbf{RED}
\STATE \textsc{RBInsertFixup}(\textit{T}, \textit{z})

\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

Some Code

def insert(self, node: rb_tree.Node) -> None:
    """Insert the node into to the tree

    Args:
     node: node to insert into the tree
    """
    hunter = rb_tree.ROOT_PARENT
    hound = self.tree.root

    while hound is not rb_tree.LEAF:
        hunter = hound
        if node > hound:
            hound = hound.right
        else:
            hound = hound.left

    node.parent = hunter

    if hunter is rb_tree.ROOT_PARENT:
        self.tree.root = node
    node.left = rb_tree.LEAF
    node.right = rb_tree.LEAF
    node.color = rb_tree.Color.RED
    self.fixup(node)
    return

from expects import be, be_true, equal, expect
from bowling.data_structures.red_black_tree import tree
from bowling.data_structures.red_black_tree.arborist import Arborist
from bowling.data_structures.red_black_tree.forester import Forester

node = tree.Node(10)
node_5 = tree.Node(5)
node_15 = tree.Node(15)
node.left = node_5
node.right = node_15
rb_tree = tree.RedBlackTree()
arborist = Arborist(rb_tree)

# case: Root is NIL and new-node's parent is NIL
arborist.insert(node)
expect(node.parent).to(be(tree.NIL))
expect(rb_tree.root).to(be(node))

# case: Root isn't NIL
root = tree.Node(20)
node = tree.Node(10)
rb_tree = tree.RedBlackTree(root=root)
arborist.tree = rb_tree
arborist.insert(node)
expect(rb_tree.root).to(be(root))
expect(node.parent).to(be(root))
expect(root.left).to(be(node))

# root is less than inserted node
root = tree.Node(5)
node = tree.Node(11)
rb_tree = tree.RedBlackTree(root=root)
arborist.tree = rb_tree
arborist.insert(node)
expect(rb_tree.root).to(be(root))
expect(node.parent).to(be(root))
expect(root.right).to(be(node))

# in all cases
expect(node.left).to(be(tree.NIL))
expect(node.right).to(be(tree.NIL))
expect(node.is_red).to(be_true)

Insert Fixup

The Pseudocode

This is a separate function to restore the red-black properties (if we messed them up with the insert). It's mostly from CLRS but they used some kind of weird formatting that made it hard for me to tell what their first else conditional was supposed to contain so I'm using a slightly clearer version that I found at https://gcallah.github.io/algorithms/RedBlackTrees.html.

\begin{algorithm}
\caption{RBInsertFixup}
\begin{algorithmic}
\INPUT The Tree and the Node to insert
\PROCEDURE{RBInsertFixup}{\textit{T}, \textit{z}}

\WHILE {\textit{z.parent.color} = \textbf{RED} }
  \IF {\textit{z}.parent = \textit{z}.parent.parent.left}
    \STATE \textit{y} $\gets$ \textit{z}.parent.parent.right

    \IF {\textit{y}.color = \textbf{RED}}
      \STATE \textit{z}.parent.color $\gets$ \textbf{BLACK}
      \STATE \textit{y}.color $\gets$ \textbf{BLACK}
      \STATE \textit{z} $\gets$ \textit{z}.parent.parent
    \ELSE
      \IF {\textit{z} = \textit{z}.parent.right}
        \STATE \textit{z} $\gets$ \textit{z}.parent
        \STATE \textsc{LeftRotate}(\textit{T}, \textit{z})
      \ENDIF
      \STATE \textit{z}.parent.color $\gets$ \textbf{BLACK}
      \STATE \textit{z}.parent.parent.color $\gets$ \textbf{RED}
      \STATE \textsc{RightRotate}(\textit{T}, \textit{z})
    \ENDIF
    
  \ELSE
    \STATE Same as when the parent is left case but with left/right switched
  \ENDIF
  \STATE \textit{T}.root.color $\gets$ \textbf{BLACK}
\ENDWHILE

\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

The Implementation

  • One Side
    def fixup_side(self, node: rb_tree.Node, uncle: rb_tree.Node,
               swap_and_rotate: bool=True, left: bool=True) -> None:
    """Fixup either the left or the right sides

    Args:
     node: the node that we're fixing
     uncle: the node's parent's sibling
     swap_and_rotate: whether we need to do a swap and rotation
     left: if the node's parent is a left child
    """
    first_rotate = self.rotate.left if left else self.rotate.right
    final_rotate = self.rotate.right if left else self.rotate.left

    if uncle.is_red:
        node.parent.color = rb_tree.Color.BLACK
        node.parent.parent.color = rb_tree.Color.RED
        uncle.color = rb_tree.Color.BLACK
        node = node.parent.parent
    else:
        if swap_and_rotate:
            node = node.parent
            first_rotate(node)
        node.parent.color = rb_tree.Color.BLACK
        node.parent.parent.color = rb_tree.Color.RED

        final_rotate(node.parent.parent)
    return
  • Both Sides
    def fixup(self, node: rb_tree.Node) -> None:
    """Fix-up the red-black properties after an insert

    Args:
     node: the node that was just inserted
    """
    while node.parent.is_red:
        if node.parent.is_left:
            uncle = node.parent.parent.right
            self.fixup_side(node, uncle,
                            swap_and_rotate=node.is_right,
                            left=True)
        else:
            uncle = node.parent.parent.left
            self.fixup_side(node, uncle,
                            swap_and_rotate=node.is_left,
                            left=False)
    self.tree.root.color = rb_tree.Color.BLACK
    return

Some Testing

# the parent is black
root = tree.Node(10, color=tree.Color.RED)
parent = tree.Node(5, color=tree.Color.BLACK)
parent.parent = root
child = tree.Node(8, color=tree.Color.RED)
child.parent = parent
uncle = tree.Node(11, color=tree.Color.BLACK)
root.right = uncle
rb_tree = tree.RedBlackTree(root=root)
arborist.tree = rb_tree
forester = Forester(rb_tree, enforce_properties=True)

arborist.insert.fixup(child)

expect(root.color).to(be(tree.Color.BLACK))
expect(parent.color).to(be(tree.Color.BLACK))
expect(uncle.color).to(be(tree.Color.BLACK))
expect(child.color).to(be(tree.Color.RED))
expect(forester.height).to(equal(2))
expect(forester.black_height).to(equal(2))

# the parent is a RED left child and the uncle is red
root = tree.Node(10, color=tree.Color.BLACK)
parent = tree.Node(5, color=tree.Color.RED)
parent.parent = root
child = tree.Node(8, color=tree.Color.RED)
child.parent = parent
uncle = tree.Node(11, color=tree.Color.RED)
root.right = uncle
arborist.tree = tree.RedBlackTree(root=root)
forester = Forester(arborist.tree, enforce_properties=True)

expect(forester.black_height).to(equal(1))
arborist.insert.fixup(child)
expect(parent.is_black).to(be_true)
expect(uncle.is_black).to(be_true)
expect(forester.black_height).to(equal(2))

# the parent is a RED left child, the uncle is black, and the node is the left child
parent.color = tree.Color.RED
uncle.color = tree.Color.BLACK
child.color = tree.Color.RED
child.key = 2
parent.left = child
node_6 = tree.Node(6, tree.Color.BLACK)
parent.right = node_6
node_1 = tree.Node(1, tree.Color.BLACK)
child.left = node_1
node_3 = tree.Node(3, tree.Color.BLACK)
child.right = node_3

arborist.insert.fixup(child)

expect(arborist.tree.root).to(be(parent))
expect(parent.color).to(be(tree.Color.BLACK))
expect(parent.right).to(be(root))
expect(root.color).to(be(tree.Color.RED))
expect(child.left).to(be(node_1))
expect(child.right).to(be(node_3))
expect(root.left).to(be(node_6))
expect(root.right).to(be(uncle))
expect(forester.height).to(equal(2))
expect(forester.black_height).to(equal(2))

# the parent is a RED left child, the uncle is black, and the node is the right child
root = tree.Node(10, color=tree.Color.BLACK)
parent = tree.Node(5, color=tree.Color.RED)
uncle = tree.Node(11, color=tree.Color.BLACK)
child = tree.Node(8, color=tree.Color.RED)
parent.parent = root
uncle.parent = root

node_4 = tree.Node(4, color=tree.Color.BLACK)
parent.left = node_4
parent.right = child
node_7 = tree.Node(7, color=tree.Color.BLACK)
node_9 = tree.Node(9, color=tree.Color.BLACK)
child.left = node_7
child.right = node_9

arborist.tree = tree.RedBlackTree(root)
forester.tree = arborist.tree

arborist.insert.fixup(child)

expect(child).to(be(arborist.tree.root))
expect(child.color).to(be(tree.Color.BLACK))
expect(child.left).to(be(parent))
expect(child.right).to(be(root))
expect(parent.color).to(be(tree.Color.RED))
expect(root.color).to(be(tree.Color.RED))
expect(parent.left).to(be(node_4))
expect(parent.right).to(be(node_7))
expect(root.left).to(be(node_9))
expect(root.right).to(be(uncle))
expect(forester.height).to(equal(2))
expect(forester.black_height).to(equal(2))

The Call

This is just a thing to make it look more like a function than a class.

def __call__(self, node: rb_tree.Node) -> None:
    """Inserts the node into the tree

    this is an alias for the ``insert`` method

    Args:
     node: the node to insert 
    """
    return self.insert(node)

All Together Now

rb_tree = tree.RedBlackTree()
arborist = Arborist(rb_tree)
forester = Forester(rb_tree)
root = tree.Node(10)

arborist.insert(root)
expect(forester.height).to(equal(0))
expect(forester.black_height).to(equal(1))

node_5 = tree.Node(5)
arborist.insert(node_5)
expect(forester.height).to(equal(1))
expect(forester.black_height).to(equal(1))
expect(node_5.color).to(be(tree.Color.RED))

node_11 = tree.Node(11)
arborist.insert(node_11)
expect(forester.height).to(equal(1))
expect(forester.black_height).to(equal(1))
expect(node_11.color).to(be(tree.Color.RED))

node_6 = tree.Node(6)
arborist.insert(node_6)
expect(forester.height).to(equal(2))
expect(forester.black_height).to(equal(2))
expect(node_11.color).to(be(tree.Color.BLACK))
expect(node_5.color).to(be(tree.Color.BLACK))
expect(node_6.color).to(be(tree.Color.RED))

node_3 = tree.Node(3)
arborist.insert(node_3)
expect(node_3.color).to(be(tree.Color.RED))
expect(node_5.color).to(be(tree.Color.BLACK))
expect(forester.height).to(be(2))
expect(forester.black_height).to(be(2))

node_1 = tree.Node(1)
arborist.insert(node_1)
expect(forester.height).to(equal(3))
expect(forester.black_height).to(equal(2))
expect(node_1.color).to(be(tree.Color.RED))
expect(node_1.parent.color).to(be(tree.Color.BLACK))
expect(node_6.color).to(be(tree.Color.BLACK))
expect(node_5.color).to(be(tree.Color.RED))

node_4 = tree.Node(4)
arborist.insert(node_4)
expect(forester.height).to(equal(3))
expect(forester.black_height).to(equal(2))
expect(node_4.color).to(be(tree.Color.RED))

node_0 = tree.Node(0)
arborist.insert(node_0)
expect(forester.height).to(equal(4))
expect(forester.black_height).to(equal(2))
expect(node_3.color).to(be(tree.Color.RED))
expect(node_1.color).to(be(tree.Color.BLACK))
expect(node_4.color).to(be(tree.Color.BLACK))
expect(node_0.color).to(be(tree.Color.RED))

def inorder(node: tree.Node):
    if node is not tree.LEAF:
        inorder(node.left)
        print(f"{node.key} ({node.color})", end=", ")
        inorder(node.right)
    return

The Arborist

The arborist takes care of trees.

# this project
from bowling.data_structures.red_black_tree import tree as rb_tree
from bowling.data_structures.red_black_tree.rotator import Rotator

class Arborist:
    """An arborist to take care of trees

    Args:
     tree: tree to take care of
    """
    def __init__(self, tree: rb_tree.RedBlackTree) -> None:
        self._tree = None
        self.tree = tree
        self._insert = None
        self._delete = None
        return

@tree.setter
def tree(self, sapling: rb_tree.RedBlackTree) -> None:
    """Sets the tree and wipes out other attributes that use it

    Args:
     sapling: new tree
    """
    self._tree = sapling
    self._insert = None
    self._delete = None
    return

The Inserter Attribute

@property
def insert(self) -> Inserter:
    """Something to insert nodes"""
    if self._insert is None:
        self._insert = Inserter(tree=self.tree)
    return self._insert

Testing

arborist = Arborist(tree.RedBlackTree())

Sources

The Main Source:

The Clearer RB-Insert-Fixup Pseudocode: