08_BalancedSearchTrees/BalancedSearchTrees.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Balanced Search Trees\n",
    "\n",
    "**Balanced search trees** are an implementation of symbol tables (with comparable keys) that guarantee efficient operations of search, insert, delete, max, min, rank, floor, ceiling, and select."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2-3 Search Trees\n",
    "\n",
    "Recall from the previous section on Elementary Symbol Tables that the goal for symbol table implementations was $\\lg N$ for all operations. **2-3 Trees**, which are left-leaning red-black BSTs, are an old implementation to do this. They allow 1 or 2 keys per node, so there's a **2-node** (one key, two children) or a **3-node** (two keys, three children). The 2-node has two links - one to keys less than the node key and one for keys greater. The 3-node has three links - one for keys less than the smaller key, one for keys between the two keys, and one for keys greater than the larger key.\n",
    "\n",
    "2-3 trees also have **perfect balance**, so every path from the root to a null link has the same length. They also have **symmetric order** so an in-order traversal (follow left-most paths to keys)  yields the keys in ascending order.\n",
    "\n",
    "To **insert**, you first search for the key. The easy case is if you end at a 2-node at the bottom, then you just replace that 2-node with a 3-node containing the new inserted key with what was in that 2-node, and add a null link for the third child. To insert a new key to a 3-node at the bottom, first create a temporary 4-node, then move the middle key in the 4-node into the parent. The parent becomes a 3-node, and the 2-node child is split so the children are re-linked (the smaller key becomes the new middle link of the parent and the larger key becomes the right link). If the parent were already a 3-node, it would become a temporary 4-node and that process would propagate up the tree. The only time the height of a 2-3 tree grows is when the root was a 3-node and the process reaches it, so the root has to split.\n",
    "\n",
    "Splitting a 4-node is a **local** transformation - there are a constant number of operations and they don't touch the subtrees, no matter how many keys are below where the split happens. Each transformation maintains symmetric order and perfect balance.\n",
    "\n",
    "**Tree height** worst case is $\\lg N$ (with all 2-nodes), or best case $\\log_{3} N \\approx 0.631 \\lg N$ (with all 3-nodes). This guarantees **logarithmic** performance for search and insert.\n",
    "\n",
    "**Implementation** is complicated (see the red-black BST option below instead):\n",
    "- Maintaining multiple node types is cumbersome\n",
    "- Need multiple compares to move down the tree\n",
    "- Need to move back up the tree to split 4-nodes\n",
    "- Large number of cases for splitting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Example of inserting in a 2-3 search tree:**\n",
    "\n",
    "![Wikipedia 2-3 search tree example](https://upload.wikimedia.org/wikipedia/commons/thumb/4/44/2-3_insertion.svg/581px-2-3_insertion.svg.png)\n",
    "\n",
    "Source: Wikipedia"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Red-Black BSTs\n",
    "\n",
    "Red-black BSTs are simple data structures that help implement 2-3 trees with very little extra code beyond the basic binary search tree. The idea is to represent a 2-3 tree as a binary search tree, and use \"internal\" left-leaning links as \"glue\" for 3-nodes. So the larger of the two keys in a 3-node will be the root in this subtree - its right link goes to keys larger than it and its left link (colored red) connects to the smaller of the two original keys. That key is now a 2-node with a left link to keys smaller and right link to keys that were between the original two keys.\n",
    "\n",
    "**Black links** connect 2-nodes and 3-nodes, **red links** \"glue\" nodes within a 3-node.\n",
    "\n",
    "Some characteristics:\n",
    "- No node has two red links connected to it\n",
    "- Every path from the root to a null link has the same number of black links (**perfect black balance**)\n",
    "- Red links lean left\n",
    "\n",
    "There's a 1-1 correspondence of left-leaning red-black (LLRB) BSTs and 2-3 trees (think of the red links as horizontal ones, and it looks like a 2-3 tree. You can use the same search code from elementary BST, just ignore the color. It actually runs faster because of better balance. Most other operations (ceiling, selection) are also identical.\n",
    "\n",
    "Because each node is pointed to by precisely one link (its parent), you can encode the color of the links as data in the node (e.g. `node.left.color == 'RED'` or `node.right.color == 'BLACK'`) and null links are black."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Node object from BST notes, ignores non-critical methods\n",
    "class Node:\n",
    "    def __init__(self, key, val, left=None, right=None, count=1, color='BLACK'):\n",
    "        self.key = key\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.count = count  # Number of nodes in subtree including self\n",
    "        self.color = color  # NEW FOR LLRB BST - color of parent link\n",
    "\n",
    "    # NEW FOR LLRB BST\n",
    "    def is_red(self, node_x):\n",
    "        if node_x is None:\n",
    "            return False\n",
    "        return node_x.color == 'RED'\n",
    "    \n",
    "    def is_black(self, node_x):\n",
    "        if node_x is None:\n",
    "            return True  # Null links are black\n",
    "        return node_x.color == 'BLACK'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n color: BLACK\n",
      "n.right color: BLACK\n",
      "n.left.color: RED\n",
      "Node left link is red: True\n",
      "Node right link is red: False\n",
      "Node left link is black: False\n",
      "Node right link is black: True\n"
     ]
    }
   ],
   "source": [
    "# Test new node functionality\n",
    "n = Node(2, 2)\n",
    "print('n color: {}'.format(n.color))\n",
    "n.right = Node(4, 4)\n",
    "print('n.right color: {}'.format(n.right.color))\n",
    "n.left = Node(1, 1, color='RED')\n",
    "print('n.left.color: {}'.format(n.left.color))\n",
    "print('Node left link is red: {}'.format(n.is_red(n.left)))\n",
    "print('Node right link is red: {}'.format(n.is_red(n.right)))\n",
    "print('Node left link is black: {}'.format(n.is_black(n.left)))\n",
    "print('Node right link is black: {}'.format(n.is_black(n.right)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Red-Black BST Operations\n",
    "\n",
    "A new operation for red-black BSTs is a **rotation**. During an insertion operation, sometimes you end up with a right-leaning red link (the wrong direction). A rotation will re-orient the link so it leans to the left. Rotations maintain symmetric order and perfect black balance.\n",
    "\n",
    "**Left Rotation Java Implementation:**\n",
    "\n",
    "![Example of a right-to-left rotation. Source: Princeton.edu](https://algs4.cs.princeton.edu/33balanced/images/redblack-left-rotate.png)\n",
    "\n",
    "Sometimes during an insertion, you'll need to temporarily rotate links to have a red right-leaning link before rotating it left. The rotation implementation is similar (see LLRB_BST class for implementation below).\n",
    "\n",
    "**Right Rotation Java Implementation:**\n",
    "\n",
    "![Example of a left-to-right rotation. Source: Princeton.edu](https://algs4.cs.princeton.edu/33balanced/images/redblack-right-rotate.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another operation is called a **color flip**, which you use to re-color the local links to split a temporary 4-node. You don't need to change any links, but the parent key will have two red links (both left and right), and will be black itself. You flip the colors so the parent is red and both its links are black.\n",
    "\n",
    "**Color Flip Java Implementation:**\n",
    "\n",
    "![Example of a red-black BST color flip. Source: princeton.edu](https://algs4.cs.princeton.edu/33balanced/images/color-flip.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Insertions** use these three operations (left rotation, right rotation, and color flip) to maintain a legal red-black BST with 1-1 correspondence to a 2-3 tree. Here are the main scenarios:\n",
    "\n",
    "1. Insert into a tree with exactly 1 node\n",
    "    - **Left:** search ends at the left null link, create a red link to the new node (converts a 2-node into a 3-node)\n",
    "    - **Right:** search ends the right null link, you attach a new node with a red link on the right, then rotate left to make a legal 3-node\n",
    "    - **Generalization:** (insert into a 2-node at the bottom) you do a standard BST insert and color the new link red. If it's on the right, rotate left\n",
    "\n",
    "2. Insert into a tree with 2 nodes (see image). The generalization is to insert into a 3-node at the bottom\n",
    "    - Do standard BST insert, color the new link red\n",
    "    - Rotate to balance the 4-node (if needed)\n",
    "    - Flip colors to pass the red link up one level\n",
    "    - Rotate to make left-leaning (if needed)\n",
    "\n",
    "![Example inserting into a tree with 2 nodes](https://x-wei.github.io/images/algoI_week5_1/pasted_image026.png)\n",
    "\n",
    "The same code handles all cases:\n",
    "- Right child red, left child black -> rotate left\n",
    "- Left child, left-left grandchild red -> rotate right\n",
    "- Both children red -> flip colors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Full Left-leaning Red-Black Binary Search Tree class\n",
    "class LL_Red_Black_BST:\n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "\n",
    "    def size(self):\n",
    "        return self._size(self.root)\n",
    "\n",
    "    def _size(self, node_x):\n",
    "        if node_x is None:\n",
    "            return 0\n",
    "        else:\n",
    "            return node_x.count\n",
    "\n",
    "    def put(self, key, val):\n",
    "        # Insert a new key-value node in the BST\n",
    "        self.root = self._put(self.root, key, val)\n",
    "\n",
    "    # Insertion code - NEW FOR LLRB BST\n",
    "    def _put(self, node_h, key, val):\n",
    "        if (node_h is None):\n",
    "            return Node(key, val, color='RED')\n",
    "        if key < node_h.key:\n",
    "            node_h.left = self._put(node_h.left, key, val)\n",
    "        elif key > node_h.key:\n",
    "            node_h.right = self._put(node_h.right, key, val)\n",
    "        else:\n",
    "            node_h.val = val\n",
    "\n",
    "        if (node_h.is_red(node_h.right) and node_h.is_black(node_h.left)):\n",
    "            # print('Rotating LEFT - parent: {}'.format(node_h.val))\n",
    "            node_h = self.rotate_left(node_h)\n",
    "        if (node_h.is_red(node_h.left) and node_h.is_red(node_h.left.left)):\n",
    "            # print('Rotating RIGHT - parent: {}'.format(node_h.val))\n",
    "            node_h = self.rotate_right(node_h)\n",
    "        if (node_h.is_red(node_h.left) and node_h.is_red(node_h.right)):\n",
    "            # print('FLIP COLORS - parent: {}, left: {}, right: {}'.format(node_h.val, node_h.left.val, node_h.right.val))\n",
    "            self.flip_colors(node_h)\n",
    "        \n",
    "        node_h.count = 1 + self._size(node_h.left) + self._size(node_h.right)\n",
    "        return node_h\n",
    "\n",
    "    # Rotate left - NEW FOR LLRB BST\n",
    "    def rotate_left(self, node_h):\n",
    "        # node_h is parent with right-leaning red link to node_x\n",
    "        # Rotates the cluster so node_x is new parent with red link to node_h\n",
    "        node_x = node_h.right\n",
    "        node_h.right = node_x.left  # Move middle keys over so they're h's right link\n",
    "        node_x.left = node_h\n",
    "        node_x.color = node_h.color  # Assign h's original color to x\n",
    "        node_h.color = 'RED'\n",
    "        node_x.count = node_h.count  # Move h's size to x, its new parent\n",
    "        node_h.count = 1 + self._size(node_h.left) + self._size(node_h.right)\n",
    "        return node_x\n",
    "\n",
    "    # Rotate right - NEW FOR LLRB BST\n",
    "    def rotate_right(self, node_h):\n",
    "        # node_h is parent with two left red links in a row (child, grandchild)\n",
    "        # Rotates to the right\n",
    "        node_x = node_h.left\n",
    "        node_h.left = node_x.right  # Move middle keys over so they're h's left link\n",
    "        node_x.right = node_h\n",
    "        node_x.color = node_h.color  # Assign h's original color to x\n",
    "        node_h.color = 'RED'\n",
    "        node_x.count = node_h.count  # Move h's size to x, its new parent\n",
    "        node_h.count = 1 + self._size(node_h.left) + self._size(node_h.right)\n",
    "        return node_x\n",
    "\n",
    "    # Color flip - NEW FOR LLRB BST\n",
    "    def flip_colors(self, node_h):\n",
    "        # Flip color of parent and two child node links\n",
    "        node_h.color == 'RED'\n",
    "        node_h.left.color = 'BLACK'\n",
    "        node_h.right.color = 'BLACK'\n",
    "\n",
    "    def get(self, key):\n",
    "        # Returns the NODE associated with given key if in tree, None otherwise\n",
    "        node_x = self.root\n",
    "        while node_x is not None:\n",
    "            if key < node_x.key:\n",
    "                node_x = node_x.left\n",
    "            elif key > node_x.key:\n",
    "                node_x = node_x.right\n",
    "            else:\n",
    "                return node_x\n",
    "        return None\n",
    "\n",
    "    def delete(self, key):\n",
    "        # Remove the node for a given key\n",
    "        self.root = self._delete(self.root, key)\n",
    "\n",
    "    def _delete(self, node_x, key):\n",
    "        if node_x is None:\n",
    "            return None\n",
    "        if key < node_x.key:\n",
    "            node_x.left = self._delete(node_x.left, key)\n",
    "        elif key > node_x.key:\n",
    "            node_x.right = self._delete(node_x.right, key)\n",
    "        else:\n",
    "            if node_x.right is None:\n",
    "                # No right child\n",
    "                return node_x.left\n",
    "            if node_x.left is None:\n",
    "                # No left child\n",
    "                return node_x.right\n",
    "            \n",
    "            # Node has two children - replace with successor\n",
    "            node_t = node_x\n",
    "            node_x = self._min(node_t.right)\n",
    "            node_x.right = self._delete_min(node_t.right)\n",
    "            node_x.left = node_t.left\n",
    "        \n",
    "        # Update subtree counts\n",
    "        node_x.count = 1 + self._size(node_x.left) + self._size(node_x.right)\n",
    "        return node_x\n",
    "\n",
    "    def delete_min(self):\n",
    "        if self.root:\n",
    "            self.root = self._delete_min(self.root)\n",
    "\n",
    "    def _delete_min(self, node_x):\n",
    "        if node_x.left is None:\n",
    "            return node_x.right\n",
    "        node_x.left = self._delete_min(node_x.left)\n",
    "        node_x.count = 1 + self._size(node_x.left) + self._size(node_x.right)\n",
    "        return node_x\n",
    "\n",
    "    def floor(self, key):\n",
    "        # Return the largest key in the BST <= a given key\n",
    "        node_x = self._floor(self.root, key)\n",
    "        if node_x is None:\n",
    "            return None\n",
    "        return node_x.key\n",
    "    \n",
    "    def _floor(self, node_x, key):\n",
    "        if node_x is None:\n",
    "            return None\n",
    "        if key == node_x.key:\n",
    "            return node_x\n",
    "        elif key < node_x.key:\n",
    "            # Floor is in left subtree\n",
    "            return self._floor(node_x.left, key)\n",
    "        \n",
    "        # Floor may be in right subtree or is root of that subtree\n",
    "        node_t = self._floor(node_x.right, key)\n",
    "        if node_t is not None:\n",
    "            return node_t\n",
    "        else:\n",
    "            return node_x\n",
    "    \n",
    "    def ceiling(self, key):\n",
    "        # Return the smallest key in the BST >= a given key\n",
    "        node_x = self._ceiling(self.root, key)\n",
    "        if node_x is None:\n",
    "            return None\n",
    "        return node_x.key\n",
    "    \n",
    "    def _ceiling(self, node_x, key):\n",
    "        if node_x is None:\n",
    "            return None\n",
    "        if key == node_x.key:\n",
    "            return node_x\n",
    "        elif key > node_x.key:\n",
    "            # Ceiling is in right subtree\n",
    "            return self._ceiling(node_x.right, key)\n",
    "        \n",
    "        # Ceiling may be in the left subtree or is root of that subtree\n",
    "        node_t = self._ceiling(node_x.left, key)\n",
    "        if node_t is not None:\n",
    "            return node_t\n",
    "        else:\n",
    "            return node_x\n",
    "    \n",
    "    def get_max(self):\n",
    "        # Returns the largest key in the tree\n",
    "        node_x = self.root\n",
    "        while node_x is not None:\n",
    "            if node_x.right is not None:\n",
    "                node_x = node_x.right\n",
    "            else:\n",
    "                return node_x.val\n",
    "        return None\n",
    "    \n",
    "    def get_min(self):\n",
    "        # Returns the smallest key in the tree\n",
    "        node_x = self.root\n",
    "        while node_x is not None:\n",
    "            if node_x.left is not None:\n",
    "                node_x = node_x.left\n",
    "            else:\n",
    "                return node_x.key\n",
    "        return None\n",
    "    \n",
    "    def _min(self, node_x):\n",
    "        # Return the node with the smallest key in node_x's subtree\n",
    "        while node_x is not None:\n",
    "            if node_x.left is not None:\n",
    "                node_x = node_x.left\n",
    "            else:\n",
    "                return node_x\n",
    "        return None\n",
    "    \n",
    "    def rank(self, key):\n",
    "        # Returns how many keys in the BST are < given key\n",
    "        return self._rank(self.root, key)\n",
    "    \n",
    "    def _rank(self, node_x, key):\n",
    "        if node_x is None:\n",
    "            return 0\n",
    "        if key < node_x.key:\n",
    "            return self._rank(node_x.left, key)\n",
    "        elif key > node_x.key:\n",
    "            return 1 + self._size(node_x.left) + self._rank(node_x.right, key)\n",
    "        else:\n",
    "            return self._size(node_x.left)\n",
    "             \n",
    "    def __len__(self):\n",
    "        return self.size()\n",
    "    \n",
    "    def __setitem__(self, key, val):\n",
    "        self.put(key, val)\n",
    "    \n",
    "    def __getitem__(self, key):\n",
    "        return self.get(key).val\n",
    "\n",
    "    def __contains__(self, key):\n",
    "        if self.get(key):\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Add nodes to the BST and get values: check put and get operations\n",
      "Key: 5, Val: 5, Link to parent: RED\n",
      "Key: 3, Val: 3, Link to parent: BLACK\n",
      "Key: 8, Val: 8, Link to parent: RED\n",
      "Key: 4, Val: 4, Link to parent: BLACK\n",
      "Key: 7, Val: 7, Link to parent: BLACK\n",
      "Key: 6, Val: 6, Link to parent: BLACK\n",
      "Key: 10, Val: 10, Link to parent: BLACK\n",
      "Key: 0, Val: 0, Link to parent: BLACK\n",
      "\n",
      "Tree size: 8\n",
      "\n",
      "Check ceiling and floor operations\n",
      "Key: 7\n",
      "Ceiling: 7\n",
      "Floor: 7\n",
      "\n",
      "Key: 2\n",
      "Ceiling: 3\n",
      "Floor: 0\n",
      "\n",
      "Key: 11\n",
      "Ceiling: None\n",
      "Floor: 10\n",
      "\n",
      "Check max and min operations\n",
      "Max value: 10\n",
      "Min value: 0\n",
      "\n",
      "Check rank operation (number of keys in the tree < given key)\n",
      "Rank of 6: 4\n",
      "Rank of 11: 8\n",
      "Rank of 0: 0\n",
      "\n",
      "Check dunder methods\n",
      "Add 12 to table via llrb[12] = 12. New max value is 12\n",
      "New tree size: 9\n",
      "Check getitem via llrb[10] is: 10\n",
      "Is 8 in the table? True\n",
      "Is 9 in the table? False\n",
      "\n",
      "Check delete operation\n",
      "Remove node 0. Tree size: 8. New min value: 3\n",
      "Remove node 12. Tree size: 7. New max value: 10\n",
      "Remove node 8. Tree size: 6\n"
     ]
    }
   ],
   "source": [
    "# Test LLRB BST functionality\n",
    "llrb = LL_Red_Black_BST()\n",
    "\n",
    "# Add nodes, value equals the key. Check put operation\n",
    "print('Add nodes to the BST and get values: check put and get operations')\n",
    "keys = [5, 3, 8, 4, 7, 6, 10, 0]\n",
    "for k in keys:\n",
    "    llrb.put(k, k)\n",
    "\n",
    "# Check get operation\n",
    "for k in keys:\n",
    "    temp_node = llrb.get(k)\n",
    "    print('Key: {}, Val: {}, Link to parent: {}'.format(k, temp_node.val, temp_node.color))\n",
    "\n",
    "print('\\nTree size: {}'.format(llrb.size()))\n",
    "\n",
    "print('\\nCheck ceiling and floor operations')\n",
    "for k in [7, 2, 11]:\n",
    "    print('Key: {}\\nCeiling: {}\\nFloor: {}\\n'.format(k, llrb.ceiling(k), llrb.floor(k)))\n",
    "\n",
    "print('Check max and min operations')\n",
    "print('Max value: {}'.format(llrb.get_max()))\n",
    "print('Min value: {}'.format(llrb.get_min()))\n",
    "\n",
    "print('\\nCheck rank operation (number of keys in the tree < given key)')\n",
    "print('Rank of 6: {}'.format(llrb.rank(6)))\n",
    "print('Rank of 11: {}'.format(llrb.rank(11)))\n",
    "print('Rank of 0: {}'.format(llrb.rank(0)))\n",
    "\n",
    "print('\\nCheck dunder methods')\n",
    "new = 12\n",
    "llrb[new] = new  # set item\n",
    "print('Add {0} to table via llrb[{0}] = {0}. New max value is {1}'.format(new, llrb.get_max()))\n",
    "print('New tree size: {}'.format(len(llrb)))  # len\n",
    "check = 10\n",
    "print('Check getitem via llrb[{}] is: {}'.format(check, llrb[check]))  # get item\n",
    "print('Is 8 in the table? {}'.format(8 in llrb))  # contains\n",
    "print('Is 9 in the table? {}'.format(9 in llrb))  # contains\n",
    "\n",
    "print('\\nCheck delete operation')\n",
    "llrb.delete(0)\n",
    "print('Remove node 0. Tree size: {}. New min value: {}'.format(len(llrb), llrb.get_min()))\n",
    "llrb.delete(12)\n",
    "print('Remove node 12. Tree size: {}. New max value: {}'.format(len(llrb), llrb.get_max()))\n",
    "llrb.delete(8)\n",
    "print('Remove node 8. Tree size: {}'.format(len(llrb)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Summary\n",
    "\n",
    "The worst case (WC) is after $N$ inserts, and the average case (AC) is after $N$ random inserts.\n",
    "\n",
    "The height of any red-black BST on $n$ keys (regardless of the order of insertion) is guaranteed to be between $\\log⁡_{2} n$ and $2 \\log_{⁡2}n$.\n",
    "\n",
    "| Implementation | WC Search | WC Insert | WC Delete | AC Search | AC Insert | AC Delete | Ordered Iteration? |\n",
    "| --- | --- | --- | --- | --- | --- | --- | --- |\n",
    "| Sequential Search (unordered list) | $N$ | $N$ | $N$ | $N/2$ | $N$ | $N/2$ | No |\n",
    "| Binary Search (ordered array) | $\\lg N$ | $N$ | $N$ | $\\lg N$ | $N/2$ | $N/2$ | Yes |\n",
    "| Binary Search Tree (BST) | $N$ | $N$ | $N$ | $1.39 \\lg N$ | $1.39 \\lg N$ | ? | Yes |\n",
    "| 2-3 Tree | $c \\lg N$ | $c \\lg N$ | $c \\lg N$ | $c \\lg N$ | $c \\lg N$ | $c \\lg N$ | Yes |\n",
    "| Red-Black BST | $2 \\lg N$ | $2 \\lg N$ | $2 \\lg N$ | $1.00 \\lg N$\\* | $1.00 \\lg N$\\* | $1.00 \\lg N$ | Yes |\n",
    "\n",
    "\\* Exact coefficient unknown but extremely close to 1.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## B-Trees\n",
    "\n",
    "**B-trees** are a general version of the red-black BST. One practical application is accessing contiguous blocks of data (a \"page\", like a file or 4096-byte chunk of data) with a probe (from a disk to memory). The time required to first access the page is much larger than the time to access data within a page. The cost is the number of probes, and the goal is to access the data with a minimum number of probes.\n",
    "\n",
    "The B-tree generalizes a 2-3 tree by allowing up to $M - 1$ key-link pairs per node. You choose $M$ as large as possible so that $M$ links fit in a page (for example, $M$ is 1024).\n",
    "\n",
    "- At least 2 key-link pairs at the root (root is a 2-node)\n",
    "- At least $M / 2$ key-link pairs in other nodes\n",
    "- External nodes contain client keys\n",
    "- Internal nodes contain copies of keys to guide search\n",
    "\n",
    "B-trees are widely used as system symbol tables or for file systems and databases.\n",
    "\n",
    "### Searching a B-Tree\n",
    "\n",
    "To search a B-tree, start at the root, then find the interval for the search key and take the corresponding link, and the search terminates in an external node.\n",
    "\n",
    "### Inserting into a B-Tree\n",
    "\n",
    "To insert into a B-tree, first search for the new key, then insert at the bottom, finally split nodes with $M$ key-link pairs on the way up the tree.\n",
    "\n",
    "### Balance in a B-Tree\n",
    "\n",
    "The proposition is that a search or insertion in a B-tree of order $M$ with $N$ keys requires between $\\log_{M-1}N$ and $\\log_{M/2}N$ probes. The proof is that all internal nodes have between $M/2$ and $M - 1$ links. In practice, the number of probes is at most 4: $M = 1024$, $N = 62 \\text{ billion}$, so $\\log_{M/2}N \\leq 4$. The optimization is to always keep the root page in memory."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Geometric Applications of BSTs\n",
    "\n",
    "One application of symbol trees and the binary search tree data structure is processing geometric data. It uses geometric objects instead of simple keys like integers or strings.\n",
    "\n",
    "### 1D Range Search\n",
    "\n",
    "There are many applications for finding how many points in a rectangle (\"2D orthogonal range search\") or how many rectangles intersect (\"orthogonal rectangle intersection\"), such as CAD, games, movies, virtual reality, or databases.\n",
    "\n",
    "**1D Range Search** is an extension of the ordered symbol table. The necessary operations are to *insert* a key-value pair, *search* for key $k$, *delete* key $k$, a *range search* to find all keys between $k_1$ and $k_2$, and a *range count* to get the number of keys between $k_1$ and $k_2$. A common application is database queries.\n",
    "\n",
    "The geometric interpretation is that keys are points on a line, and you find or count the points in a given 1d interval.\n",
    "\n",
    "**Implementations:**\n",
    "- Unordered array: fast insert, slow range search (need to go through all the keys to see whether they're in the range)\n",
    "- Ordered array: slow insert, binary search for $k_1$ and $k_2$ to do range search\n",
    "\n",
    "| Data Structure | Insert | Range Count | Range Search |\n",
    "| --- | --- | --- | --- |\n",
    "| Unordered Array | 1 | $N$ | $N$ |\n",
    "| Ordered Array | $N$ | $\\log N$ | $R + \\log N$ |\n",
    "| Goal | $\\log N$ | $\\log N$ | $R + \\log N$ |\n",
    "*$N$ is number of keys and $R$ is number of keys that match*\n",
    "\n",
    "**The BST implementation for 1D range count:**\n",
    "\n",
    "```py\n",
    "def size(lo, hi):\n",
    "    # Check if the tree contains hi to include that key in count\n",
    "    if (contains(hi)):\n",
    "        return rank(hi) - rank(lo) + 1\n",
    "    else:\n",
    "        return rank(hi) - rank(lo)\n",
    "```\n",
    "\n",
    "This running time is proportional to $\\log N$, proof is that the nodes examined are equal to the search path to `lo` plus the search path to `hi`.\n",
    "\n",
    "**The BST implementation for 1D range search:**\n",
    "\n",
    "It's a recursive search where you first find all keys in the left subtree (if any fall in the range), check the current node, then recursively find all the keys in the right subtree (if any fall in the range). The running time is proportional to $R + \\log N$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Line Segment Intersection\n",
    "\n",
    "**Orthogonal line segment intersection search** is when you find all intersections given $N$ horizontal and vertical line segments.\n",
    "\n",
    "The naive brute force algorithm checks all pairs of line segments for intersection and operates in quadratic time.\n",
    "\n",
    "One assumption for the code is the *nondegeneracy assumption* - all $x$ and $y$ coordinates are distinct.\n",
    "\n",
    "The **sweep-line algorithm** basically sweeps a vertical line from left to right:\n",
    "\n",
    "- $x$-coordinates define events\n",
    "- $h$-segment (hit the left endpoint of a horizontal segment): insert $y$-coordinate into BST\n",
    "- $h$-segment (hit the right endpoint of a horizontal segment): remove $y$-coordinate from BST (that horizontal segment has been processed and no intersections found)\n",
    "- hit a $v$-segment: do a range search for the interval of $y$'s endpoints (any horizontal line segments $x$ coordinate will be in the BST, so any intersections will return in the range search)\n",
    "\n",
    "The sweep-line algorithm takes time proportional to $N \\log N + R$ to find all $R$ intersections among $N$ orthogonal line segments. The algorithm reduces 2D orthogonal line segment intersection search to 1D range search."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### KD-Trees\n",
    "\n",
    "How to efficiently process sets of points in space - need 2D keys.\n",
    "\n",
    "**2D orthogonal range search** uses an extension of the ordered symbol table to 2D keys. It has the same functionality with insert, delete, and search for 2D keys, as well as range search (find all keys that lie in a 2D range) and range count (the number of those keys).\n",
    "\n",
    "The geometric interpretation is that all keys are points in a plane and you want to find or count the number of points in a given $h$-$v$ rectangle. Some common applications are in networking, circuit design, and databases.\n",
    "\n",
    "**Grid implementation:**\n",
    "\n",
    "- Divide space into $M$-by-$M$ grid of squares\n",
    "- Create list of points contained in each square\n",
    "- Use 2D array to directly index relevant square\n",
    "- Insert: add $(x, y)$ to list for corresponding square\n",
    "- Range search: examine only squares that intersect 2D range query\n",
    "\n",
    "There's a space-time tradeoff - space is $M^2 + N$ and time is $1 + N/M^2$ per square examined, on average. Want to choose a square size to balance performance (too small wastes space, too large too many points per square). Rule of thumb is $\\sqrt N$-by-$\\sqrt N$ grid. This is a fast, simple solution for evenly-distributed points.\n",
    "\n",
    "Points are usually NOT evenly distributed in geometric applications, they're usually **clustered**. The average list is short, but some are long.\n",
    "\n",
    "**2D Trees**\n",
    "\n",
    "One adaptation to address geometric data clustering is to use **space-partitioning trees** that represent a recursive subdivision of 2D space. The grid divides space uniformly into squares, the **2D tree** recursively divides space into two half-planes, a **quadtree** recursively divides space into four quadrants, and a **BSP tree** recursively divides space into two regions.\n",
    "\n",
    "With a 2D tree, first point divides the plane vertically. The next two points are nodes under the first and divide the plane horizontally. Every level in the tree switches horizontal and vertical divisions. The data structure is like a BST, but it alternates using the $x$- and $y$-coordinates as keys. The search function gives the rectangle containing the point and the insert function further subdivides the plane.\n",
    "\n",
    "To find all points in a query axis-aligned rectangle:\n",
    "\n",
    "- Check if point in the node lies in the rectangle\n",
    "- Recursively search left/bottom trees (if any could fall in rectangle)\n",
    "- Recursively search right/top (if any could fall in rectangle)\n",
    "- If the splitting line hits the rectangle, you have to check both branches\n",
    "\n",
    "Another function is to find the nearest neighbor:\n",
    "\n",
    "- Check distance from point in node to query point\n",
    "- Recursively search left/bottom trees (if contains closer point)\n",
    "- Recursively search right/top (if contains closer point)\n",
    "- Organize method so that it begins by searching for query point\n",
    "\n",
    "A typical case is $\\log N$ but the worst case (even if the tree is balanced) is $N$ (all points in a circle and query point is in the center).\n",
    "\n",
    "A fun phenomenon in nature to model is how birds (or a school of fish or swarm of insects) behave in a mass group. The **flocking boids** model does this:\n",
    "\n",
    "- Collision avoidance: point away from *k nearest* boids\n",
    "- Flock centering: point towards the center of mass of *k nearest* boids\n",
    "- Velocity matching: update velocity to the average of *k nearest* boids\n",
    "\n",
    "Shows that 2D trees can efficiently process a lot of information. Also, they can expand to more dimensions, just recursively partition $k$-dimensional space into 2 half-spaces. This is a $k$-dimensional model, or a **KD tree**.\n",
    "\n",
    "**KD tree** recursively partitions $k$-dimensional space into 2 half-spaces. The implementation is to still use a BST, but cycle through dimensions (like the 2D tree switched between horizontal and vertical levels) - the left subtree has points whose $i^{th}$ coordinate is less than the node point and the right subtree has points whose $i^{th}$ coordinate is greater than the node point.\n",
    "\n",
    "One similar application is the $N$-body simulation in physics problems (how do a large number of particles behave when affected by same gravitational forces)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Interval Search Trees\n",
    "\n",
    "**Interval search trees** are another extension of geometric algorithms to process complex objects - this time it's an interval.\n",
    "\n",
    "**1D interval search:** a data structure that holds a set of (overlapping) intervals. In 1D, that's a line segment from a `lo` to a `hi`\n",
    "\n",
    "- Insert an interval `(lo, hi)`\n",
    "- Search for an interval `(lo, hi)`\n",
    "- Delete an interval `(lo, hi)`\n",
    "- *Interval intersection query:* given an interval `(lo, hi)`, find all intervals (or one interval) in the data structure that intersects `(lo, hi)`\n",
    "\n",
    "**Implementation:**\n",
    "\n",
    "The implementation makes the *non-degeneracy assumption* that no two intervals have the same left endpoint. First, create a BST, where each node stores an interval `(lo, hi)`, and use the left endpoint as the BST key. After inserting the root node, every new node inserted with a left endpoint less than the root node's left endpoint goes in the left subtree, everything else goes in the right subtree.\n",
    "\n",
    "At each node, you also store the **max endpoint** in the subtree rooted at that node. In general, look at all the right endpoints in the subtree (including the one at the node you're at) and save the largest value. In practice, since you're saving this info at each node, you only need to look at the max stored in the left and right subnodes and the current node's endpoint, and take the max of those.\n",
    "\n",
    "When you **insert** a node `(lo, hi)`, use `lo` as the search key, insert as needed in the BST, then move up the tree to update the max in each node on the search path.\n",
    "\n",
    "**Search** looks for any one interval that intersect the query interval `(lo, hi)`:\n",
    "\n",
    "- If interval in node intersects query interval, return it\n",
    "- Else if left subtree is null, go right\n",
    "- Else if max endpoint in left subtree is less than `lo` (the largest `hi` value in the left subtree is still less than the `lo` value of the interval so there can't be an intersection), go right\n",
    "- Else go left"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Rectangle Intersection\n",
    "\n",
    "**Orthogonal rectangle intersection search's** goal is to find all intersections among a set of $N$ orthogonal rectangles. The brute force quadratic algorithm checks all pairs of rectangles for intersection, but is too inefficient for large sets of rectangles. This problem uses the non-degeneracy assumption that all $x-$ and $y-$coordinates are distinct.\n",
    "\n",
    "A major practical application came up in the 1970's when microprocessor design became a geometric problem - with the increasing power and complexity of chips, designers had to start using a computer. You can't put certain wires near each other and can't have certain components intersect.\n",
    "\n",
    "They needed an efficient solution to be able to design more complex chips and take advantage of Moore's Law (doubling computer speed every ~18 months). The quadratic algorithm lost time running analysis as chip components increased, even with twice as powerful computers. A version of the sweep-line algorithm was more efficient and capable of taking advantage of Moore's Law:\n",
    "\n",
    "- $x$-coordinates of left and right endpoints define events\n",
    "- Maintain set of rectangles that intersect the sweep line in an interval search tree (using $y-$ intervals of rectangle)\n",
    "- Left endpoint: interval search for $y-$interval of rectangle; insert $y-$interval\n",
    "- Right endpoint: remove $y-$interval\n",
    "\n",
    "The algorithm's worst-case run time to find all $R$ intersections among $n$ rectangles is $n \\log N + R \\log n$."
   ]
  }
 ],
 "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}