Chapter_20_van_Emde_Boas_Trees/exercises_20.3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 20.3 The van Emde Boas tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 20.3-1\n",
    "\n",
    "> Modify vEB trees to support duplicate keys."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class VanEmdeBoasTree:\n",
    "    def __init__(self, u):\n",
    "        self.u = u\n",
    "        temp = u\n",
    "        bit_num = -1\n",
    "        while temp > 0:\n",
    "            temp >>= 1\n",
    "            bit_num += 1\n",
    "        self.sqrt_h = 1 << ((bit_num + 1) // 2)\n",
    "        self.sqrt_l = 1 << (bit_num // 2)\n",
    "        self.min = None\n",
    "        self.max = None\n",
    "        self.min_cnt = 0\n",
    "        self.max_cnt = 0\n",
    "        if not self.is_leaf():\n",
    "            self.summary = VanEmdeBoasTree(self.sqrt_h)\n",
    "            self.cluster = []\n",
    "            for _ in xrange(self.sqrt_h):\n",
    "                self.cluster.append(VanEmdeBoasTree(self.sqrt_l))\n",
    "\n",
    "    def is_leaf(self):\n",
    "        return self.u == 2\n",
    "\n",
    "    def high(self, x):\n",
    "        return x / self.sqrt_l\n",
    "\n",
    "    def low(self, x):\n",
    "        return x % self.sqrt_l\n",
    "\n",
    "    def index(self, x, y):\n",
    "        return x * self.sqrt_l + y\n",
    "\n",
    "    def minimum(self):\n",
    "        return self.min\n",
    "\n",
    "    def maximum(self):\n",
    "        return self.max\n",
    "\n",
    "    def member(self, x):\n",
    "        if x == self.min or x == self.max:\n",
    "            return True\n",
    "        if self.is_leaf():\n",
    "            return False\n",
    "        return self.member(self.cluster[self.high(x)], self.low(x))\n",
    "\n",
    "    def successor(self, x):\n",
    "        if self.is_leaf():\n",
    "            if x == 0 and self.max == 1:\n",
    "                return 1\n",
    "            return None\n",
    "        if self.min is not None and x < self.min:\n",
    "            return self.min\n",
    "        max_low = self.cluster[self.high(x)].maximum()\n",
    "        if max_low is not None and self.low(x) < max_low:\n",
    "            offset = self.cluster[self.high(x)].successor(self.low(x))\n",
    "            return self.index(self.high(x), offset)\n",
    "        succ_cluster = self.summary.successor(self.high(x))\n",
    "        if succ_cluster is None:\n",
    "            return None\n",
    "        offset = self.cluster[succ_cluster].minimum()\n",
    "        return self.index(succ_cluster, offset)\n",
    "\n",
    "    def predecessor(self, x):\n",
    "        if self.is_leaf():\n",
    "            if x == 1 and self.min == 0:\n",
    "                return 0\n",
    "            return None\n",
    "        if self.max is not None and x > self.max:\n",
    "            return self.max\n",
    "        min_low = self.cluster[self.high(x)].minimum()\n",
    "        if min_low is not None and self.low(x) > min_low:\n",
    "            offset = self.cluster[self.high(x)].predecessor(self.low(x))\n",
    "            return self.index(self.high(x), offset)\n",
    "        pred_cluster = self.summary.predecessor(self.high(x))\n",
    "        if pred_cluster is None:\n",
    "            if self.min is not None and x > self.min:\n",
    "                return self.min\n",
    "            return None\n",
    "        offset = self.cluster[pred_cluster].maximum()\n",
    "        return self.index(pred_cluster, offset)\n",
    "\n",
    "    def insert_empty(self, x, n):\n",
    "        self.min = x\n",
    "        self.max = x\n",
    "        self.min_cnt = self.max_cnt = n\n",
    "\n",
    "    def insert(self, x, n=1):\n",
    "        if self.min is None:\n",
    "            self.insert_empty(x, n)\n",
    "            return\n",
    "        if x == self.max:\n",
    "            self.max_cnt += n\n",
    "        if x == self.min:\n",
    "            self.min_cnt += n\n",
    "            return\n",
    "        if x < self.min:\n",
    "            x, self.min = self.min, x\n",
    "            n, self.min_cnt = self.min_cnt, n\n",
    "        if not self.is_leaf():\n",
    "            if self.cluster[self.high(x)].minimum() is None:\n",
    "                self.summary.insert(self.high(x))\n",
    "                self.cluster[self.high(x)].insert_empty(self.low(x), n)\n",
    "            else:\n",
    "                self.cluster[self.high(x)].insert(self.low(x), n)\n",
    "        if x > self.max:\n",
    "            self.max = x\n",
    "            self.max_cnt = n\n",
    "\n",
    "    def delete(self, x, n=1):\n",
    "        if self.min == self.max:\n",
    "            if self.min is None or self.min_cnt == n:\n",
    "                self.min = self.max = None\n",
    "                self.min_cnt = 0\n",
    "            else:\n",
    "                self.min_cnt -= n\n",
    "            self.max_cnt = self.min_cnt\n",
    "            return\n",
    "        if self.is_leaf():\n",
    "            if x == 0:\n",
    "                self.min_cnt -= n\n",
    "                if self.min_cnt == 0:\n",
    "                    self.min = 1\n",
    "                    self.min_cnt = self.max_cnt\n",
    "            else:\n",
    "                self.max_cnt -= n\n",
    "                if self.max_cnt == 0:\n",
    "                    self.max = 0\n",
    "                    self.max_cnt = self.min_cnt\n",
    "            return\n",
    "        next_n = n\n",
    "        if x == self.min:\n",
    "            if self.min_cnt > n:\n",
    "                self.min_cnt -= n\n",
    "                return\n",
    "            first_cluster = self.summary.minimum()\n",
    "            x = self.index(first_cluster,\n",
    "                           self.cluster[first_cluster].minimum())\n",
    "            self.min = x\n",
    "            self.min_cnt = self.cluster[first_cluster].min_cnt\n",
    "            next_n = self.cluster[first_cluster].min_cnt\n",
    "        self.cluster[self.high(x)].delete(self.low(x), next_n)\n",
    "        if self.cluster[self.high(x)].minimum() is None:\n",
    "            self.summary.delete(self.high(x))\n",
    "            if x == self.max:\n",
    "                if self.max == self.min:\n",
    "                    self.max_cnt = self.min_cnt\n",
    "                    return\n",
    "                self.max_cnt -= n\n",
    "                if self.max_cnt == 0:\n",
    "                    sum_max = self.summary.maximum()\n",
    "                    if sum_max is None:\n",
    "                        self.max = self.min\n",
    "                        self.max_cnt = self.min_cnt\n",
    "                    else:\n",
    "                        self.max = self.index(sum_max,\n",
    "                                              self.cluster[sum_max].maximum())\n",
    "                        self.max_cnt = self.cluster[sum_max].max_cnt\n",
    "        elif x == self.max:\n",
    "            if self.max == self.min:\n",
    "                self.max_cnt = self.min_cnt\n",
    "                return\n",
    "            self.max_cnt -= n\n",
    "            if self.max_cnt == 0:\n",
    "                self.max = self.index(self.high(x),\n",
    "                                      self.cluster[self.high(x)].maximum())\n",
    "                self.max_cnt = self.cluster[self.high(x)].max_cnt\n",
    "\n",
    "    def display(self, space=0, summary=False):\n",
    "        disp = ' ' * space\n",
    "        if summary:\n",
    "            disp += 'S '\n",
    "        else:\n",
    "            disp += 'C '\n",
    "        disp += str(self.u) + ' ' + str(self.min) + ' ' + str(self.max) + ' | '\n",
    "        disp += str(self.min_cnt) + ' ' + str(self.max_cnt)\n",
    "        print(disp)\n",
    "        if not self.is_leaf():\n",
    "            self.summary.display(space + 2, True)\n",
    "            for c in self.cluster:\n",
    "                c.display(space + 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 20.3-2\n",
    "\n",
    "> Modify vEB trees to support keys that have associated satellite data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class VanEmdeBoasTree:\n",
    "    def __init__(self, u):\n",
    "        self.u = u\n",
    "        temp = u\n",
    "        bit_num = -1\n",
    "        while temp > 0:\n",
    "            temp >>= 1\n",
    "            bit_num += 1\n",
    "        self.sqrt_h = 1 << ((bit_num + 1) // 2)\n",
    "        self.sqrt_l = 1 << (bit_num // 2)\n",
    "        self.min = None\n",
    "        self.max = None\n",
    "        self.min_data = None\n",
    "        self.max_data = None\n",
    "        if not self.is_leaf():\n",
    "            self.summary = VanEmdeBoasTree(self.sqrt_h)\n",
    "            self.cluster = []\n",
    "            for _ in xrange(self.sqrt_h):\n",
    "                self.cluster.append(VanEmdeBoasTree(self.sqrt_l))\n",
    "\n",
    "    def is_leaf(self):\n",
    "        return self.u == 2\n",
    "\n",
    "    def high(self, x):\n",
    "        return x / self.sqrt_l\n",
    "\n",
    "    def low(self, x):\n",
    "        return x % self.sqrt_l\n",
    "\n",
    "    def index(self, x, y):\n",
    "        return x * self.sqrt_l + y\n",
    "\n",
    "    def minimum(self):\n",
    "        return self.min\n",
    "\n",
    "    def maximum(self):\n",
    "        return self.max\n",
    "\n",
    "    def member(self, x):\n",
    "        if x == self.min or x == self.max:\n",
    "            return True\n",
    "        if self.is_leaf():\n",
    "            return False\n",
    "        return self.member(self.cluster[self.high(x)], self.low(x))\n",
    "\n",
    "    def get_data(self, x):\n",
    "        if x == self.min:\n",
    "            return self.min_data\n",
    "        if x == self.max:\n",
    "            return self.max_data\n",
    "        if self.is_leaf():\n",
    "            return None\n",
    "        return self.cluster[self.high(x)].get_data(self.low(x))\n",
    "\n",
    "    def successor(self, x):\n",
    "        if self.is_leaf():\n",
    "            if x == 0 and self.max == 1:\n",
    "                return 1\n",
    "            return None\n",
    "        if self.min is not None and x < self.min:\n",
    "            return self.min\n",
    "        max_low = self.cluster[self.high(x)].maximum()\n",
    "        if max_low is not None and self.low(x) < max_low:\n",
    "            offset = self.cluster[self.high(x)].successor(self.low(x))\n",
    "            return self.index(self.high(x), offset)\n",
    "        succ_cluster = self.summary.successor(self.high(x))\n",
    "        if succ_cluster is None:\n",
    "            return None\n",
    "        offset = self.cluster[succ_cluster].minimum()\n",
    "        return self.index(succ_cluster, offset)\n",
    "\n",
    "    def predecessor(self, x):\n",
    "        if self.is_leaf():\n",
    "            if x == 1 and self.min == 0:\n",
    "                return 0\n",
    "            return None\n",
    "        if self.max is not None and x > self.max:\n",
    "            return self.max\n",
    "        min_low = self.cluster[self.high(x)].minimum()\n",
    "        if min_low is not None and self.low(x) > min_low:\n",
    "            offset = self.cluster[self.high(x)].predecessor(self.low(x))\n",
    "            return self.index(self.high(x), offset)\n",
    "        pred_cluster = self.summary.predecessor(self.high(x))\n",
    "        if pred_cluster is None:\n",
    "            if self.min is not None and x > self.min:\n",
    "                return self.min\n",
    "            return None\n",
    "        offset = self.cluster[pred_cluster].maximum()\n",
    "        return self.index(pred_cluster, offset)\n",
    "\n",
    "    def insert_empty(self, x, data):\n",
    "        self.min = x\n",
    "        self.max = x\n",
    "        self.min_data = self.max_data = data\n",
    "\n",
    "    def insert(self, x, data):\n",
    "        if self.min is None:\n",
    "            self.insert_empty(x, data)\n",
    "        else:\n",
    "            if x < self.min:\n",
    "                x, self.min = self.min, x\n",
    "                data, self.min_data = self.min_data, data\n",
    "            if not self.is_leaf():\n",
    "                if self.cluster[self.high(x)].minimum() is None:\n",
    "                    self.summary.insert(self.high(x), data)\n",
    "                    self.cluster[self.high(x)].insert_empty(self.low(x), data)\n",
    "                else:\n",
    "                    self.cluster[self.high(x)].insert(self.low(x), data)\n",
    "            if x > self.max:\n",
    "                self.max = x\n",
    "                self.max_data = data\n",
    "\n",
    "    def delete(self, x):\n",
    "        if self.min == self.max:\n",
    "            self.min = self.max = None\n",
    "            self.min_data = self.max_data = None\n",
    "        elif self.is_leaf():\n",
    "            if x == 0:\n",
    "                self.min = 1\n",
    "                self.min_data = self.max_data\n",
    "            else:\n",
    "                self.min = 0\n",
    "            self.max = self.min\n",
    "            self.max_data = self.min_data\n",
    "        else:\n",
    "            if x == self.min:\n",
    "                first_cluster = self.summary.minimum()\n",
    "                x = self.index(first_cluster,\n",
    "                               self.cluster[first_cluster].minimum())\n",
    "                self.min = x\n",
    "                self.min_data = self.cluster[first_cluster].min_data\n",
    "            self.cluster[self.high(x)].delete(self.low(x))\n",
    "            if self.cluster[self.high(x)].minimum() is None:\n",
    "                self.summary.delete(self.high(x))\n",
    "                if x == self.max:\n",
    "                    sum_max = self.summary.maximum()\n",
    "                    if sum_max is None:\n",
    "                        self.max = self.min\n",
    "                        self.max_data = self.min_data\n",
    "                    else:\n",
    "                        self.max = self.index(sum_max,\n",
    "                                              self.cluster[sum_max].maximum())\n",
    "                        self.max_data = self.cluster[sum_max].max_data\n",
    "            elif x == self.max:\n",
    "                self.max = self.index(self.high(x),\n",
    "                                      self.cluster[self.high(x)].maximum())\n",
    "                self.max_data = self.cluster[self.high(x)].max_data\n",
    "\n",
    "    def display(self, space=0, summary=False):\n",
    "        disp = ' ' * space\n",
    "        if summary:\n",
    "            disp += 'S '\n",
    "        else:\n",
    "            disp += 'C '\n",
    "        disp += str(self.u) + ' ' + str(self.min) + ' ' + str(self.max)\n",
    "        print(disp)\n",
    "        if not self.is_leaf():\n",
    "            self.summary.display(space + 2, True)\n",
    "            for c in self.cluster:\n",
    "                c.display(space + 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 20.3-3\n",
    "\n",
    "> Write pseudocode for a procedure that creates an empty van Emde Boas tree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "See exercise 20.3-1 and exercise 20.3-2."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 20.3-4\n",
    "\n",
    "> What happens if you call VEB-TREE-INSERT with an element that is already in the vEB tree? What happens if you call VEB-TREE-DELETE with an element that is not in the vEB tree? Explain why the procedures exhibit the behavior that they do. Show how to modify vEB trees and their operations so that we can check in constant time whether an element is present."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Already/not: nothing changes.\n",
    "\n",
    "Constant time: add an auxiliary array of size $u$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 20.3-5\n",
    "\n",
    "> Suppose that instead of $\\sqrt[\\uparrow]{u}$ clusters, each with universe size $\\sqrt[\\downarrow]{u}$, we constructed vEB trees to have $u^{1/k}$ clusters, each with universe size $u^{1-1/k}$, where $k > 1$ is a constant. If we were to modify the operations appropriately, what would be their running times? For the purpose of analysis, assume that $u^{1/k}$ and $u^{1-1/k}$ are always integers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "MINIMUM/MAXIMUM: $O(1)$.\n",
    "\n",
    "SUCCESSOR/PREDECESSOR/INSERT/DELETE worst: $T(u) = T(u^{1/k}) + O(1) = O(\\lg \\log_{1/k} u)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 20.3-6\n",
    "\n",
    "> Creating a vEB tree with universe size $u$ requires $O(u)$ time. Suppose we wish to explicitly account for that time. What is the smallest number of operations $n$ for which the amortized time of each operation in a vEB tree is $O(\\lg\\lg u)$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since MINIMUM/MAXIMUM is $O(1)$, we need about $\\displaystyle \\left \\lceil \\frac{u}{\\lg\\lg u} \\right \\rceil$ operations."
   ]
  }
 ],
 "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
}