Chapter_13_Red-Black_Trees/exercises_13.3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 13.3 Insertion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 13.3-1\n",
    "\n",
    "> In line 16 of RB-INSERT, we set the color of the newly inserted node $z$ to red. Observe that if we had chosen to set $z$'s color to black, then property 4 of a red-black tree would not be violated. Why didn’t we choose to set $z$'s color to black?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Violate property 5."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 13.3-2\n",
    "\n",
    "> Show the red-black trees that result after successively inserting the keys $41, 38, 31, 12, 19, 8$ into an initially empty red-black tree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Insert 41:\n",
    "\n",
    "![](img/13.3-2_1.png)\n",
    "\n",
    "Insert 38:\n",
    "\n",
    "![](img/13.3-2_2.png)\n",
    "\n",
    "Insert 31:\n",
    "\n",
    "![](img/13.3-2_3.png)\n",
    "\n",
    "![](img/13.3-2_4.png)\n",
    "\n",
    "Insert 12:\n",
    "\n",
    "![](img/13.3-2_5.png)\n",
    "\n",
    "![](img/13.3-2_6.png)\n",
    "\n",
    "Insert 19:\n",
    "\n",
    "![](img/13.3-2_7.png)\n",
    "\n",
    "![](img/13.3-2_8.png)\n",
    "\n",
    "![](img/13.3-2_9.png)\n",
    "\n",
    "Insert 8:\n",
    "\n",
    "![](img/13.3-2_10.png)\n",
    "\n",
    "![](img/13.3-2_11.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 13.3-3\n",
    "\n",
    "> Suppose that the black-height of each of the subtrees $\\alpha, \\beta, \\gamma, \\delta, \\epsilon$ in Figures 13.5 and 13.6 is $k$. Label each node in each figure with its black-height to verify that the indicated transformation preserves property 5."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](img/13.3-3_1.png)\n",
    "\n",
    "![](img/13.3-3_2.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 13.3-4\n",
    "\n",
    "> Professor Teach is concerned that RB-INSERT-FIXUP might set $T.nil.color$ to RED, in which case the test in line 1 would not cause the loop to terminate when $z$ is the root. Show that the professor's concern is unfounded by arguing that RBINSERT-FIXUP never sets $T.nil.color$ to RED."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In order to set $T.nil.color$ to RED, $z.p$ must be the root; and if $z.p$ is the root, then $z.p$ is black, the loop terminates. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 13.3-5\n",
    "\n",
    "> Consider a red-black tree formed by inserting $n$ nodes with RB-INSERT. Argue that if $n > 1$, the tree has at least one red node."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In case 1, $z$ and $z.p.p$ are RED, if the loop terminates, then $z$ could not be the root, thus $z$ is RED after the fix up.\n",
    "\n",
    "In case 2, $z$ and $z.p$ are RED, and after the rotation $z.p$ could not be the root, thus $z.p$ is RED after the fix up.\n",
    "\n",
    "In case 3, $z$ is RED and $z$ could not be the root, thus $z$ is RED after the fix up.\n",
    "\n",
    "Therefore, there is always at least one red node."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 13.3-6\n",
    "\n",
    "> Suggest how to implement RB-INSERT efficiently if the representation for red-black trees includes no storage for parent pointers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use stack to record the path to the inserted node, then parent is the top element in the stack.\n",
    "\n",
    "In case 1, we pop $z.p$ and $z.p.p$.\n",
    "\n",
    "In case 2, we pop $z.p$ and $z.p.p$, then push $z.p.p$ and $z$.\n",
    "\n",
    "In case 3, we pop $z.p$, $z.p.p$ and $z.p.p.p$, then push $z.p$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "RED = 0\n",
    "BLACK = 1\n",
    "\n",
    "\n",
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self.vals = []\n",
    "\n",
    "    def push(self, x):\n",
    "        self.vals.append(x)\n",
    "\n",
    "    def pop(self):\n",
    "        if len(self.vals) == 0:\n",
    "            return None\n",
    "        x = self.vals[-1]\n",
    "        del self.vals[-1]\n",
    "        return x\n",
    "\n",
    "\n",
    "class RedBlackTreeNode:\n",
    "    def __init__(self, key, left=None, right=None):\n",
    "        self.color = BLACK\n",
    "        self.key = key\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "class RedBlackTree:\n",
    "    def __init__(self):\n",
    "        self.nil = RedBlackTreeNode(None)\n",
    "        self.nil.color = BLACK\n",
    "        self.nil.left = self.nil\n",
    "        self.nil.right = self.nil\n",
    "        self.root = self.nil\n",
    "\n",
    "\n",
    "def left_rotate(T, x, p):\n",
    "    y = x.right\n",
    "    x.right = y.left\n",
    "    if p == T.nil:\n",
    "        T.root = y\n",
    "    elif x == p.left:\n",
    "        p.left = y\n",
    "    else:\n",
    "        p.right = y\n",
    "    y.left = x\n",
    "\n",
    "\n",
    "def right_rotate(T, x, p):\n",
    "    y = x.left\n",
    "    x.left = y.right\n",
    "    if p == T.nil:\n",
    "        T.root = y\n",
    "    elif x == p.right:\n",
    "        p.right = y\n",
    "    else:\n",
    "        p.left = y\n",
    "    y.right = x\n",
    "\n",
    "\n",
    "def rb_insert_fixup(T, z, stack):\n",
    "    while True:\n",
    "        p = stack.pop()\n",
    "        if p.color == BLACK:\n",
    "            break\n",
    "        pp = stack.pop()\n",
    "        if p == pp.left:\n",
    "            y = pp.right\n",
    "            if y.color == RED:\n",
    "                p.color = BLACK\n",
    "                y.color = BLACK\n",
    "                pp.color = RED\n",
    "                z = pp\n",
    "            elif z == p.right:\n",
    "                stack.push(pp)\n",
    "                stack.push(z)\n",
    "                z = p\n",
    "                left_rotate(T, z, pp)\n",
    "            else:\n",
    "                ppp = stack.pop()\n",
    "                stack.push(p)\n",
    "                p.color = BLACK\n",
    "                pp.color = RED\n",
    "                right_rotate(T, pp, ppp)\n",
    "        else:\n",
    "            y = pp.left\n",
    "            if y.color == RED:\n",
    "                p.color = BLACK\n",
    "                y.color = BLACK\n",
    "                pp.color = RED\n",
    "                z = pp\n",
    "            elif z == p.left:\n",
    "                stack.push(pp)\n",
    "                stack.push(z)\n",
    "                z = p\n",
    "                right_rotate(T, z, pp)\n",
    "            else:\n",
    "                ppp = stack.pop()\n",
    "                stack.push(p)\n",
    "                p.color = BLACK\n",
    "                pp.color = RED\n",
    "                left_rotate(T, pp, ppp)\n",
    "    T.root.color = BLACK\n",
    "\n",
    "\n",
    "def rb_insert(T, z):\n",
    "    stack = Stack()\n",
    "    stack.push(T.nil)\n",
    "    y = T.nil\n",
    "    x = T.root\n",
    "    while x != T.nil:\n",
    "        stack.push(x)\n",
    "        y = x\n",
    "        if z.key < x.key:\n",
    "            x = x.left\n",
    "        else:\n",
    "            x = x.right\n",
    "    if y == T.nil:\n",
    "        T.root = z\n",
    "    elif z.key < y.key:\n",
    "        y.left = z\n",
    "    else:\n",
    "        y.right = z\n",
    "    z.left = T.nil\n",
    "    z.right = T.nil\n",
    "    z.color = RED\n",
    "    rb_insert_fixup(T, z, stack)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}