Chapter_13_Red-Black_Trees/exercises_13.2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 13.2 Rotations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 13.2-1\n",
    "\n",
    "> Write pseudocode for RIGHT-ROTATE."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "RIGHT-ROTATE(T, y)\n",
    " 1  x = y.left\n",
    " 2  y.left = x.right\n",
    " 3  if x.right != T.nil\n",
    " 4      x.right.p = y\n",
    " 5  x.p = y.p\n",
    " 6  if y.p == T.nil\n",
    " 7      T.root = x\n",
    " 8  elseif y == y.p.right\n",
    " 9      y.p.right = x\n",
    "10  else y.p.left = x\n",
    "11  x.right = y\n",
    "12  y.p = x\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 13.2-2\n",
    "\n",
    "> Argue that in every $n$-node binary search tree, there are exactly $n - 1$ possible rotations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Every node can rotate with its parent, only the root does not have a parent, therefore there are $n - 1$ possible rotations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 13.2-3\n",
    "\n",
    "> Let $a$, $b$, and $c$ be arbitrary nodes in subtrees $\\alpha$, $\\beta$, and $\\gamma$, respectively, in the left tree of Figure 13.2. How do the depths of $a$, $b$, and $c$ change when a left rotation is performed on node $x$ in the figure?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$a$: increase by 1.\n",
    "\n",
    "$b$: unchanged.\n",
    "\n",
    "$c$: decrease by 1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 13.2-4\n",
    "\n",
    "> Show that any arbitrary $n$-node binary search tree can be transformed into any other arbitrary $n$-node binary search tree using $O(n)$ rotations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For each left leaf, we perform right rotation until there is no left leaf. We need at most $n-1$ right rotations to transform the tree into a right-going chain. \n",
    "\n",
    "Since we can transform every tree into a right-going chain, and the operation is invertible, therefore we can transform one tree into the right-going chain and use the inverse operation to construct the other tree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 13.2-5 $\\star$\n",
    "\n",
    "> We say that a binary search tree $T_1$ can be right-converted to binary search tree $T_2$ if it is possible to obtain $T_2$ from $T_1$ via a series of calls to RIGHT-ROTATE. Give an example of two trees $T_1$ and $T_2$ such that $T_1$ cannot be right-converted to $T_2$. Then, show that if a tree $T_1$ can be right-converted to $T_2$, it can be right-converted using $O(n^2)$ calls to RIGHT-ROTATE."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](img/13.2-5_1.png) ![](img/13.2-5_2.png)\n",
    "\n",
    "We can use $O(n)$ calls to rotate the node which is the root in $T_2$ to $T_1$'s root, then use the same operation in the two subtrees. There are $n$ nodes, therefore the upper bound is $O(n^2)$."
   ]
  }
 ],
 "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
}