day 76 - 2-3 tree.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from bokeh.plotting import figure, show, output_notebook\n",
    "from bokeh.io import push_notebook\n",
    "from time import sleep"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, value, left=None, right=None, red=False):\n",
    "        self.value = value\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.red = red\n",
    "\n",
    "    @staticmethod\n",
    "    def red(node):\n",
    "        return node and node.red\n",
    "\n",
    "    def rotate_left(self):\n",
    "        if not Node.red(self.left) and Node.red(self.right):\n",
    "            child = self.right\n",
    "            self.right, child.left = child.left, self\n",
    "            self.red, child.red = True, self.red\n",
    "            return child\n",
    "        else:\n",
    "            return self\n",
    "\n",
    "    def rotate_right(self):\n",
    "        if Node.red(self.left) and Node.red(self.left.left):\n",
    "            child = self.left\n",
    "            self.left, child.right = child.right, self\n",
    "            self.red, child.red = True, self.red\n",
    "            return child\n",
    "        else:\n",
    "            return self\n",
    "    \n",
    "    def flip_colors(self):\n",
    "        if Node.red(self.left) and Node.red(self.right):\n",
    "            self.red, self.left.red, self.right.red = True, False, False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def insert(node, value, root=True):\n",
    "    if not node:\n",
    "        return Node(value, red=not root)\n",
    "    \n",
    "    # insert value\n",
    "    if value == node.value:\n",
    "        pass\n",
    "    elif value < node.value:\n",
    "        node.left = insert(node.left, value, root=False)\n",
    "    else:\n",
    "        node.right = insert(node.right, value, root=False)\n",
    "    \n",
    "    # update tree w.r.t invariants\n",
    "    node = node.rotate_left()\n",
    "    node = node.rotate_right()\n",
    "    node.flip_colors()\n",
    "\n",
    "    # keep root black\n",
    "    if root:\n",
    "        node.red = False\n",
    "\n",
    "    return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def draw(node, red, black, xlo=0, xhi=1, x=.5, y=0):\n",
    "    if node:\n",
    "        x_, y_ = (xlo + xhi) / 2, y - 1\n",
    "        (red if node.red else black).append([x, y, x_, y_])\n",
    "        draw(node.left, red, black, xlo, x_, x_, y_)\n",
    "        draw(node.right, red, black, x_, xhi, x_, y_)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## run"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# insert few values\n",
    "root = None\n",
    "for i in range(5):\n",
    "    root = insert(root, i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "    <div class=\"bk-root\">\n",
       "        <a href=\"http://bokeh.pydata.org\" target=\"_blank\" class=\"bk-logo bk-logo-small bk-logo-notebook\"></a>\n",
       "        <span id=\"a9a47e6b-6413-432b-b807-c046ca5ab7d7\">Loading BokehJS ...</span>\n",
       "    </div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/javascript": [
       "\n",
       "(function(global) {\n",
       "  function now() {\n",
       "    return new Date();\n",
       "  }\n",
       "\n",
       "  var force = true;\n",
       "\n",
       "  if (typeof (window._bokeh_onload_callbacks) === \"undefined\" || force === true) {\n",
       "    window._bokeh_onload_callbacks = [];\n",
       "    window._bokeh_is_loading = undefined;\n",
       "  }\n",
       "\n",
       "\n",
       "  \n",
       "  if (typeof (window._bokeh_timeout) === \"undefined\" || force === true) {\n",
       "    window._bokeh_timeout = Date.now() + 5000;\n",
       "    window._bokeh_failed_load = false;\n",
       "  }\n",
       "\n",
       "  var NB_LOAD_WARNING = {'data': {'text/html':\n",
       "     \"<div style='background-color: #fdd'>\\n\"+\n",
       "     \"<p>\\n\"+\n",
       "     \"BokehJS does not appear to have successfully loaded. If loading BokehJS from CDN, this \\n\"+\n",
       "     \"may be due to a slow or bad network connection. Possible fixes:\\n\"+\n",
       "     \"</p>\\n\"+\n",
       "     \"<ul>\\n\"+\n",
       "     \"<li>re-rerun `output_notebook()` to attempt to load from CDN again, or</li>\\n\"+\n",
       "     \"<li>use INLINE resources instead, as so:</li>\\n\"+\n",
       "     \"</ul>\\n\"+\n",
       "     \"<code>\\n\"+\n",
       "     \"from bokeh.resources import INLINE\\n\"+\n",
       "     \"output_notebook(resources=INLINE)\\n\"+\n",
       "     \"</code>\\n\"+\n",
       "     \"</div>\"}};\n",
       "\n",
       "  function display_loaded() {\n",
       "    if (window.Bokeh !== undefined) {\n",
       "      var el = document.getElementById(\"a9a47e6b-6413-432b-b807-c046ca5ab7d7\");\n",
       "      el.textContent = \"BokehJS \" + Bokeh.version + \" successfully loaded.\";\n",
       "    } else if (Date.now() < window._bokeh_timeout) {\n",
       "      setTimeout(display_loaded, 100)\n",
       "    }\n",
       "  }\n",
       "\n",
       "  function run_callbacks() {\n",
       "    window._bokeh_onload_callbacks.forEach(function(callback) { callback() });\n",
       "    delete window._bokeh_onload_callbacks\n",
       "    console.info(\"Bokeh: all callbacks have finished\");\n",
       "  }\n",
       "\n",
       "  function load_libs(js_urls, callback) {\n",
       "    window._bokeh_onload_callbacks.push(callback);\n",
       "    if (window._bokeh_is_loading > 0) {\n",
       "      console.log(\"Bokeh: BokehJS is being loaded, scheduling callback at\", now());\n",
       "      return null;\n",
       "    }\n",
       "    if (js_urls == null || js_urls.length === 0) {\n",
       "      run_callbacks();\n",
       "      return null;\n",
       "    }\n",
       "    console.log(\"Bokeh: BokehJS not loaded, scheduling load and callback at\", now());\n",
       "    window._bokeh_is_loading = js_urls.length;\n",
       "    for (var i = 0; i < js_urls.length; i++) {\n",
       "      var url = js_urls[i];\n",
       "      var s = document.createElement('script');\n",
       "      s.src = url;\n",
       "      s.async = false;\n",
       "      s.onreadystatechange = s.onload = function() {\n",
       "        window._bokeh_is_loading--;\n",
       "        if (window._bokeh_is_loading === 0) {\n",
       "          console.log(\"Bokeh: all BokehJS libraries loaded\");\n",
       "          run_callbacks()\n",
       "        }\n",
       "      };\n",
       "      s.onerror = function() {\n",
       "        console.warn(\"failed to load library \" + url);\n",
       "      };\n",
       "      console.log(\"Bokeh: injecting script tag for BokehJS library: \", url);\n",
       "      document.getElementsByTagName(\"head\")[0].appendChild(s);\n",
       "    }\n",
       "  };var element = document.getElementById(\"a9a47e6b-6413-432b-b807-c046ca5ab7d7\");\n",
       "  if (element == null) {\n",
       "    console.log(\"Bokeh: ERROR: autoload.js configured with elementid 'a9a47e6b-6413-432b-b807-c046ca5ab7d7' but no matching script tag was found. \")\n",
       "    return false;\n",
       "  }\n",
       "\n",
       "  var js_urls = [\"https://cdn.pydata.org/bokeh/release/bokeh-0.12.5.min.js\", \"https://cdn.pydata.org/bokeh/release/bokeh-widgets-0.12.5.min.js\"];\n",
       "\n",
       "  var inline_js = [\n",
       "    function(Bokeh) {\n",
       "      Bokeh.set_log_level(\"info\");\n",
       "    },\n",
       "    \n",
       "    function(Bokeh) {\n",
       "      \n",
       "    },\n",
       "    \n",
       "    function(Bokeh) {\n",
       "      \n",
       "      document.getElementById(\"a9a47e6b-6413-432b-b807-c046ca5ab7d7\").textContent = \"BokehJS is loading...\";\n",
       "    },\n",
       "    function(Bokeh) {\n",
       "      console.log(\"Bokeh: injecting CSS: https://cdn.pydata.org/bokeh/release/bokeh-0.12.5.min.css\");\n",
       "      Bokeh.embed.inject_css(\"https://cdn.pydata.org/bokeh/release/bokeh-0.12.5.min.css\");\n",
       "      console.log(\"Bokeh: injecting CSS: https://cdn.pydata.org/bokeh/release/bokeh-widgets-0.12.5.min.css\");\n",
       "      Bokeh.embed.inject_css(\"https://cdn.pydata.org/bokeh/release/bokeh-widgets-0.12.5.min.css\");\n",
       "    }\n",
       "  ];\n",
       "\n",
       "  function run_inline_js() {\n",
       "    \n",
       "    if ((window.Bokeh !== undefined) || (force === true)) {\n",
       "      for (var i = 0; i < inline_js.length; i++) {\n",
       "        inline_js[i](window.Bokeh);\n",
       "      }if (force === true) {\n",
       "        display_loaded();\n",
       "      }} else if (Date.now() < window._bokeh_timeout) {\n",
       "      setTimeout(run_inline_js, 100);\n",
       "    } else if (!window._bokeh_failed_load) {\n",
       "      console.log(\"Bokeh: BokehJS failed to load within specified timeout.\");\n",
       "      window._bokeh_failed_load = true;\n",
       "    } else if (force !== true) {\n",
       "      var cell = $(document.getElementById(\"a9a47e6b-6413-432b-b807-c046ca5ab7d7\")).parents('.cell').data().cell;\n",
       "      cell.output_area.append_execute_result(NB_LOAD_WARNING)\n",
       "    }\n",
       "\n",
       "  }\n",
       "\n",
       "  if (window._bokeh_is_loading === 0) {\n",
       "    console.log(\"Bokeh: BokehJS loaded, going straight to plotting\");\n",
       "    run_inline_js();\n",
       "  } else {\n",
       "    load_libs(js_urls, function() {\n",
       "      console.log(\"Bokeh: BokehJS plotting callback run at\", now());\n",
       "      run_inline_js();\n",
       "    });\n",
       "  }\n",
       "}(this));"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "\n",
       "\n",
       "    <div class=\"bk-root\">\n",
       "        <div class=\"bk-plotdiv\" id=\"ca4eb2b8-c88c-4939-a230-5423bb145dd1\"></div>\n",
       "    </div>\n",
       "<script type=\"text/javascript\">\n",
       "  \n",
       "  (function(global) {\n",
       "    function now() {\n",
       "      return new Date();\n",
       "    }\n",
       "  \n",
       "    var force = false;\n",
       "  \n",
       "    if (typeof (window._bokeh_onload_callbacks) === \"undefined\" || force === true) {\n",
       "      window._bokeh_onload_callbacks = [];\n",
       "      window._bokeh_is_loading = undefined;\n",
       "    }\n",
       "  \n",
       "  \n",
       "    \n",
       "    if (typeof (window._bokeh_timeout) === \"undefined\" || force === true) {\n",
       "      window._bokeh_timeout = Date.now() + 0;\n",
       "      window._bokeh_failed_load = false;\n",
       "    }\n",
       "  \n",
       "    var NB_LOAD_WARNING = {'data': {'text/html':\n",
       "       \"<div style='background-color: #fdd'>\\n\"+\n",
       "       \"<p>\\n\"+\n",
       "       \"BokehJS does not appear to have successfully loaded. If loading BokehJS from CDN, this \\n\"+\n",
       "       \"may be due to a slow or bad network connection. Possible fixes:\\n\"+\n",
       "       \"</p>\\n\"+\n",
       "       \"<ul>\\n\"+\n",
       "       \"<li>re-rerun `output_notebook()` to attempt to load from CDN again, or</li>\\n\"+\n",
       "       \"<li>use INLINE resources instead, as so:</li>\\n\"+\n",
       "       \"</ul>\\n\"+\n",
       "       \"<code>\\n\"+\n",
       "       \"from bokeh.resources import INLINE\\n\"+\n",
       "       \"output_notebook(resources=INLINE)\\n\"+\n",
       "       \"</code>\\n\"+\n",
       "       \"</div>\"}};\n",
       "  \n",
       "    function display_loaded() {\n",
       "      if (window.Bokeh !== undefined) {\n",
       "        var el = document.getElementById(\"ca4eb2b8-c88c-4939-a230-5423bb145dd1\");\n",
       "        el.textContent = \"BokehJS \" + Bokeh.version + \" successfully loaded.\";\n",
       "      } else if (Date.now() < window._bokeh_timeout) {\n",
       "        setTimeout(display_loaded, 100)\n",
       "      }\n",
       "    }if ((window.Jupyter !== undefined) && Jupyter.notebook.kernel) {\n",
       "      comm_manager = Jupyter.notebook.kernel.comm_manager\n",
       "      comm_manager.register_target(\"b1d503c4-c1b2-4fbd-9039-315f5f05adc3\", function () {});\n",
       "    }\n",
       "  \n",
       "    function run_callbacks() {\n",
       "      window._bokeh_onload_callbacks.forEach(function(callback) { callback() });\n",
       "      delete window._bokeh_onload_callbacks\n",
       "      console.info(\"Bokeh: all callbacks have finished\");\n",
       "    }\n",
       "  \n",
       "    function load_libs(js_urls, callback) {\n",
       "      window._bokeh_onload_callbacks.push(callback);\n",
       "      if (window._bokeh_is_loading > 0) {\n",
       "        console.log(\"Bokeh: BokehJS is being loaded, scheduling callback at\", now());\n",
       "        return null;\n",
       "      }\n",
       "      if (js_urls == null || js_urls.length === 0) {\n",
       "        run_callbacks();\n",
       "        return null;\n",
       "      }\n",
       "      console.log(\"Bokeh: BokehJS not loaded, scheduling load and callback at\", now());\n",
       "      window._bokeh_is_loading = js_urls.length;\n",
       "      for (var i = 0; i < js_urls.length; i++) {\n",
       "        var url = js_urls[i];\n",
       "        var s = document.createElement('script');\n",
       "        s.src = url;\n",
       "        s.async = false;\n",
       "        s.onreadystatechange = s.onload = function() {\n",
       "          window._bokeh_is_loading--;\n",
       "          if (window._bokeh_is_loading === 0) {\n",
       "            console.log(\"Bokeh: all BokehJS libraries loaded\");\n",
       "            run_callbacks()\n",
       "          }\n",
       "        };\n",
       "        s.onerror = function() {\n",
       "          console.warn(\"failed to load library \" + url);\n",
       "        };\n",
       "        console.log(\"Bokeh: injecting script tag for BokehJS library: \", url);\n",
       "        document.getElementsByTagName(\"head\")[0].appendChild(s);\n",
       "      }\n",
       "    };var element = document.getElementById(\"ca4eb2b8-c88c-4939-a230-5423bb145dd1\");\n",
       "    if (element == null) {\n",
       "      console.log(\"Bokeh: ERROR: autoload.js configured with elementid 'ca4eb2b8-c88c-4939-a230-5423bb145dd1' but no matching script tag was found. \")\n",
       "      return false;\n",
       "    }\n",
       "  \n",
       "    var js_urls = [];\n",
       "  \n",
       "    var inline_js = [\n",
       "      function(Bokeh) {\n",
       "        (function() {\n",
       "          var fn = function() {\n",
       "            var docs_json = {\"7e51c6e8-3db5-42d4-8860-04923019c30f\":{\"roots\":{\"references\":[{\"attributes\":{\"formatter\":{\"id\":\"1184fbfb-19d8-4ee0-ae03-656a0d8cfb12\",\"type\":\"BasicTickFormatter\"},\"plot\":{\"id\":\"2740cf73-4c85-44b5-ad78-c42d9796781f\",\"subtype\":\"Figure\",\"type\":\"Plot\"},\"ticker\":{\"id\":\"6bd1273f-63f3-42c5-8139-2e105e4a6641\",\"type\":\"BasicTicker\"},\"visible\":false},\"id\":\"dbc6290f-6955-4852-a6b4-cad511e6cd85\",\"type\":\"LinearAxis\"},{\"attributes\":{\"callback\":null},\"id\":\"9c2e3e65-6b87-4a3e-a1c8-6383215ab78c\",\"type\":\"DataRange1d\"},{\"attributes\":{},\"id\":\"d85b42f1-7284-4426-8480-47490a4115cf\",\"type\":\"BasicTickFormatter\"},{\"attributes\":{\"line_color\":{\"value\":\"#ff0000\"},\"x0\":{\"field\":\"x0\"},\"x1\":{\"field\":\"x1\"},\"y0\":{\"field\":\"y0\"},\"y1\":{\"field\":\"y1\"}},\"id\":\"3fc1e127-5403-440b-b734-a5c2a78ad88a\",\"type\":\"Segment\"},{\"attributes\":{},\"id\":\"6bd1273f-63f3-42c5-8139-2e105e4a6641\",\"type\":\"BasicTicker\"},{\"attributes\":{},\"id\":\"17f3176f-3ce0-437b-9a8a-c47b1abec61e\",\"type\":\"ToolEvents\"},{\"attributes\":{\"line_alpha\":{\"value\":0.1},\"line_color\":{\"value\":\"#1f77b4\"},\"x0\":{\"field\":\"x0\"},\"x1\":{\"field\":\"x1\"},\"y0\":{\"field\":\"y0\"},\"y1\":{\"field\":\"y1\"}},\"id\":\"223cf30f-613c-4e47-9728-14b8fccdcb13\",\"type\":\"Segment\"},{\"attributes\":{\"below\":[{\"id\":\"dbc6290f-6955-4852-a6b4-cad511e6cd85\",\"type\":\"LinearAxis\"}],\"left\":[{\"id\":\"b7576116-17be-43c8-a069-5342bdb5caa9\",\"type\":\"LinearAxis\"}],\"plot_height\":400,\"plot_width\":800,\"renderers\":[{\"id\":\"dbc6290f-6955-4852-a6b4-cad511e6cd85\",\"type\":\"LinearAxis\"},{\"id\":\"9444601f-87e7-479c-b342-26cc3f3a5f31\",\"type\":\"Grid\"},{\"id\":\"b7576116-17be-43c8-a069-5342bdb5caa9\",\"type\":\"LinearAxis\"},{\"id\":\"719a9652-74e3-44e4-bfd8-bf0fcec9f0b9\",\"type\":\"Grid\"},{\"id\":\"f110b8ed-f6e2-46ed-84f0-48272ce8a52f\",\"type\":\"BoxAnnotation\"},{\"id\":\"1f1a7570-98c1-4001-82be-471b05c3d83f\",\"type\":\"GlyphRenderer\"},{\"id\":\"519b46ad-0429-483f-9917-08ffe6b64bab\",\"type\":\"GlyphRenderer\"}],\"title\":{\"id\":\"29e1dc3c-0254-4696-833b-bcae83bd806f\",\"type\":\"Title\"},\"tool_events\":{\"id\":\"17f3176f-3ce0-437b-9a8a-c47b1abec61e\",\"type\":\"ToolEvents\"},\"toolbar\":{\"id\":\"c634a601-c49e-4bf8-b9e5-ec797e2fad58\",\"type\":\"Toolbar\"},\"x_range\":{\"id\":\"5d3143d4-8c4d-45a0-bfe9-bb641ea037e0\",\"type\":\"DataRange1d\"},\"y_range\":{\"id\":\"9c2e3e65-6b87-4a3e-a1c8-6383215ab78c\",\"type\":\"DataRange1d\"}},\"id\":\"2740cf73-4c85-44b5-ad78-c42d9796781f\",\"subtype\":\"Figure\",\"type\":\"Plot\"},{\"attributes\":{\"plot\":{\"id\":\"2740cf73-4c85-44b5-ad78-c42d9796781f\",\"subtype\":\"Figure\",\"type\":\"Plot\"}},\"id\":\"5e15ef77-1e78-4df8-92f8-0ad9f16afa10\",\"type\":\"WheelZoomTool\"},{\"attributes\":{\"callback\":null,\"column_names\":[\"x0\",\"y0\",\"x1\",\"y1\"],\"data\":{\"x0\":[0.5,0.25,0.25,0.5],\"x1\":[0.5,0.125,0.375,0.75],\"y0\":[0,-2,-2,-1],\"y1\":[-1,-3,-3,-2]}},\"id\":\"15c263c0-8247-4e8d-843b-86f8d86d86d8\",\"type\":\"ColumnDataSource\"},{\"attributes\":{\"overlay\":{\"id\":\"f110b8ed-f6e2-46ed-84f0-48272ce8a52f\",\"type\":\"BoxAnnotation\"},\"plot\":{\"id\":\"2740cf73-4c85-44b5-ad78-c42d9796781f\",\"subtype\":\"Figure\",\"type\":\"Plot\"}},\"id\":\"6c06f744-a38d-4801-a133-a93b8e638daf\",\"type\":\"BoxZoomTool\"},{\"attributes\":{\"callback\":null,\"column_names\":[\"x0\",\"y0\",\"x1\",\"y1\"],\"data\":{\"x0\":[0.5],\"x1\":[0.25],\"y0\":[-1],\"y1\":[-2]}},\"id\":\"22411456-0a7d-41a5-8733-cf4e161a001b\",\"type\":\"ColumnDataSource\"},{\"attributes\":{\"line_alpha\":{\"value\":0.1},\"line_color\":{\"value\":\"#1f77b4\"},\"x0\":{\"field\":\"x0\"},\"x1\":{\"field\":\"x1\"},\"y0\":{\"field\":\"y0\"},\"y1\":{\"field\":\"y1\"}},\"id\":\"89edead1-e95a-47ec-83fd-c7d726c935fc\",\"type\":\"Segment\"},{\"attributes\":{\"line_color\":{\"value\":\"#000000\"},\"x0\":{\"field\":\"x0\"},\"x1\":{\"field\":\"x1\"},\"y0\":{\"field\":\"y0\"},\"y1\":{\"field\":\"y1\"}},\"id\":\"2d51594f-d026-4c0c-8836-338e1c377ed2\",\"type\":\"Segment\"},{\"attributes\":{\"active_drag\":\"auto\",\"active_scroll\":\"auto\",\"active_tap\":\"auto\",\"tools\":[{\"id\":\"f598581b-3d89-43c3-a5dd-c98dbc54eb10\",\"type\":\"PanTool\"},{\"id\":\"5e15ef77-1e78-4df8-92f8-0ad9f16afa10\",\"type\":\"WheelZoomTool\"},{\"id\":\"6c06f744-a38d-4801-a133-a93b8e638daf\",\"type\":\"BoxZoomTool\"},{\"id\":\"1d0e5e11-532f-40d3-9eda-46315cb98c46\",\"type\":\"SaveTool\"},{\"id\":\"8d633754-3c54-4c62-852e-37125e262999\",\"type\":\"ResetTool\"},{\"id\":\"14c83e2b-0cb9-4f64-9b16-1e95ee5d7bb8\",\"type\":\"HelpTool\"}]},\"id\":\"c634a601-c49e-4bf8-b9e5-ec797e2fad58\",\"type\":\"Toolbar\"},{\"attributes\":{\"data_source\":{\"id\":\"15c263c0-8247-4e8d-843b-86f8d86d86d8\",\"type\":\"ColumnDataSource\"},\"glyph\":{\"id\":\"2d51594f-d026-4c0c-8836-338e1c377ed2\",\"type\":\"Segment\"},\"hover_glyph\":null,\"muted_glyph\":null,\"nonselection_glyph\":{\"id\":\"89edead1-e95a-47ec-83fd-c7d726c935fc\",\"type\":\"Segment\"},\"selection_glyph\":null},\"id\":\"519b46ad-0429-483f-9917-08ffe6b64bab\",\"type\":\"GlyphRenderer\"},{\"attributes\":{\"plot\":{\"id\":\"2740cf73-4c85-44b5-ad78-c42d9796781f\",\"subtype\":\"Figure\",\"type\":\"Plot\"}},\"id\":\"1d0e5e11-532f-40d3-9eda-46315cb98c46\",\"type\":\"SaveTool\"},{\"attributes\":{\"plot\":{\"id\":\"2740cf73-4c85-44b5-ad78-c42d9796781f\",\"subtype\":\"Figure\",\"type\":\"Plot\"}},\"id\":\"8d633754-3c54-4c62-852e-37125e262999\",\"type\":\"ResetTool\"},{\"attributes\":{\"plot\":{\"id\":\"2740cf73-4c85-44b5-ad78-c42d9796781f\",\"subtype\":\"Figure\",\"type\":\"Plot\"}},\"id\":\"14c83e2b-0cb9-4f64-9b16-1e95ee5d7bb8\",\"type\":\"HelpTool\"},{\"attributes\":{\"callback\":null},\"id\":\"5d3143d4-8c4d-45a0-bfe9-bb641ea037e0\",\"type\":\"DataRange1d\"},{\"attributes\":{\"plot\":null,\"text\":\"\"},\"id\":\"29e1dc3c-0254-4696-833b-bcae83bd806f\",\"type\":\"Title\"},{\"attributes\":{\"formatter\":{\"id\":\"d85b42f1-7284-4426-8480-47490a4115cf\",\"type\":\"BasicTickFormatter\"},\"plot\":{\"id\":\"2740cf73-4c85-44b5-ad78-c42d9796781f\",\"subtype\":\"Figure\",\"type\":\"Plot\"},\"ticker\":{\"id\":\"71250163-1cf2-46ca-9d88-b280f1871683\",\"type\":\"BasicTicker\"},\"visible\":false},\"id\":\"b7576116-17be-43c8-a069-5342bdb5caa9\",\"type\":\"LinearAxis\"},{\"attributes\":{\"plot\":{\"id\":\"2740cf73-4c85-44b5-ad78-c42d9796781f\",\"subtype\":\"Figure\",\"type\":\"Plot\"}},\"id\":\"f598581b-3d89-43c3-a5dd-c98dbc54eb10\",\"type\":\"PanTool\"},{\"attributes\":{\"plot\":{\"id\":\"2740cf73-4c85-44b5-ad78-c42d9796781f\",\"subtype\":\"Figure\",\"type\":\"Plot\"},\"ticker\":{\"id\":\"6bd1273f-63f3-42c5-8139-2e105e4a6641\",\"type\":\"BasicTicker\"},\"visible\":false},\"id\":\"9444601f-87e7-479c-b342-26cc3f3a5f31\",\"type\":\"Grid\"},{\"attributes\":{},\"id\":\"1184fbfb-19d8-4ee0-ae03-656a0d8cfb12\",\"type\":\"BasicTickFormatter\"},{\"attributes\":{\"dimension\":1,\"plot\":{\"id\":\"2740cf73-4c85-44b5-ad78-c42d9796781f\",\"subtype\":\"Figure\",\"type\":\"Plot\"},\"ticker\":{\"id\":\"71250163-1cf2-46ca-9d88-b280f1871683\",\"type\":\"BasicTicker\"},\"visible\":false},\"id\":\"719a9652-74e3-44e4-bfd8-bf0fcec9f0b9\",\"type\":\"Grid\"},{\"attributes\":{\"data_source\":{\"id\":\"22411456-0a7d-41a5-8733-cf4e161a001b\",\"type\":\"ColumnDataSource\"},\"glyph\":{\"id\":\"3fc1e127-5403-440b-b734-a5c2a78ad88a\",\"type\":\"Segment\"},\"hover_glyph\":null,\"muted_glyph\":null,\"nonselection_glyph\":{\"id\":\"223cf30f-613c-4e47-9728-14b8fccdcb13\",\"type\":\"Segment\"},\"selection_glyph\":null},\"id\":\"1f1a7570-98c1-4001-82be-471b05c3d83f\",\"type\":\"GlyphRenderer\"},{\"attributes\":{},\"id\":\"71250163-1cf2-46ca-9d88-b280f1871683\",\"type\":\"BasicTicker\"},{\"attributes\":{\"bottom_units\":\"screen\",\"fill_alpha\":{\"value\":0.5},\"fill_color\":{\"value\":\"lightgrey\"},\"left_units\":\"screen\",\"level\":\"overlay\",\"line_alpha\":{\"value\":1.0},\"line_color\":{\"value\":\"black\"},\"line_dash\":[4,4],\"line_width\":{\"value\":2},\"plot\":null,\"render_mode\":\"css\",\"right_units\":\"screen\",\"top_units\":\"screen\"},\"id\":\"f110b8ed-f6e2-46ed-84f0-48272ce8a52f\",\"type\":\"BoxAnnotation\"}],\"root_ids\":[\"2740cf73-4c85-44b5-ad78-c42d9796781f\"]},\"title\":\"Bokeh Application\",\"version\":\"0.12.5\"}};\n",
       "            var render_items = [{\"docid\":\"7e51c6e8-3db5-42d4-8860-04923019c30f\",\"elementid\":\"ca4eb2b8-c88c-4939-a230-5423bb145dd1\",\"modelid\":\"2740cf73-4c85-44b5-ad78-c42d9796781f\",\"notebook_comms_target\":\"b1d503c4-c1b2-4fbd-9039-315f5f05adc3\"}];\n",
       "            \n",
       "            Bokeh.embed.embed_items(docs_json, render_items);\n",
       "          };\n",
       "          if (document.readyState != \"loading\") fn();\n",
       "          else document.addEventListener(\"DOMContentLoaded\", fn);\n",
       "        })();\n",
       "      },\n",
       "      function(Bokeh) {\n",
       "      }\n",
       "    ];\n",
       "  \n",
       "    function run_inline_js() {\n",
       "      \n",
       "      if ((window.Bokeh !== undefined) || (force === true)) {\n",
       "        for (var i = 0; i < inline_js.length; i++) {\n",
       "          inline_js[i](window.Bokeh);\n",
       "        }if (force === true) {\n",
       "          display_loaded();\n",
       "        }} else if (Date.now() < window._bokeh_timeout) {\n",
       "        setTimeout(run_inline_js, 100);\n",
       "      } else if (!window._bokeh_failed_load) {\n",
       "        console.log(\"Bokeh: BokehJS failed to load within specified timeout.\");\n",
       "        window._bokeh_failed_load = true;\n",
       "      } else if (force !== true) {\n",
       "        var cell = $(document.getElementById(\"ca4eb2b8-c88c-4939-a230-5423bb145dd1\")).parents('.cell').data().cell;\n",
       "        cell.output_area.append_execute_result(NB_LOAD_WARNING)\n",
       "      }\n",
       "  \n",
       "    }\n",
       "  \n",
       "    if (window._bokeh_is_loading === 0) {\n",
       "      console.log(\"Bokeh: BokehJS loaded, going straight to plotting\");\n",
       "      run_inline_js();\n",
       "    } else {\n",
       "      load_libs(js_urls, function() {\n",
       "        console.log(\"Bokeh: BokehJS plotting callback run at\", now());\n",
       "        run_inline_js();\n",
       "      });\n",
       "    }\n",
       "  }(this));\n",
       "</script>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "output_notebook()\n",
    "\n",
    "# get plot data\n",
    "red, black = [], []\n",
    "draw(root, red, black)\n",
    "\n",
    "# plot\n",
    "plot = figure(plot_height=400, plot_width=800)\n",
    "plot.axis.visible = False\n",
    "plot.grid.visible = False\n",
    "\n",
    "red_segment = plot.segment(*zip(*red), color='#ff0000')\n",
    "black_segment = plot.segment(*zip(*black), color='#000000')\n",
    "\n",
    "handle = show(plot, notebook_handle=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for _ in range(100):\n",
    "    for i in np.random.randint(0, 1000, 5):\n",
    "        root = insert(root, i)\n",
    "\n",
    "    red, black = [], []\n",
    "    draw(root, red, black)\n",
    "\n",
    "    x0, y0, x1, y1 = red and zip(*red) or [tuple()] * 4\n",
    "    red_segment.data_source.data.update({\n",
    "        'x0': x0, 'y0': y0, 'x1': x1, 'y1': y1\n",
    "    })\n",
    "    x0, y0, x1, y1 = black and zip(*black) or [tuple()] * 4\n",
    "    black_segment.data_source.data.update({\n",
    "        'x0': x0, 'y0': y0, 'x1': x1, 'y1': y1\n",
    "    })\n",
    "\n",
    "    push_notebook()\n",
    "    sleep(.1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}