RedBlackBST.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Rot-Schwarz Bäume"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die Datenstruktur die wir nutzen um einen Rot-Schwarz Baum zu implementieren ist sehr ähnlich zu der Implementation von einem klassischen Binären Suchbaum. Im Vergleich zum Binärbaum benötigen wir aber das zusätzliches Feld ```color``` in jedem Knoten um die Farbe zu speichern. Wir definieren uns dafür den Datentyp ```Color```, der die Farbe Rot und Schwarz repräsentieren kann. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from enum import Enum\n",
    "class Color(Enum):\n",
    "        RED = 1\n",
    "        BLACK = 2\n",
    "        \n",
    "        @staticmethod\n",
    "        def flipColor(color):\n",
    "            if color == Color.RED:\n",
    "                return Color.BLACK\n",
    "            else:\n",
    "                return Color.RED"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die Methoden ```size```, ```isEmpty```, ```contains``` und ```get``` können wir direkt vom vom binären Suchbaum übernehmen. Die Unterschiede kommen nur zum Tragen, wenn wir den Baum verändern, d.h. Knoten einfügen oder löschen. Wir zeigen hier nur die Methode ```put```. Beachten Sie, wie nach dem Einfügen eines Knotens die Methoden ```rotateLeft```, ```rotateRight```und ```flipColors``` verwendet werden, um sicherzustellen, dass wir wieder einen gültigen Rot-Schwarz Baum bekommen. *Diese Operationen werden durch die Rekursion auf jedem Elternknoten durchgeführt*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class RedBlackBST:\n",
    "\n",
    "    class Node:\n",
    "        def __init__(self, key, value, color, count = 1):\n",
    "            self.key = key\n",
    "            self.value = value\n",
    "            self.count = count\n",
    "            self.left = None\n",
    "            self.right = None\n",
    "            self.color = color # color of parent link\n",
    "    \n",
    "    def __init__(self):\n",
    "        self._root = None\n",
    "\n",
    "  \n",
    "    def root(self) : return self._root;\n",
    "    \n",
    "    def size(self):\n",
    "        return self._size(self._root)\n",
    "    \n",
    "    def _size(self, root):\n",
    "        if (root == None):\n",
    "            return 0\n",
    "        else:\n",
    "            return root.count\n",
    "    \n",
    "    def isEmpty(self):\n",
    "        return self.size() == 0\n",
    "    \n",
    "    def contains(self, key):\n",
    "        return self.get(key) != None\n",
    "    \n",
    "    def get(self, key): \n",
    "        return self._get(key, self._root)\n",
    "    \n",
    "    def _get(self, key, node):\n",
    "        if node == None:\n",
    "            return None\n",
    "        elif key < node.key:\n",
    "            return self._get(key, node.left)\n",
    "        elif key > node.key:\n",
    "            return self._get(key, node.right)\n",
    "        elif key == node.key:\n",
    "            return node.value\n",
    "        else:\n",
    "            raise Exception(\"should never reach this line\")\n",
    "            \n",
    "    def put(self, key, value):\n",
    "        self._root = self._put(key, value, self._root)\n",
    "        self._root.color  = Color.BLACK;\n",
    "    \n",
    "    def _put(self, key, value, node):\n",
    "        if (node == None):\n",
    "            return RedBlackBST.Node(key, value, Color.RED, 1)\n",
    "        elif key < node.key:\n",
    "            node.left = self._put(key, value, node.left)\n",
    "        elif key > node.key:\n",
    "            node.right = self._put(key, value, node.right)\n",
    "        elif key == node.key:\n",
    "            node.value = value\n",
    "      \n",
    "        if self._isRed(node.right) and not self._isRed(node.left):\n",
    "            node = self._rotateLeft(node)\n",
    "        if self._isRed(node.left) and self._isRed(node.left.left):\n",
    "            node = self._rotateRight(node)\n",
    "        if self._isRed(node.left) and self._isRed(node.right):\n",
    "            self._flipColors(node)\n",
    " \n",
    "        node.count = 1 + self._size(node.left) + self._size(node.right)\n",
    " \n",
    "        return node\n",
    "         \n",
    "    def _rotateRight(self, node):\n",
    "        t = node.left;\n",
    "        node.left = t.right;\n",
    "        t.right = node;\n",
    "        t.color = t.right.color;\n",
    "        t.right.color = Color.RED;\n",
    "        t.count = node.count;\n",
    "        node.count = self._size(node.left) + self._size(node.right) + 1;\n",
    "        return t;\n",
    "\n",
    "    \n",
    "    def _rotateLeft(self, node):\n",
    "        t = node.right;\n",
    "        node.right = t.left;\n",
    "        t.left = node;\n",
    "        t.color = t.left.color;\n",
    "        t.left.color = Color.RED;\n",
    "        t.count = node.count;\n",
    "        node.count = self._size(node.left) + self._size(node.right) + 1;\n",
    "        return t;\n",
    " \n",
    "        \n",
    "        \n",
    "    def _flipColors(self, node):\n",
    "        \n",
    "        node.color = Color.flipColor(node.color);\n",
    "        node.left.color = Color.flipColor(node.left.color);\n",
    "        node.right.color = Color.flipColor(node.right.color);\n",
    "        return node\n",
    " \n",
    "    \n",
    "    def keys(self):\n",
    "        return self._keys(self._root)\n",
    "        \n",
    "    def _keys(self, node):        \n",
    "        if node == None:\n",
    "            return []\n",
    "        else:\n",
    "            nodesLeft = self._keys(node.left)            \n",
    "            nodesRight = self._keys(node.right)\n",
    "            return nodesLeft +[node.key] + nodesRight\n",
    "\n",
    "    def _isRed(self, node):\n",
    "        \n",
    "        if node == None:\n",
    "            return False\n",
    "        else:\n",
    "            return node.color == Color.RED\n",
    "        \n",
    "    def height(self):\n",
    "        return self._height(self._root)\n",
    "    \n",
    "    def _height(self, node):\n",
    "        if node == None:\n",
    "            return -1\n",
    "        else:\n",
    "            return 1 + max(self._height(node.left), self._height(node.right))   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Visualisierung"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wie bereits beim Binärbaum definieren wir uns die Methode ```plotTree``` um den Baum (diesmal inklusive Farben) zu visualisieren. Die Details der Implementation sind für das Verständnis vom Algorithmus nicht relevant. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "import matplotlib\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "class NodeWithId:\n",
    "    def __init__(self, key, value, color, id, left, right):\n",
    "        self.key = key\n",
    "        self.value = value\n",
    "        self.id = id\n",
    "        self.color = color\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        \n",
    "def _augmentTreeWithId( t, n):\n",
    "    if t == None:\n",
    "        return (None, n)\n",
    "    else:        \n",
    "        (leftNode, newN) = _augmentTreeWithId(t.left, n)\n",
    "        (rightNode, rightN) = _augmentTreeWithId(t.right, newN + 1)\n",
    "        return (NodeWithId(t.key, t.value, t.color, newN + 1, leftNode, rightNode), rightN )\n",
    "\n",
    "def _buildTreeGraph(g, t, parentNode, depth, showValues):\n",
    "    if t == None:\n",
    "        return\n",
    "    _buildTreeGraph(g, t.left, t, depth + 1, showValues)\n",
    "    label = \"\" \n",
    "    if showValues:\n",
    "        label = str((t.key, t.value))\n",
    "    else:\n",
    "        label = str(t.key)\n",
    "    g.add_node(t.id, pos=(t.id, -depth), label=label)\n",
    "    if (parentNode != None):\n",
    "        if t.color == Color.RED:\n",
    "            g.add_edge(t.id, parentNode.id, color='r')\n",
    "        else:\n",
    "            g.add_edge(t.id, parentNode.id, color='black')\n",
    "    _buildTreeGraph(g, t.right, t, depth + 1, showValues)\n",
    "\n",
    "def showTree(bst, showValues = False):\n",
    "    g = nx.Graph()\n",
    "    (tt, _) = _augmentTreeWithId(bst.root(), 0)\n",
    "    _buildTreeGraph(g, tt, None, 0,  showValues)\n",
    "    pos=nx.get_node_attributes(g,'pos')\n",
    "    labels = nx.get_node_attributes(g, 'label')\n",
    "    \n",
    "    edges = g.edges()\n",
    "    colors = [g[u][v]['color'] for u,v in edges]\n",
    "    nx.draw_networkx_nodes(g, pos, node_size=500, node_color='#00b4d9')\n",
    "    nx.draw_networkx_labels(g, pos, labels)\n",
    "    nx.draw_networkx_edges(g, pos, edge_color = colors, width=5.0,alpha=1.0)\n",
    "    plt.axis('off')\n",
    "    plt.show()\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Experimente"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "scrolled": true
   },
   "source": [
    "Als erstes zeigen wir wieder wie der Baum für verschiedene Sequenzen von Schlüsseln aussieht. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir beginnen mit unserem Standardbeispiel:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAADnCAYAAAC9roUQAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAgAElEQVR4nO2debhd09nAf29ubiYUiSCm3pLctKbWUFNQIrRyQ4hZqCSGhqCl/aqfKpJqq60iITFGQg1VmZBralA1FFV8ZtcUJBJTCHFzk9yT9/tj7Sv3nrvOfM7e+5zz/p4nz8Nee6/9ruG+Z+213kFUFcMwDCMcukQtgGEYRjVhStcwDCNETOkahmGEiCldwzCMEDGlaxiGESKmdA3DMELElK5hGEaIdI1aAMOoRKSxqStQB/QAWoD52lDfGqlQRiwQc44wjOIgjU19gDHAKKA/sBJYjfui7A68AUwHpmpD/ZJopDSixpSuYRSINDZ1Ay4AzsYp2V5pbm/GKeFLgfHaUL+y9BIaccKUrmEUgDQ2bQHMAzYlvbJNphlYCAzRhvr3SiGbEU9M6RpGngQK9xmgN1CTRxUJYAmwsyne6sGUrmHkQbCl8BKwJfkp3DYSwNvANtpQv6oYshnxxkzGDCM/LsBtKRSicAme3wQ4v2CJjLLAlK5h5EhgpXA26fZwxwyG55/Itsq1gF9IY1PvwqUz4o4pXcPInTE4K4Visjqo16hwTOkaRu6MIjdLhWzoFdRrVDimdA0jBwJPs/4lqn5AUL9RwZjSNYzcqMN5mpWCVUH9RgVjStcwcqMHxd/PbSMR1G9UMKZ0DSM3Wijd301NUL9RwZjSNYwcOPyx+97tsjqR3Wq0dRWsXLHmXyJjkLFaYH6BIhoxxzzSDCNbRHYHJm09pXHnV7fIcJY2ZjB8tLDjtaPGwvFnpXvqZW2o37ZAKY2YYyelhpEJkc2Ai4GRAKPnzeKCY89geY+eqZ+54aFc39IMTMtTQqOMsO0Fw0iFSE9Efg28TqBwAU58YAYqUuy3dcGUblVgStcwkhERRA4DXgEuIskRoveypZw9Zxq9WpqL877ViRbgEgtsXh3Ynq5htEdke+ByYN90t7XUdnuhz21P927u0bMfhQS9SbTCRx8kOG/01rr4/aa86zHKBlvpGgaAyAaITAGeI73C/RQY22PVyh2be/QchIuHm8jrnYlW+HIpnPvjGj5ccJeIWMCbKsCUrlHdiNQiciYuf9mppP6baMWtgAegeg2qiSDw+M64eLi57TW0NMPi9+Gsw+DjRQADgVki0j3Plhhlgildo3oR2R94HpgIrJfmzgeA7VE9C9XP2hcEindb4DKcY0Mm5duMagv33LaU04a1Kdw2fgBcJ1L8UzojPtierlF9iPQH/gIcnOHON4GzgEay+EMJ4uG2ZQMegIulkMDt+dbiVtPTgGkMG9gPeAL4hqeq8ap6YTZNMcoPU7pG9SCyDvBrnCLtlubOL4HfApNQXZHXq1y0sDpcLIUWYL421HdwSRORIcC9+O3lT1DVm/J5txFvTOkalY9IF+DHwB+AjdPcqbiV6K9RXRyOaDIGmOopWgUcoKr/DEMOIzxM6RqVTeC6izvwSscTwE9Rfab0QnVERH4HnOsp+hzYQ1VfDVkko4SY0jUqE5FNca67x2W4cyHwS+C2bPZtS4G4lfgtwNGe4neA3VT1o3ClMkqFKV2jshDpAfwct3JMl1JnBfBn4GJUvwpDtHSIk3seMMhT/BSwr6ouD1cqoxSY0jUqA2dmdSjOKqEuw90zgP9BdX6JpcoJEdkA+Df+dEAzgSNVtVQB1I2QMDtdo/xxrrsP4hRTXZo7XwD2RfWIuClcAFX9BBiK83pL5jDgj+FKZJQCU7pG+SLSB5HJZOe6eyqwEzG3BlDVN4BD8Odh+4WIjA1ZJKPI2PaCUX6I1AJjgfHA+mnuTABXAuOTPcnijogcDdzmKVoNDFPVe0MWySgSpnSN8sI5FEwEts5w5z+An6H6SumFKg0ici7wO0/RMmBPVf2/kEUyioApXaM8ENkKd0g2PMOdbwJnA3OjMgErFkEMhuuAEz3FC3GmZAvClcooFFO6RrwJ0XU3jojbSrkHGOIp/j9gL1X9MlypjEIwpWvEE+cwcDzOwSGd6y44191zw3LdDRsRWRd4HNjGU3wvcLCqZkw1bMQDs14w4ofIbjh71emkV7j/BnZBdUylKlwAVV0KNAC+Nh4ITLJwkOWDKV0jPohsgshNtCnT1HyAc+8dhOp/QpEtYlT1XWAY/ni9p+L2sY0ywLYXjOhxLrBn41x310pzZ5vr7h9RXRaGaHFDRA4G5gDJK1sFjlDVmeFLZeSCKV0jOnJz3Z2Jc919p9RixR1x6YUmeopagH1U9amQRTJywJSuEQ0i2+Fyjg3OcOeLuJCLD5deqPJBRCYCZ3qKPgZ2Vftxii2mdI1wEekDTMB5lKU7U/gUOA+4HjuZ74SI1ACz8Kcceg0Xh7esvPCqBVO6RjiIdMUp2glkdt2djHPdXRKGaOWKiKwFPALs5Cl+GPiRqvpiOBgRYkrXKD3Odfdy/Ham7Sl7192wEZF+wJPAFp7im4BRan/kscJMxozSIbIVInNwyjSdwn0L5977Q1O4uaGqi3A2vF94in8M/CZciYxM2ErXKD7OdfdcnBlYOtfdZTjX3YmV5LobBSKyP85d2JdZ+Meq+teQRTJSYErXKB7Odfc4nOtuvwx3T8e57i4qtVjVgoicCFzvKbLMwjHClK5RHER2xWXdTedJBm7/8cxq8SQLGxH5PfC/nqLPgd1V9bWQRTKSMKVrFIbIJriV7fEZ7vwAOAe4FcvzVTKCzMK3Akd5ii2zcAwwpWvkh3PdPQsXdjGT6+4luKy7Vem6GzYZMgs/CQy2zMLRYUrXyA3nunsIznX3WxnunoVz3X275HIZHbDMwvHFTMaM7BHZFmf+NYv0CvdFYD9UDzOFGw3tMgv7HEwOw20JGRFgStfIjMu6eyUuU8F+ae5cApwG7IjqQ6HIZqQkyCw8HH9m4f8RkZ+ELJKBbS8Y6cjNdXcKcKG57sYPETkGd7iWTAKXWfi+kEWqakzpGn5E9sOFD8zkujsP57r7cumFMvJFRH4NXOQpsszCIWNK1+iIy7p7Ce6wLB1v4TzO7i73rLvVQJDO53pgjKd4IS4c5MJwpapOTOkaDue6+7/Az8nsunsRcLm57pYXQWbhe/Hvyz8P7G2ZhUuPKd1qx1x3qwoRWQ+XWXhrT/E9wHDLLFxazHqhmnGuu08AN5Je4T4F7IrqaFO45Y2qfo4zJfvQUzwUmGiZhUuLKd1qxGXdvRHnnbRrmjs/wLn37oHq06HIZpScILPwQYDPK+00nKehUSJse6GayM119y/AH8x1t3IRkeHAbPyZhQ9T1dnhS1X5mNKtBtzn4nCcIt0yw93multFiMjPgMs8RctxmYXtC6fImNKNOdLY1BWXnrwHLsX2fG2oz/6gw7nuXk56TzKAl3D2tg/mJ6lRjgT7t5OA0z3FH+GiknXILFzwnKxyTOnGEGls6oOzpxyFC1iyEliN24PvDryBsySYqg31fg8wkd7AeOBUoCbN65bgUrpca1l3q5Mgs/AcYJin+FVgEHNf70Khc9IATOnGCmls6gZcgHM6WA30SnN7M27CXwqM14Z651/vXHd/gnPd7Z3m+QRwFXCBue4aIrI28C9ghw4FXWvhlF+/y4FHb4RIfnPS6IAp3ZggjU1b4FxqNyX9xE6mGedRNESHDeyPc93dNsMzD+K2El7KR1ajMhEXkP5JYHMA+vaDi6ZDnw2hRy5Tst2cbKh/r9hyljumdGNAoHCfwa1M020F+FFNrNu8rPWF0w/qvsXHac1o38Z5nN1prruGDxHZDnicvv3W4bKZsM66UOPLdZmRBG7ramdTvB0xpRsxwZbCSzirgtwVbkBNopUtF7/Py6cNozbRaWv2K9a47rbkLaxRFci6vYfy5781svFm+SrcNhK4H/pttKF+VXGkK3/MOSJ6LsBtKeStcAESNV1Z2Gcjxh8zLrnoJqAe1YtN4RpZceuTg9hos5UFKlxwc3oT4PzChaocbKUbIYGVwgKc6U1R6LGihYUn7E3vZUufxmXdfapYdRuVTynmJM6sbFOzanAU/FNmFMQYnJWCp2QwfP4J1NRAlxrYvD8MHg4/Ogq6pP5AEdBRZ138t7t+e+pxlnXXyIPUcxLWzMsuNe5wbae9YOxvoGc6B0dWB/VeUlxRyxPbXoiWUaSzVDj/arjjObjhYTjiZJh5HUz6ddoKl3fvIXfvOnh7U7hGnowik/XM+VfDjOfgijnw1itwx7WZ6uwV1GtgSjcyAq8eX6bWzqy1Duy6H/zycnhwNsxvyvTEgKB+w8ianOYkwPp9Ycc94e1Xs7nb5mSAKd3oqMOfMDA1A7eHDTaGV57JdOeqoH7DyIU6cpmTnyyG/z4K/bbI5m6bkwH2yxMdPUi3d5aK3hvCl0sz3ZWguAchRnWQ3Zy8aJyLS7a8GbbfDUaemU3dNicDbKUbHS3k0/+ffugM1tNTE9RvGLmQ3Zw8b7I7a/jDX2HB2/DFZ9nUbXMywJRudMwnfS6yzjS94JTu1jtlurM2qN8wcmE+uczJ7XaBISPghj9mc7fNyQBTuhERhMJ7M6ubm5fB0w/Dn86GfQ6GuoGZnnjDQu0ZuZLTnGxj+Anw3BPZHKbZnAwwpRst03HBQfxMGAtH7ACjfgC3Xw2HjIaf/SFTnc3AtOKJaFQZ00k3J5NZt7ezH//blHR32Zxsh3mkRYg0NvXGRWMy7x8jFticLD220o0QbahfQvOyyaxoKZYjQzNwiU1uI1+CuXMpuax201aoNieTMKUbISJSy8jdv8sni7vQOTJYbiRa4culX+GClxtGIYzHrXYTBdWSaIVlNieTMaUbEUFuqimsWjmE80Y529t8Fa9TuHDm8D4MG/ijYsppVB9BxochwBJWr87vK+zrOXnIBgwb6EsDVLWY0o2Oc4CTAPh4EZx1GCxeAC3Lc6ulpRkWv++e/3hRF+BvIpLRpsww0qEN9e+xdMkufLQwQUuOOw0d56QAt4jILiURtAyxg7QIEJGjgL91Kuhau5o/3noHA7cfTqYcaarNJFq7M+O6Gm6bnLxKXgzsqqoWsd/IGxE5mK61d3LMOGc5owo9eqZ+IP2c/Ag3J+eXVur4Y0o3ZERkEC5HWXdP8WmqelVwgtyWeXUAzm89gfPqqcVlXp3Gu003Me6gG4EDPXW9BOypqhl9hg3Dh4jMA/YDYO11Yf/DYNjIZWy0WTfSz8lpQIOnyleBPVT181AaEFNM6YaIiPTHJf7r4yn+i6r+otMzLjJTHc6EpwWY397IXETWAR4Fvuup8x9Ag6paqhQjJ0RkW+BFT9GBzH19HunnpD+zsOMh4EBVrdpMwaZ0Q0JE+gD/xq1ck5kFHKF5xsAVkc2Ap3CpUZK5HjhFbaCNHBCRa4BTki43Ad/JZp4GmYWfAjbzFE8HxlTrnLSDtBAQke7AbPwK92ng+HwVLoCqLsB9zi3zFJ+EO7QzjKwQkd7A8Z6iSdnOU1X9ADcnv/QUjwLSR+OvYEzplpjANOwGYC9P8XzgYHUG5AWhqs8DR+EPzfeH4PDOMLLhJCD5xOwLXJLTrFHVF4Aj8Nv7/lZEjs1PvPLGlG7pmQD4JtfnwFBV/bBYL1LVe4DTUxTfGBziGUZKRKQr/jk0VVV9q9a0qOr9wGkpiqeJiG8xUtGY0i0hIjIaOM9TtAoYoapZ5TnJBVW9CviLp6g7cGdwmGcYqRgObJ50TYEr861QVa8F/uQp6gbMEZH6fOsuR0zplggR2Q9IlbHvZFV9uISv/yXucC6ZPsA9waGeYfj4qefa3ar6doH1/i9wh+d6b9yc7Ftg/WWDKd0SICJbAzPxp0OaoKo3lvL9wWHH8bhDumQGALODwz3D+BoR2QH/2cOkQusO5uQJOAueZLbCrXirIp2PKd0iIyIbA/cAvpw6NwMXhiFHcDh3MP5o/XsBNwSHfIbRhi/Z2cs429qCUdXluO0L36p5D9y5Q8XrpIpvYJiISC/gLuCbnuJ/ASeFaZsYHNINxR3aJXMsFv3JCBCRDfEf+E4q5pxV1Y9xc9KXWO1I4HfFeldcMaVbJESkBrgF+L6n+HXgUFVdEa5UEBzWjcAd3iVzXnDYZxin0Dk/2me4r7OioqqvA4fin5O/EpGTi/3OOGFKt3j8GTjEc/0TnCtuZEGcg0O7VBP52uDQz6hSRKQWv1nXdcWwIfehqo8AqX7wrxKRA0rx3jhgSrcIiMg44CxP0Qqc88NbIYvUieDwzred0BWYGRz+GdXJ4UC/pGurgcmlfKmq3gKc7ymqAWaIyHalfH9UWOyFAhGRYcCd+H/AjlRVn5lMJAQHZzcBx3mK3wV2U9XF4UplRI2I/BvYLenyTFU9PIR3t3lsjvIUv4+bkx+UWo4wMaVbACKyI+6AbC1P8Tmq6jMIj5TAVOwBYG9P8TPAPqr6VbhSGVERBBd/ylO0t6o+GpIM3YB7gcGe4meBH6iqL65IWWLbC3kiIpsDc/Er3Gtxe7yxIzjMOxR3uJfMzrgo/zXhSmVEiM9M7HngsbAECMI8HoaLt5vMjsCtlTQnTenmgYh8A2ik8z4YwP3AuDiHrQsO9Rpwh3zJDAcuCVciIwpEpB/OTCuZiWHP3yCw+VBcholkDgIuC1OeUmJKN0eCk947AN8m/4u4fdwCU/uWnuBw72DcYV8yPxORVIFzjMphLC7rQ3s+xpdKKgSCVD4HAb5EgWeIiM9FuewwpZsDwab/ZMBnzvIBzjTsi3Clyh9V/Tf+uKkAE4NDQqMCCfb2x3qKrlHVlrDlaUNVnwZG4oLsJHOZiAwPWaSiY0o3N36J3971K2CYqr4fsjwFE1hX+IKcdwFuDw4LjcrjKGDDpGutwFURyNIBVZ0NdEpdBQhuf3fnkEUqKqZ0s0REjgQu9hStBo5S1edCFqmY/Bl/RLRewNzg0NCoEIIvNt+n+h0xMs+6DJjiud42J32u9mWBmYxlgYjsgQv64YvMdbqqltSIPAyC4NVzgR96il/EZRYum60TIzVBMHufdcJuquozH4uEYE7eiTtgS+ZlYFA5Zru2lW4GRGQr3MD7FO5llaBwAYLDvyPxZ4DdDrgjOEQ0yh/fKvfpOClc+HpOHoUzYUtmG5zXWtnNSVO6aQiCfd8DbOApng38T7gSlZZgJduAOxRM5gBgsoWDLG+CraIRnqKJYcuSDYFTxDBgoad4CHB1uc1JU7opaJfB15dK5GngOFX1Jdwra4LDwGG4w8FkTsYdJhrly2m42AbtWQTMiECWrFDVhaTOdj0Gl5WibDCl6yGsDL5xJTgUPBJ/ZuGLg0NFo8wQkZ64EI7JXBV4hcUWVf0/UmcW/p2IHBOySHljStfPePwBnZfibHGLlsE3rgSZhc9IUXxTcLholBcjcTnJ2rOS1Ln8YoWq3geMS1E8XUT2DFOefDGlm4SIjAJ+4ylqxWXwfSVciaJDVacAl3qK2jILbxWySEaeBF9vvjgLt5XTIkJVr8Ef16Qbbk4OCFmknDGTsXaIyGBc7ARfQslRpU4oGUeCnFUzcEFykmkC9lDVT8OVysgVEdkXf66znVT12bDlKYRgTt6OiwOczJvA7qrqiysSC2ylGxAE8Z6FX+H+thoVLnydxfU4/JmF67HMwuWCb5X7WLkpXPh6Tv4YeNJT3J+YZxY2pQuIyEa4qGG+DL63ABeEK1G8sMzC5Y2IfAsXPS6ZglOrR0W7zMLveIoHAdPimlk4lkKFSZDB926gzlP8L+DEOIdpDItg368Bd5iYzLG4w0cjnozDxS1ozwKcSWTZoqofkTqz8NHAb8OVKDuqWukGgZFvxp/Bt4mIMvjGleAQcQTuUDGZ3wSHkEaMEJG1gZM8RZPLIQRpJlT1NVJnFj5XRHxtj5SqVrrAn/AfEH0CDI0yg29cUdWH8P8RA1wXHEYa8eF4Om+btQDXRSBLSQgyC49JUXy1iOwfpjyZqFqlKyKnAWd7ilYAw+OQwTeuBIeKvk+3rsAsyywcD4I9Td8B2s2VZnGiqjfjP3tpyyy8bcgipaQqTcZEpAG4izLI4BtXgoOzv+IM7pOZj4tYVTb2n5WIiByAM4FMZntV9QU2KmuCOTkNOMFT/D6wq6ouCleqzlTdSldEdsDZ+Pna/itTuNkRHC6eiDtsTKYOuDs4pDSiwxdN7OFKVLjw9Zw8BXjYU7w5bk76EsmGSlUpXRHZjNQZfK/D7fEaWdIus3CTp/j7wM2VlMW1nAg8s3xxaGMZTaxYtMss/JqneCfgtqjnZNUo3XYZfDfxFD9AzDP4xpXgsHEo/szCh2I/ZFHhi5vxDm7RUdGo6mekzyzsc20PjapQukGg478D23uKXwSOUFWfyYmRBcGh43D8mYXPFpFUQUqMEhAsMEZ7iq6sxHCkPlT1HZxDjy/J5pki4jtgDIWKOEiTxqauuH3EHrhOnq8N9a3w9eb61fhD2i3Cba6XXULJOCIiR+B+3JJZjbMI6bDKSjduRvZ06scR2x/EyhXJq7mvgM1U9fOw5YsSERmBix2S7ByiwCGqeleH+0OYk2WrdKWxqQ/ONm8Uzt96Je6PuwsuCtYbwHRO3r8Xi9670FPFV8De5eh7HmdE5Bz8CTy/AvZm7uvvks24wVRtqDc76RSknP+qXUi0rs0H78K8WfDADFi2FGCKqlblF4eI/By4xFPUjJuT8wlxTpad0pXGpm44e7yzcR2T+oQ80bqS1tZuzJkGt02G1q93ELwrL6Nwgi+La0hOVd+1Fo4/axkjxtQikiDduLk/hi64vbfx2lAf6wDbYZLT/G9ZDiIwZxo8MGN7Xfx+RVotZCKYk5OBUzsURDQny0rpSmPTFsA8YFPSd1BHWprh04/gvFHw8SKAM1T1ypIIabTtoc/F5VWDvv3gounQZ0PokZMVWTMuN9YQbah/r9hylht5z/+VKxJ06/42VdyPnTILRzgny0bpBhPuGVzk+9xNPhKt8OVSOP/EqfrWK7Hzx640gsOcx+jbbzsumwnrrAs1vqiZGUkAS4Cdq1VhQBHmv/UjIrIO8C/69vtelHOyLJRu8En1ErAl+U04RyKhdOnyJiLbaEO9WSuUGKmr35LzprzOhpt0zXNyt5EA3gaqctyKNv+rvB8BZMvv1HHulW+wYb/I5mS5mIxdgPukKsyouaZGENkEOL8YQhkZmDz3RDbarLXAyQ1u3Kt53Ioz/60f4Yo7T2ajTVdFOSdjv9INTmkX4Ew4OjNmMHz+CXSpcZ8K39kBxo13ezapaQE2tdPx0pFx3KDj2LVxzX3QZ6NUT1TduGU1/1e2wPXz1uxN3n8HPHwXXPzXVNVWXT9CFn05bCBc+wBs8s011265Aha9C7/wGT8AefRlOax0x+BPBb6G86+GGc/BXx+D9frANRljF68mdSg4ozhkHjdYM3Zt/1IrXKjOccvcj4kE3HVTLnVWYz9CtnMyN3Luy3JQuqPI9qS2W3cY9CN4L2NUxl5BvUbpGEUuJ+zZUY3jNopM/TjiRJh1Ayz7Its6q7EfISZzMtZKN/AO6Z/1Ay3L4dF7YOB3s7l7QFC/UWRyHrfcqJpxy7ofB2wL2+0Cs6fmUn3V9CPEa07GvdPrcN4h3dLeddE4qKmB5c2wXm+YkNXkWxXU/2aBMhqdqSObcYM1YwdOcZw3JdMT1TRudWTbjyPPhF8eAwf7Qsl6qaZ+hFz6Mndy6su4K90eZLMHc95k+N4ebm/rqQfhV8fDVY2wft90TyVId8hjFEJ24wZrxi57qmncsu/Hunr4/j5wx7Ww+VbZPFFN/QjZ9GWXGmfP355Eq/NcS09OfRnr7QXcyWD2MtbUwB4HQJcu8PJ/M96NPwKRUTi5jVtuVNO45daPI8+E+/8On2aVsKOa+hGy6cu+/eDDBR2vfbgA+vqiwXYgp76Mu9KdTy6fA6rw5Dx3oJD51742qN8oPvMpzWccVNe4zSeXftzkm7DXULg7palYe6qpHyGbvtxrKNx+FXyyGFavhuefgKcfgkE/zFR3Tn0Za6UbhFTLvE8yYSwcvgMcuSPcdDmcdTF8c0Cmp96wMIKlIetxy4+qGbe8+vGYcS7WSGaqph8hy748Zpyz8//lsXD092Han519bl19pupz6su47+mCC6l2IalMPW54KJ86m3EJ7IzSMZ104wb5jF01jtt0cpn/ffvB7IzBxKqxHyFTX3bvAWPOcf+yJ+e+jPVKN2AqxZezC9U56cLExq04WD8Wj1j0ZeyVbuBedynuF6UYNAOXVJsLZNjYuBUH68fiEZe+jL3SDRiPi2FZaH6nRFDPhIIlMrLBxq04WD8Wj8j7siyUbhClfQiwhNWJfCP0tMXAHFKtYe3CxsatOHTox/yVRdX3I3TsS1mdyDcOQ0F9WRZKF0Ab6t/j0Xv3Y/GCbE9n17ByRVvsy6oN4BwV2lD/Hk8+uC+LF6iNW/4E7d8Z1x+5fh5/hfXj12hD/XtD//PPfbZcvIBeuc7JIvRl7EM7tkdEfk7X2ks4ZhwcMtrZ5fbomfqBlmaQLjD7BuUfM7+ti99vCk9aow0R+Rlday/LY9zg/ju21o8WvhqetPEmCGh+PvBzMuVIW5PX6xJgQjWvcDshcsbKrrWTxh8zjksPGY2osjzdnCxiX5aN0hWRGpydXR0Aa68L+x8Gh4xaQp+N1sb5PydQrSHRuhYL58O8mfCPWW3ZUC9T1bMjEr9qCcatCZf1IJ9xm6SqP41K/rgijU29WZPBdgBt/ei8o2pxGWynAdOq8dAsLSJdgNdw/caStddl6v6HMXH4CZ8t3GDjtShxX5aT0j0EmJ10WYGBzH39Hdrnqj90+yNYteL3Sfd+AWyqqstKLqzxNSJyEHCXp+jbzH39LdqP24jtR7ByxR+T7vsS2ExVs45bWG0EEa7qaOtHmF9Njg85IzIUaPSUbCtzX3+dEvdlOSndh4F9ki43quowz729cRHik78XTlfVyaWR0PAhIvOA/ZIu36eqB3ruXR83bsmfzD9V1UklEtGoNkTupy1T9Rrmobp/GK8vi4M0EdmezgoXwPuHqKpLgGdN4FAAAA7KSURBVJs9RWeI+7QwQkBEtqGzwoXU4/YZ4EuBYONmFAeR79BZ4UKKOVkKymUin+m59irwjzTP+DpxIP4ON0qDb9yagPvTPHOF51p/oNPK2DDy4AzPtbfwbzeUhNgrXRHZABjpKbpC0+yNqOpLwIOeIp8iMIpMsMVzvKdokqqmtI9U1Vfw/5jauBmFIbIe4IvyfgVp5mSxib3SBU6mc4Dgpfg/Q5PxrXYPFJGBBUtlZOIkOu+pf0F24zbRc+0AcZ+GhpEvJ9L5vGAZLhBOaMRa6YpILXCap+h6Vf0qiyoacYbMyZxekGBGWkSkKzDOUzRVVb/Moop78Yfh830aGkZmnOmi7+9+GqpLwxQl1koXOBTYLOnaauDKbB5W1USKe0eJyLoFymakZjiwRdI1JftxW41/b/eEwMLBMHLlINps/DuS1ZwsJnFXur59vLtUdX4OddyAc91rz9rA6HyFMjLiG7e7VdX31ZGK6Tgb3fb0wjkEGEau+ObkPaiG7qUaW6UrIjsBgzxFvv2+lKj7dJjuKToj8JYyioiIfA/Y21OUk0lO4Azhi1N6uo2bkRPO5HRfT0kktt+xVbr4f5leAB7Joy7fp+qWwNA86jLS4xu3l4F8UnxciduWaE8d7lPRMLLFdxbwGvBA2IJATJWuiGwEHO0pmpTOTCwVqvo6cJ+nyHz6i4iI9AWO9RTlO25vAPd4imzcjOxwJqfHeUquICJ33FgqXeAndM7c+SlwawF1+rYl9hORbQuo0+jIT4DuSdc+w+8dmC2+T8B9Ai9Fw8jESeRvcloSYqd0RaQbcKqn6FpVXV5A1Q/gvKGSMTOkIpDGvO86VS0kPco/cN6HyZizhJEeNye9potEGPgqdkoXOALYOOlaAriqkEoDMyTfqun4wHvKKIzDgX5J11YDBQUYCrYlfHvyIwNvRcNIxSF0NjnN2nSxVMRK6YqI4N+vm6mq7xfhFTfhvKLa0xP3CWIUhm/lOVtVi5Gp4CbcJ2F7euC8FQ0jFT5dcheq74QuSTtipXSBXYHve64XxbQj8Iaa6ik6PfCiMvJARHYBdvMU5WTel4rA+/B6T9FpwbaGYXSkSCanpSBuStf3y/Rf4IkivsNnhrQ5zovKyA/fKvd54LEivuNK3HZFezbDeS0aRjK+OfkS8M+Q5ehEbJSuiGyK2xdMJi9zo1QEXlF3e4rMDCkPRKQfcKSnaGKRx20+/gwUdqBmdCS1yenEqMzE2hMbpYuzWEj+xP8IuL0E7/JtV+wlIjuU4F2VzlhcHqn2fAz8rQTv8n0aDgq8Fw2jDZ/J6RIKMzktGrFQuiLSA9dRyVytqitK8MqHcF5SydiqKQdEpDtO6SZzjaq2lOCVj+C8EpOxcTMcaUxOKcx0sWjEQukCxwDJ5j+rgKtL8bLgs9e32j1WRDYsxTsrlKOA5P5qpUDzvlSkGbejAy9Gw0hlcjolAlm8RK50AzMx30rl76q6qISvvhnnLdWebsApJXxnxZDGvO8OVf2ghK++Feed2J5u+L+UjOrDp0tmURyT06IQudIF9gK+57leUtOOwEvqOk+RmSFlxx7Ajp7rJY3cFHglXuspOjXwZjSqFZHdgF08JbHKJB0Hpev7ZXpSVf8Twrsn09kMqR9+KwqjI75V7tOq+mQI774K98nYno1xn5ZG9eLTJc8Cj4ctSDoiVboi8k38dpahGDAH3lKzPUV2MJMGEdkcGOEpCmVFEXgnzvQU/TTY9jCqDWdy6vvRnRQHM7H2RL3SPc0jwwf4/6BKhU/B7xZ4WRl+TgOSA4kvAu4IUQafgv8+zqvRqD7G4jc5LYXpYkFEpnRFZC38vvNTVHVViKI8BjznuW6rXQ8i0hP/YeNVqroyRFGewHkrJmNOLtVGGpNTSmNyWhBRrnRHAslJBlfgPyQpGWnMkI4MvK2MjowEkqOyrSQ+43Z44N1oVA9HA32TrpXM5LRQIlG6aczEblXVj8OWB/cJkvzeWvyG/1VLmnG7TVU/DFsenLfiR0nXuuI3jjcqkdSmi3+ntCaneRPVSncwsI3neiSmHYH31DWeorGB15Xh2AfYznM9qnFbgX8185PAy9GofPbEb3IaKzOx9kSldH2/TP9S1edDl2QNV+G8qdqzIc7rynD4VrmPqeqzoUuyhqtxn5Lt2QDn5WhUPj5d8iSqT4cuSZaErnRFZCtgmKco0l+mwIvKd/puZkiAiHwLf/jLqMdtEfB3T9GZNm4VjsgW+E1OY7vKhWhWuqcDyX8M7wF3RiBLMj7zsR1x3lfVzjg6j9sC/HbOYeMbt+/hvB2NymUcfpPTGRHIkjWhKl0RWQcY4ymarKrJn/aho6pPAb7Pkqo2QxKRtfGnNIrLuP0H8HnCmdlfpSLSC7/J6VWEa3KaM2GvdE8AvpF0bTn+VCxR4Vs1jQi8sKqVHwPrJl1rwR+7Iip843Zo4PVoVB7H4Tc59R2Ix4rQlK6IdMGf7vyvqrokLDmyYAbOu6o9NfjTi1c8acbtZlVNjvYVJTNxn5bt6UKVjltFk8Z0kWhMTnMizJXuD4F6z/VYbXoHXlW+eLCniPukqTb2B77tuR63cVuFP2bqyYH3o1E5xMrkNFfCVLq+X6YHVdWXwSFqrsV5WbWnN3BsBLJEjW/cHlbVF0OXJDPX4j4x27M+zovOqBx8c/JRVH3u/LEjFKUrIt8GfuQpijwdso/Au+o2T1FVmY+JSD0w1FMU13H7GH8eLDMfqxScyelBnpJYzkkfyVF5ioI0NnUF6oAeQAtda8+gtdOB4ltAYyneXyQm4Q7+2rMtvdYeLI1N79LWNpivDfWRn+AXgyzH7R1gbsii5cIkYHTStW3otfYQaWx6hwoct0omeU4ur+02rseqlXE1Oc0KKVaoSWls6oMzBxsF9Md9nq9GtYZE61p88C7MmwUPzIBlSwHOUtXLi/LyEiEijwJ7ss56sP9hMGQEbFK3mq5dm3HBz7sA3YE3gOnAVG2oj9OhYEbyGLefq+ql0UmcGRF5BNg7adyUrl2/okLGrZJJNydrE61r9f/gXUbPm8WJD8ygt5uT56D6p+gkzo2Cla40NnUDLgDOxk3o1IdNLctBBO66aSUvP7Op/uefnxT08hIj66x7DIeOuZVDRoMq9OiZ7vZm3B/zpcB4bagPM8xhzuQ5bqt44alN9dlHY31CLOusdySHjr69EsetksllTvZsWY6K8NO7bmz94bOPb7bvC09GEXApLwpSutLYtAUwD9iUdH+0yaxa2Uptt3eAIdpQ/17eApQQaWzaAtV5rGzpT/eeuewHNgMLiXvbbNySif24VTL5zsluq1a2roz5nEwmb6UbdNIzuFP95CwC2ZAAlgA7x62zrG1psbYZRaXaxi0vpRt8BrwEbEl+ndRGAngb2EYb6mPhumdtywprm1EUqnHc8jUZuwD3GVBIJxE8vwlwfoH1FBNrW2asbUaxqLpxy3mlG5wsLsCZcKTmV8fDO6/BzY9DbbdM1bYAm0Z9gpx12/55N8yZBgvegZ5rwZbfhiPHwjY7++4un7aNGQyffwJd2s3//Q6FU1PO4/Jq25kXwfeCgHGPNMKUC+G8ybCdNwdpLNpWyWQct8N3WPPfK5Y7PdI2N8eNh30P9j0V+3HLx053DO5kMTUfLoBXnoFe68BTD8KeB2aqc3VQ7yV5yFNMMrdt9jSYca0b9B33hK618N9HXTv9Srd82gZw/tVrFFNmyqttbTw4G66/GC68Br6zY6q74tK2Sib9uM1o52CW/KOZmtiPWz7bC6PIdLr40BwY+F23SnpwTjZ19grqjZpRpGvbV1/CLZPcym+PA6BHL6d0dx0MY85J9VR5tC0/yq9t990OUy+GCdenU7gQn7ZVMqOo3DmZkpyUbuAd0j/jjQ/dCfscBPseBM8+Bp9lZY47IKg/ErJq22vPwcoVsPv+uVYf/7blT/m07Z7b4OaJcNGNMMCX6q0TkbatkqnkOZmJXFe6dXQOBNORl5+Bjz5wWwr9t4V+m8MjWXmNrgrqj4o6MrXti8/hG+tDTc7jGf+2tXHRODhq5zX/7vNlwulA+bTtucfdF1idL9idl6jbVsnUke245U6sxy1XpduDTHtnD86BHQbBur3d//9gmNtDy0yCTAdYpSVz276xHnzxGSRydtmPf9vaOG8y3P7Mmn8/OjLTE+XTtnHjYeF8mPRr56mWmajbVslkP265E+txy1XptqR9ZkULPHYvvPQfOG6Q+zfnRmfF8PZrmequCeqPivRtA/j2DtCtO/x7Xq51x79t+VM+bVuvD/xuOrz8X2e5kJmo21bJVPKcTEuujZ4PpLb/enKeM+mY0ghXzHH/rr7Hneo/lPFArTaoPyrmk65tAGutAyPPhKsnOMXbshxaV8Ezj8ANaeNtxL9t+VNebeuzEfz+Rnj2Ubju95nujrptlcx8KndOpiUnpRuEwnsz5Q0PznYRnTbcBNbvu+bfsJHOtjX9Z/kbUYbay9i2Ng4dDSf+Cm6fAiN3h1H7wNxbYPch6Z4qj7YBTBjr7CPb/l00LtMT5dO2Nvr2g9/dCI/fD9P/ku7OSNtWyeQ1btkT63HL54RvOnAhPlOPCVP9T+w11P1LTTMwLQ9Zis10UrWtPfsenMow20f5tO2Gh3Kts3zbtvHmMP2RdHXGpW2VzHSy+XuDXOZm7Mctnz2VqXk+l0mOOHSUtS03rG1GIVTluOXc4MC97lLcL0oxaAYuiYPbnrUtJ6xtRkFU67jl+yszHhd7NFHg+xNBPRMKrKeYWNsyY20zikXVjVteSjeIrj8EF8My385qi4E5JE6h2KxtGbG2GUWjGsct7/2UIFjwzrgYlrl+HnwVPBfLoMPWtpRY24yiU23jVtAmdtDIbYHLcMbImTqsObjvMlyw4dh2krWtA9Y2o6RU07gVMxtwb9Zk8ByA839O4LxDanGZV6cB0+K+0Z2Mtc3aZoRHpY9b0ZRuh0qTctUD8+NsrJwL1rbypJLbVslU4riVROkahmEYfkoVcMIwDMPwYErXMAwjREzpGoZhhIgpXcMwjBAxpWsYhhEipnQNwzBC5P8Bm4qWvkwS4QoAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "rbt = RedBlackBST()\n",
    "for (value, key) in enumerate(sorted(list(\"REDBLACKTREEFUN\"))):\n",
    "    rbt.put(key, value)\n",
    "showTree(rbt)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wie wir sehen, ist dies ein gültiger Rot-Schwarz  Baum, der einem 2-3 Baum der Höhe 2 entspricht (Rote Kanten werden zu 3-Knoten). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Als nächstes testen wir was passiert, wenn wir bereits sortierte Inputs einfügen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAADnCAYAAAC9roUQAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAgAElEQVR4nO2deZhcRdWH3zNbFsKWsIVAEkMYQCKCRlH2JSAS1rCGsISwSthERFQkBIOiIqCyiJCFHURIEIaPJYBsfiBIQKMfThADhF0ggTCZTGbmfH/UnclMT/Xt29vt293nfZ55HrhVXX3mpOZ0df1OnRJVxTAMw4iHmlIbYBiGUU1Y0DUMw4gRC7qGYRgxYkHXMAwjRizoGoZhxIgFXcMwjBixoGsYhhEjdaU2wDCKiTQ11wEjgf5AK7BYxze2l9Qoo6oROxxhVBrS1DwEmAJMBkYDbUAn7ptdP2ARMAeYqeMbPyqNlUa1YkHXqBikqbkBmAacgwuyA0O6t+CC8OXAdB3f2FZ8Cw3Dgq5RIUhT83BgPjCM8GCbSgvwFjBOxze+UQzbDKMnFnSNsicIuC8Ag4HaHIboAD4CxlrgNYqNBV2jrAm2FBYCo8gt4HbRAbwGbK3jG1cVwjbD8GEpY0a5Mw23pZBPwCV4/cbAhXlbZBghWNA1ypYgS+Ec0u3hTtkDXvpz72fz74HzJqYbcg3gXGlqHlw4Kw2jNxZ0jXJmCi5LoZB0BuMaRlGwoGuUM5PJLlMhCgODcQ2jKFjQNcqS4KTZ6CINv3kwvmEUHJtYRrkyEnfSrCG014ypUNtDY2tfBZt9PtPYq4LxX83DPsPwYkHXKFf6E2U/94KrYdsdVv///Hvg4bsyvaojGN8wCo5tLxjlSivFm7+1wfiGUXAs6BrlymIybS3kTn0wvmEUHAu6Rlmi4xvbB6xsXVKcwfVVK/9oFAsLukb5IVKHyA+n3fabEQNaV6TvN+ux3vu5AOMmwM9vT/+a1hVwxzVriUhGtc0wcsGCrlFeiGwBPA3MOOmhu2pVpNDjw703bgK8KCLfEZF8jxcbRi8s6BrlgUgNImcCC4DtAQYvX8Y582YzsLWlMO/R2gJzZ8HyZeCKnV8GPCYinyvMGxiGVRkzygGREcAsYI/Upra6esZcfT//3mhT7aytzX3Z29EO774Jp+3n/rs3y3E1Hm5Q+4Mx8sRWukZyERFEjgf+jifgAjS0r+q87RfnXN1ZU/NfXH5tLnSg+jHTTnrVE3ABBgG/A5pEZOMc38MwAAu6RlIR2QiYh1vhrpmm16vATmMXLTwdkbG4erjZ7jV8BrxGXf22vPvmNsCVIX2/CSwUkSOzfA/D6MaCrpE8RA7FFSY/IKTXVcC2qP4vQHDjwxjgCtzBhkzBtyXodwWucPkbqrpCVb8N7A68nuZ16wK3i8idIjIk6q9kGF3Ynq6RHETWBX4DTArptQQ4HtX5aYdx9XC7bgPeHFdLoQN30qwedxvwbGB2utuARWQt3KWVJ4TY8i5woqo2hfQxjF5Y0DWSgcg3cFsJYXumNwFnobo08rCuWthIXC2FVmBxNgcfRGQ/4AZgw5BuM4FzVPWTqOMa1YsFXaO0iAwCfgGcGtLrA+BkVOfFY1Rvgm2Ea4DDQ7q9DkxW1T/FYpRRttierlE6RHYCXiY84M4FxpQq4AKo6oeqegQwEfg4TbcRwOMicoWIDIjPOqPcsJWuET8i/YGLgXOBdLm1y4AzgFtI0CQNUsZuwGUypOMV4FhVfT4eq4xywoKuES8i2wE3A1uH9HoEOAHVN+MxKjtERIATcULboDTdOoCfAD9WVbvS3ejGgq4RDyJ1wPdxV5ynK57fAnwXuDZJq9t0iMgoYA6wc0i3BbhV78JYjDISjwVdo/iIbInLPPhKSK8/A5NRXRSPUYUhKIhzNnAJrl6DjzbgAuByVc311JxRIVjQNYqHSA1wJvBT0l9/04Zb/V5GGQekoBTkzcCXQro9jctw+Hc8VhlJxIKuURxERuIOIOwW0utl4BhU/x6DRUVHROqBH+JWtelKQn6GExCvs+I51YkFXaOwOJFpCu54bbqaCZ241e/FqLbFZVpciKsDcROwVUi3B3Gn2d6KxyojKVjQNQqHyFBcNa79Qno1A8ei+lw8RpWGIFd3BvBt0qfFLQWmArfbqrd6sKBrFAaRw4FrgcEhvX4NfB/VAlUdTz4isisuw2FkSLc/AN9S1f/GYZNRWizoGvkhMhi4Gggrd/gGrkjNY/EYlSxEZE3gl8BJId3eA05S1fviscooFRZ0jdwR+Sau2MvQkF6zgW+juiweo5KLiOyLO82WyV9nW/GcysWCrpE90VZu7wMnofrHeIwqDyT6N4PJqvp4PFYZcWIFb4zsENkFl+oVFnDvxhWpsYCbgqp+pKoTgSMAby1fYDjuQsxficjA+Kwz4sBWukY0XJGaS8isxp8O3FYOx3hLjbhsj+uB8SHdmnHHiCs626OasKBrZCZa3ulDuCI1lneaBbI6r/lK0hfP6c5r1grMa642LOga6cnyhJWtbnNH3Am+OcCuId1ewq16K+IEX7ViQdfw42oJ3AR8OaTXM8BxWC2BgiBZ1qqw4jnliQVdozfuD/9sXC3YjFWzyrlITVIRka1wH3hjQ7r9GThOVV+NxyqjUFjQNVYj8jncV9xdQnotwB3jtfqwRSQonnM+EesP2zHi8sGCrtFVpCbqTQgzKrFITVIRkS/hSkZ+PqTbI8AUVV0Sj1VGPljQrXai3/l1HKp/iccooyeS5Z1ytupNNhZ0qxmRI3FXi68b0utK4AeorojHKCMdIrIzbvtnVEi3e4BTVfWDWIwyssaCbjUiMgQXbA8P6fU67vqcP8VikxEJERkEXAacEtLtfeBkVb03HquMbLCgW22IjMdtJ2wU0msmcA5WdCWxiMg+uH+njUO63QicpVZsKFFY0K0WRNbCCWUnhPR6DzgR1fvjMcrIBxFZF7gKOCqk25vA8ar6aDxWGZmwgjfVgMhuwN8ID7i/B7a2gFs+qOrHqjoJOAz4ME23TYH5IvIbK56TDGylW8m4K2N+gjvskI6PgdNQvSMeo4xiICIb4a5K2j+k2yLcMeJn47HK8GEr3UpF5CvAi4QH3AdxJRgt4JY5qvoucCCueM6nabptDjwjIj8RkXSnDY0iYyvdSsOdZPoR8APCi9ScA1xvRWoqDxEZgbuBYveQbn8DjlHVv8VjldGFBd1KQmQM7sz+diG9nsKlgr0Wj1FGKQiK55wO/Iz0xXNWAdOAX6hqe1y2VTsWdCsBkVrcynUG0JCm10pcmcYrrUhN9SAiW+A+iL8a0u1Z3F7vonisqm4s6JY7IqNw+Zg7hfR6ETgG1X/GY5SRJESkDvgecBHpi+esAM4DrlHVzphMq0os6JYrrkjNybgLItdI06sDt/q9BNVVcZlmJBMR2Q636h0T0m0+rnjOm/FYVX1Y0C1HRIbhTpXtE9Lr/3AlGF+IxyijHAiyFqbjSkKmy176BFdM/SYrnlN4LOiWE251OxF3hfc6aXopcAVwgRWpMdIhIjvitqU2C+k2DzhFVd+Px6rqwIJuuSCyHnAtcGhIr8W4zIQnYrHJKGuC4jk/A04L6fZfXOC9Jx6rKh8LujEiTc11wEhcCk8rsFjHN2ZO1RHZH3dV94Yhva4HvoNqusR4w/AiInsDs4BhId1uBs5U1aUZx8t1nlcJFnSLjDQ1D8GdEpoMjMbdL9aJ20/rhzuaOQeYqeMbP+r9YlkLV8/2+JC3eAdXpOaBAptuVBFB8ZxfA0eHdFuCE9ke6fP6fOZ5lWFBt0hIU3MDLvH8HNzkCys20oKbnJcD03V8Yxsiu+Mm6fCQ190BnI5qumInhpEVIjIBuA5YL6TbNcB5qvpZ3vO8CrHaC0VAmpqHAwtxdQ/6Ez4RCdr7A2dLZ+c/Fmz2+VnAY6QPuB8BR6A60QKuUUiCvdsxQFgB9NOAl2TPgw8mx3kOLAz+TqoOW+kWmGAivQAMJn3tg7TUdLTrkE+XyQvfPoThH7zj69IEnISqt9EwCoG4TJljcVsOa/XpsP5QuOJuWGudTmpqc1m8deAWD2N1fOMbeRlbZljQLSDBV62FuDussg64XdR2tDPq3Tf5x2n7Ud/RrT8sx60QZlmRGiMuRGQ4TmTbs/thXT1cfT9stAnUpjvgFokO4DVgax3fWDWHd2x7obBMwynAOQdcgI7aOt4asiHTJ07tevQEsA2qMy3gGnGiqm8Ae+NuGnZ53xOnwpAN8g244P5ONgYuzHegcsJWugUiUG+XkL6iU9b0b2vl5dMPuKDx7dd/ip2HN0qMiDSyznq3MvPRsfQr2DQHl1Y2rFqyGmylWzim4NTbNK17wIRt4LDt4IixcO6R8MDt0Jn+JSvrGlq3+N3DKy3gGklAVZu58Ym7qK0N3wqYsge89Odshu7E/f1UBRZ0C8dkMqm3F/4W7loAsx6Hw06Cu6+HX/8wbXetqekfjGsYyaC27jjq6usLPOpAqmieW9AtAMEJnNGRX7DGmrD9nnDelfDoXFjcHNZ782B8wygpWc/z7KiaeW5BtzCMxJ3AyY4ttoH1NoJ/hhYCWxWMbxilZiS5zPNoVM08t6BbGPoTtp8bxuAN4NNlYT06KKA4Zxh5kPs8z0zVzHMLuoWhlVx9+eF7sObaYT1qg/ENo9TkPs8zUzXz3IJuYVhM+rvJ0tP8Nxd0P//lsF71wfiGUWoWk8s8j0bVzHMLugUgKFv3auQXtCyHvzwOPz8HdjsARm4R1nuRlcUzkkBW87x9FbStXP3TkXEKV808rwq1MCbm4C7+S582dvGpUFsLUgObjoaDjodvHhk2Zgswu5BGGkaezCHTPAe46OTe/3/EqXDMt9P1rqp5bifSCoQ0NQ8G3qKwYkBVndQxko/N8/yx7YUCEUyYy3Gf2oWgBbisWiaiUR7YPM8fC7qFZTqfffpJhP2rcDo7O3GriYsLYZRhFJjptR3t79bmO887OhTtfJsqm+cWdAvJfltswhkHDOLTZVGEAz8d7fDJxzVcdu73q6ncnVE+6H5btC88bb+3B3+6jJwDb0c7fLpUOGvCU9U2z21Pt0CISAPwFPBV1h8KM+a48nf9MxXT70Fri0shu+B4+OCdJcAXVbVqvnYZZYLI94BL31h/KONmzOGtIRvQkvs8BzhQVf9YJGsThwXdAiEiPwe+2/2grt7VHZ1wYid1da2IpJ+Vq1atorOjnrmz4Pare66S7wUOVvtHMpKCyNeApwlqRrfV1TN94lR+efAUVtbVr6CmZkDa13Z2tLJqVX/PPP8It8BYUmzzk4AF3QIgIt8AHvQ0LeakH+zGgccdhquitDnujHkHbtLWA4voaL+R43Y5hKUfbu8Z43RVvbpIphtGdETWARbgqZHwXOM2h33t8rtGEjbPYTYn792ft1+f4Rn9CWBPVe0oiu0JwoJunojIRsDLwAYpTR3ATqr6bHdfV0VpJC7dphVY3JUQLiIjgJeAdVLGWQlsr6ovF+UXMIwouDvT7gAO97Rehmr3t7wM81yA+4F9PeNMU9WKF9Us6OaBiNTgVrh7eZq/r6qXZjneBOBuT9MrwFhV/Sx7Kw2jAIicCFzvaXke2AnVyNXHRGR93EJlaEpTJ7Cbqj6Vs51lgGUv5Me5+APufODn2Q4WXH99radpS+BX2Y5nGAVB5PO4W4FT+RSYmE3ABVDVD4CjgdQVXw1wm4gMzsnOMsFWujkiItvjBIXUo9Tv40SBd3McdwDwHPAFT/NEVb0jl3ENIyfcfPwLMMbTehSqt+c+tMwAfFenVLSAbCvdHBCRtXH7W77aFcfmGnABVHUFcCRdN6/25nciMirXsQ0jB36JP+DOzifgBlwE+C5TOxA4Lc+xE4sF3SwJhIDr8Fe5v0xVH8r3PVT1n8BZnqY1gdtFpNB3VBlGX5zG8C1Py79wV7Lnhaq2A0cBSz3NvxSRL+b7HknEgm72TAGO8Dx/Hv9XpVy5AbjL8/yrgC/lxjAKh8hwYKanpQ04kgKJuqr6OnCip6kfcIeIrFGI90kSFnSzQES2An7jafoUt99asPujgv2sk/EXdj5PRPYu1HsZRi9E6oDb6Ju+CPAdVF8q5Nup6t3Abz1NFSkgW9CNSCBw3Qn4Ttycoqr/LvR7qupSYCIu5zeVm4McYcMoNNOAHT3P7wWKdVDnHGCh5/kJIhJadLrcsKAbncvwZxTM1vwFhbQEhysu8DRtANwU5AobRmEQ2R3/NtkS4ASKlFFQTQKy/cFGQEQOxq+mFkRQiMDPcbm/qeyFyxU2jPwRWQ+4BZCUlk5gEqofFvPtVfUfwNmepooSkC3oZkAyCApxnBJT1U7gWOADT/MlQc6wYeSOy8qZDWzsaf0xqk/GZMn1VLiAbIcjQhAnKDwO7ORpPkNVr4rZnn2A//E0/QfYTlWXxWmPUUGInAVc6Wl5EtgTl94VkymyDq4OyQhP8zdU9eG4bCkGttIN50L8AbeYgkJaVPVB3N5yKp8DrgtyiA0jO0S+BPzC0/IRblsh1lt6K11AtpVuGkRkN+Ax+u5vLQG21SLvb6UjKJb+NPAVT/OJqurbCjEMPyJrAn/FlWNM5SBU743Zom5E5PvATzxNjwD7BNtuZYetdD2IExRuJY2gUKqACxDkAk/E5Qan8psgl9gwonIV/oB7VSkDbsDPgEc9z8taQLagm0LwFX0WaQQFjU9QSEuQE3yqp2kA7hRPIa/HNioVkaNxAm0qL9PzFpQSEaxkj6HCBGQLun05A9jf8/xJEqSequptOLU5lW3w7/saxmpENsdfRrQFd8y3NWaLvKjqO8BxnqY6XBrZ2jGblDe2p9sDEdkOeBZoSGlK5B1Owbn0vwJbeJonqOrcmE0yygGRfrjqXl/ytE5B1fdhXlJE5DLgO56mO3FH8MsmkNlKN0BEBuH+AVMDLsCUpAVcgCBH+EhcznAqM4McY8NI5af4A+7twJx4TYnMD4AXPM+PwBWhKhss6K4mraCgpRcU0qKu+IhPVFgXuDXINTYMh8i+wLc9La8BpxbrmG++9BCQl3uay0pAtqALiMgk/PtGiRAUInAV8EfP852AH8Vsi5FURDYGbvS0tOOu3fkkZouyQlVfpQIE5KoPuiIyGn9ZuRbcMd9ECAphBPtZU4C3PM0XBDnHRjUjUgvcDKznaf0+qn+J2aKcUNVb8W+BlI2AXNVBNzhocAcwyNN8uqq+ErNJORPkDh+FyyXuSQ1um8H3x2ZUD+cDe3iePwRcHrMt+XIGrthUKlOD4lSJpqqDLk5Q+LLneZIFhbQEOcQ/9jRtDMyyY8JVisgOwHRPy3vAcZTZyS5VXU4ZC8hVmzImIt8EHvA0vYYrHpPo/a10BMLZY8DOnuazVNV3lbZRqYisiyse4wtEe6P6SMwWFQwRORP/zRJPA7trzDUjolKVK10RGUp6QeHIcg240H3Z3yRcbnEqvwhykY1qwH2zuR5/wL20nANuwG+A+zzPEy0gV91KV5yg8DD+/a3vqmpZbMZnQkQOBOZ5mpqBLwdf0YxKRuQU/CLxs8AuqK6K2aKCIyJDcFlGw1KaOoE9VfVPsRuVgWpc6X6PyhEU0hLkFvvq/TameW5UEiJj8NfH/QQ4qhICLnQLyJMoIwG5qla64gSFJ4HalKb3cMd834vfquIR5C0+C3zR03x0kH5jVBoiA4Hngc97Wo9A9fcxW1R0RGQ6rv51KvcBBybpmHDVrHSDavS30TfgAhxTaQEXIMgxPhKXc5zKb4McZaPyuAJ/wL2hEgNuwI+BpzzP9yeeewwjUxVBV1YLCr7rPy7V8hcU0hLkGp/uaRqEq9LkqzVhlCsihwEne1r+DzgrZmtio4eA/LGnOVECclUEXeAk4FDP82fxfyWpNObgco9TGYu/Mr9RjoiMxC0uUmnFbSv4vvFUDKr6JnC8p6kBd0zYdwgqdip+T1ecoPA8kHou+xPctTv/id+q+BGRtYAFwChP876q6rvw0igX3PXkTwJf87Sehqqvdm5FIiJXAVM9TTeq6uSYzelDRa90xQkKd9A34AKcVC0BFyDIPZ6Iy0VO5cYgd9koX6bjD7hz8aeNVTLnAn/zPD8uKG5VUio66OJSwLb2PL9BK1dQSIu6oiY/8DStj7tltdLnQ2UisieutkIqbwInJrVcY7FIuoBcsX9kInIIcIqnqaIFhQj8EpeTnMqeuBxmo5wQ2QC4hb6XqHbgyjX6TiZWPKr6f/izFkouIFdk0BUnKPiuIm8FjtAKFxTCCC77Ow6Xm5zKj0Xk6zGbZOSK+2YyB9jI03oRqs/Ea1DimI3bXkylpAJyxQlp4gSFJwBf8DhNq0hQCENE9sIdh07ldZzAuDRmk4xsEfkO/hqyfwLGodoRr0HJI7i4cgHwOU9zSQTkSlzpXoQ/4FajoJCWIDf5Z56mEcD1VgYy4YiMxZUmTeVD4GgLuA5VXYbb302MgFx2K11paq4DRuIyElqBxTq+sR1ARPYA5tN3f+tN3OqtKve30hF8K3gK2N7TfIqq/q67b4jfjeKQ1ucu/e9FYDPPy/ZH9f74rCwPROQ8/IuMR4G9g223WOZ5WQRdaWoegruOZjIwGle8uBO3Uu8HLGLph3fxrX1P4dOlqftbHcCuavtbXkTkc7h6q2ulNLWyw9578oPf7EiY392e4kwd32gfaAUg41xXXXTGfTe3XnTbVV8avHxZ6suvRNV36WTVE2Tm/A+wd5/GjUfM4HcPf0JM8zzRQVeamhuAacA5OCcMTNu5bWUHqrXMmw23Xw3t3UWUfqSqM4pubBkjIofjrp931NXDxKlw8BSlvmFFUEAlHS24yXk5MF3HN/qq+RsZyGauD2hdgYpwzrzZTLv9ahrcXF8AfB3VlbEYXIaIyIa4MpAbAqvn+UHHQ319KzW1YRdbFmyeJzboSlPzcNxWwTDCgm0qrS3w4ftwwWT44J0/AePU9rcyIiLXAyey/lCYMQeGbAD9o7sdNynfAsbp+MY3imFjpZLrXB/Y2sKwD9/n4R8d3zLy/be3Q7W5aEZWCCKyN/BQKed5IoNuMAlfAAbjrwoWTkc7LP9Eefze7fX6nz5faPsqEREZyEabvsRld27OmmtDbV0uw3TgbqwYa4E3GvnO9dqOduo72j9tbeg/xnweDRk95hqmX/+tUs3zxAXd4GvWQlyNgOwDbhednZ3U1Pwb2FrHN1ZEweZiIk3NDbStbKa2dkSOE7GLDtw9c+b3DBRsrpvPIyNNzQ2oLqSzczS1tflk6OTs8ySmjE3Dfc3KZxJCTU0N7hbcaqgiVgim0dBv/TwDLrh/N/N7NAoz183n2TANkWF5BlzIw+eJWukGyu0S/AVqYMoesPS/UFPrvhZstR1MnQ7rh6batQLDTF1PT1Z+7+K6B2HIhmHDmt9DyOjzLs4/BnY/AL5xWJRhzechRJrnba1ww/zV+7wP3QWP/xEuvTndsFn7PGkr3Sn0veuoNxf+Fv6wAG5+GtYZAtf9ONOYncG4Rnqi+73rJzzggvk9E5l9nj3m83Ay+7yjA/54UzZjZu3zpAXdyURVbxv6wY77wBv/ztRzYDCukZ7JZJMhEg3zeziTMZ/HzWQy+XzCCXDPLFj+SdQxs/Z5YoJucBIkesm11hXw1AOwhe/OxT5sHoxvpJC137PD/O7BfB4/kX2++Rj4wldhrq9eVvpXZePzJP3jjMSdBAkvuTZjKtTWwooWWGcwXBzJOauC8V/N08ZKZCTZ+B3cpLzgmihjm9/9jCSKz3PDfO5nJFF9PulMOG8iHHBc1LGz8nmSgm5/ouxxXXA1bLuD23t57lEnNFzbBOuuH/aqDjIJFtVLdn7PDvO7n2g+zw3zuZ/oPh/ZCF/ZDe76HWzqK2/Rh6x8npjtBZwKGN2e2lrYYW+oqYF//DVj72B8oy/Z+T07zO9+zOfxk53PJ50JD/0ePvSVne5DVj5PUtBdTDZft1Th2fluwzvzp1F9ML7Rl8UU52sumN/TsRjzedwsJhufbzwCdt4X7kubKtaTrHyemKAblE/LvCdy8alw6HZw+Jfgpivh25fCiM0zvWqRlSH0E9nvuWF+95C1z7NL4zefe8hpnk+c6mq5ZCYrnydpTxdc+bSLSJfWMeuxXMZswV3bYaRnDub3uJlDmM+7WLEc1lw36pjm83DmkM08X38ozP17pjGz9nliVroBMym8TTXYRMyE+T1+Mvv89UXw5r9hs62ijmk+DycR8zxRQTc4Snc5/quTc6EFuMyORYZjfo+fjD6f/Qv40RSYfC5sMCzKkObzDCRlnieq9gJY5aVSYX6PH/N5/CTB54la6QIEFdnH4epV5lp8vKve5TibhNHo5ffci76b37PAfB4/SYgviQu6AEFh4LHAa7StzM4xbSvbcZ9AVkg7S7r9/snHyyKqtj35DPN71nT7fMVn72ftc9UWzOdZ0+XzhlVtSwaWYJ4nMuhC4JjvH7sz82bDylZXayGM1hbXb95s5YLJX7NJmCP7bfEmx+2yjHtvzM7vb/3nNtxXLfN7luj4xjc4eoe/Zu3zv//lYcznOaHjG9/48Miv3nH2vTfSf2UrAzL53O3ftgJXkKfPE7en2xMRORW4lkFrw16HwLgJsPFIqKv7DBF3EWX7qjV4+3WYfzc8cg+4G1KnqKqpuDkgIjvhrmWnl9+Hj16FSBvQwcrWQdTU1KT4/XJV/U5JjS9TRGR94G2grpfPN92snZqalUAHbSsHIlKX4vOHVfUbJTa/PHG3Ay8GNv1o0NrM3OsQ5oybwCubjOrorK1txW0h1OIOPizCZSjMrvzbgEWeAXof+K9vuJK5f7+arnvpDxpzDu2rvpXy0sdVdY+YzKwoROQ64OSUx49w/7/2xRX16M+0Eyew4M/T6ey18/MusKmqWmJ+lojIGcCvUx6/xSkXjGL/Y4YD/bl62hgeuuv2FJ934nz+dly2VgwiuwOpCegd/xo2cviW1z00kK74AosLfdgksUFXREbjPmFS2U5VX+rRb3vgWU+/kar6erHsq0REpD8ueK6d0nSMqt7So9/goF99Sr9vquqDxbWy8hCR53EaRk9+pqrn9+hTgztR9bmUft9V1cuKbGLlITKbvnVwm1Ddr6+TGwUAAA+tSURBVNhvndg9XeAYz7OFuHvre/IX/MF5UsEtqnz2p2/A/QyY2/OBqn4E3O95/bFFsqtiEZGt6BtwAXod+lfVTuAWTz/zebaIDAQO9bREKrSQL4kMuiIi+IPuTZqyNA/+33e/xjHBOEZ0fD6/W1U/8zz3+fwgEVmrwDZVOj6fv6iq//A89wWFL4hIpEr+RjcHAYNSnn0C/DGON09k0AV2pO/XKAVuS9PftwLYEv8KwvAQiDnf9DSl+/R/AJer2JMBwCGFtKuSCbYMjvY0eX2uqovwb6XZajc7fP66C9WMKQyFIKlB1/fpP19V3/J1VtXFwJMRxzH8HEnfAkhvAY/7OqtqG3CHp8l8Hp1dgU1TnnUAt4e8xvcN4ygRSVrxqmQiMhTYy9OS1W2U+ZC4oBuIOUd4mjI5xdc+UUSKVbe00vB9+t+i4SelfD7fXURGFMimSsfn8wdVNaxy9p2462F6shHulJWRmaPoG/cWA0/HZUDigi4RxRwPf6Bv9fb1gH0KZFfFElXM8WAiZo5IjmKOiZh5411c4ITKWEhi0M1GzOlGVZcB90Ycz+hNNmJONyZi5kU+Yo6JmLngBMdtPC2xZC10kaigm4OYE6XfASISuQp0tZGtmOPBRMzc8Io5Gk3MMREzN3yLi+dQbY7TiEQFXbIUczw8DLyf8qwBOCxPuyqZXMScbkzEzB7JU8wxETMHnNDo2/aKTUDrImlBNxcxpxtVXYU/rcz2u9KTi5iTiomY2VEIMcdEzOzYEyc49mQVTpiMlcQE3TzEnCj9dxSRSBfYVxO5ijkeTMTMjnSLi2zEHBMxs8Pn8yZUP4zbkMQEXXIUczwsAHyv8e1bVjsFOZljImZ0pEBijomYWSCyJnCwpyX2rQVISNAtgJjTTTAZfa+zydiXfMScVEzEjIZXzNHcxBwTMaNxCE5o7MnHOEEydhIRdMlTzPFwK+7YcE82A76e43gVR75ijgcTMTMgBRZzTMSMjM8fd6C6MnZLSE7QLYSY042qLgEejfg+1UpBT+aYiBmJYog5JmKGITIc2N3TUpKtBUhA0C2gmBPl9UcEx4yNwog5qZiIGY5XzNH8xBwTMcOZBKRuKy4CniuBLUACgi7FK7N2D33vt18HGJ/nuGVPocQcDyZipkGKJOaYiBlC+hKxN1PC2xuSEHQLKeZ0o6rLcYE3yvtVG4UUc7oxETOUYoo5JmL6+TKwlee5T4CMjZIG3SKIOVHG2VdE1ivQ+GVHocUcDyZi+vGKOVoYMcdETD8+nz+F6n9it6QHpV7pFrvM2mO4W1Z7Uoc7blytFPVkjomYfZEiizkmYnoQqcfFl1RKJqB1UeqgWwwxp5vg+PCtEd+3WiiGmJOKiZi9iUPMMRGzN/vgBMWerMQJjyWlZEG3iGJOKr5Ptq+IyJYFfp/EUywxx4OJmAEh9/3dnHrfX56YiNkbn8/vRXVp7JakUMqVblHEnFRUdSHwkqepGtXdWE7mmIjZi1jEHBMxeyCyDnCApyXWurnpKEnQjUHMiTLu0cHx42qimGJOKiZiOrxijhZHzDER03EY0C/l2QfAQyWwpQ+lCjpxl1m7HXesuCfDgV2K9H6Jo9hijoeqFzElZjHHRMxufL/vbTjBseSUKujGIeZ0o6rv4tJqothRqcR6MsdETKA0Yk51i5gio4CdPC2J2FqAEgTdGMWcKOMfGhxDrmhiFHNSqXYR0yvmaHHFnGoXMX3C4T+BF+M2JB2lWOmWqszavcCnKc/WBA4s8vsmgZKczKlmEVNKJOZUtYjpFhe+37Okx35TKUXQjVPM6SY4VnxXRHsqjTjFnFSqVcQspZhTrSLm13DCYU8U/zZXyYh14pdAzInyPt8QkVRRr2KIW8zxUK0iplfM0XjEnGoVMX0+fwzVN2O3JIS4VxulLrP2FPBGyrMa/EGpUijpyZxqFDGlxGJOVYqYIv2AIzwtiRHQuogt6JZQzOkmOF7sTSCP4/1LRCnEnFSqTcRMgphTbSLmeCC1qloL/v3tkhLnSjcpZdZ8QXdbEflCzHYUnVKJOR6qRsSUEDEnrsUFVKWI6fP5XFRT513JiTPollLM6UZV/4W7vjqVSpyMiTiZU2UiZpLEnOoQMZ1AuK+npeQVxXzE4vwEiDlR3vdoEamN3ZLiUkoxJ5VqETG9Yo6WRsypFhHzCKA+5dk7+E/nlZy4PvGSVmbtTqA95dlQ3PHkiqDUYo6HihcxJWFiThWJmL7f51acoJg44gq6SRBzulHV/wJNnqZK+rqbBDGnmyoRMZMo5lS2iCmyBfBVT0sitxYghqCbIDEnyvtPEJHUSzLLjqSIOb739zyrJBHTK+ZoacWcShcxfR/aL6P699gtiUhdMQaVpuY6YCTQn7G7HsCLT/ejs9dKPwll1u4HluLOpXcxkH79D5Wm5qeB/rirrRfr+MbUrYjE0cvn+03akgfu2CzF5yU/maOq/xKRv5C6MqlvOFaamq+jzHwOPfz+4tMbMXTEvry3hBS/l3TFpaorROQuYEqvhtq6Y6Wp+XnK2OcDVrYO+OsmoyZv/vbr1CXI55mQQi18pKl5CO4fdjIwGmgDOlnZOoia2hreeR3m3wMP/wGWL/uVqp5dkDfOAxG5FjiVNdeBvQ6BcRNg4xFKXf1nQCfum0A/3AGOOcBMHd/4Ueks7k1an7etHIDU1Kf4/FFVHVdKewFEZCpwVS+fDx0BdXWfIdJBwn0Oafy+qq2O9lX9qWug2++P3P0uny7dREu8tygiuwJ/6u3z4YHPa8rW57Ud7TX921YObKtrYPQ7r3P8/HuY8vAfOocsXzYMt5+dSPIOutLU3ABMA87BBar0e0WtK0AE3n97FpuO+paOb2zL683zRAavvwv7Hf0EBx0PqtA/tQ5PL1pwk/NyYHopbc/J56+8dB9f/NqhJff51l8eythdl3Dg5Jpy8jnk4Pe6unbq6n9OqefLpbf0Y9HC9xl/1FqV7PMBrSvoqK3tbKtvuJQE2J6OvIKuNDUPB+YDwwibgKmotiDyFjBOxzemKtqxIE3Nw1GdT1vraPoNyOY6kxagZLaXvc9hPm0rR9HQL5v0vJL6HPLwe1Lmy6q2kdQ3pKZVhWE+LxI5B93AIS8Ag4Fc8ls7gI+AsXE7plxtL1e7wWzH5ktWlLPtmcgp6AZL/oXAKHJzSBcdwGvA1jq+MZaE/XK1vVztBrM9wOZLRMrZ9ijkmjI2Dbfkz/cEVy2wMXBhnuNkQ7naXq52g9kONl+yoZxtz0jWK91ARVyCSzVJz/nHwH9egVuegfqGTMO2AsOKrZhGsv1P98G82bDkPzBgDRi1JRx+Kmw9Nt0rim57JLun7AFL/ws1PebpngfDt9LOt+T4/IkmuHcOvL7IiTwbbgJ7HgT7HuVEwL4kx3Zwvj9zBmy7Q5RhSz9fUu19ogmuuQguuBq+4DtnACTB51P2gI/ehxufhLUHr35+xoEu1sx81M2dvsRie1RyWelOwamI6XlvCfzzBfcH81yk48+dpOYRFodw2+fOhut/4oLsLc/A7MfdH3747xCH7Zl9DnDhb+EPC1b/pA+4kBSf3zMLrr8EJpwANz8Nt/wZpk6Hf74I7Wm/ESbD9txIznwBeHQu/PZiuOi6sIALSfH5hsPgyR6HSRf/C9paM40Zl+2RyCXoTiaTkvjYPNjii26l9ei8KGMODMYtNpNJZ/tnn8Ktv3aBaoe9of9AqKuH7feAKd8LGzMO2yeTnXobhQT5fBrstA8MHOQ+qDf7PHz3l2HfkEpve+4kZ748eCfMvBQuvgG2+lKm3snw+e4HuvjSxaPzYI+DMo0Zl+2RyCroBidBRmfs+Ni9sNv+sPv+8OLT8PF/owy/eTB+Ucho+ysLoG0lfH2vXIYvmu2RfZ4bpff5qjb4Wk51hkpre36Ufr48cDvc8iuYcSNsHvkUdul9vuW20LIc3vw3dHTAUw/A7r4qA30oqu3ZkO1KdyTu1FN6/vECvP827PRNGD0Ghm4KT9wfZexVwfjFYiRhtn+yFNZaF2pz+ncppu0jyeTzLmZMhSPGrv558PeZXlFin3/c1+fnHulsn7ANLHw+bOzS2p4fpZ8vC55x30ZHNmYzdjJ8vvuBboX70jOwySgYsmGUsYtte2SyDbr9ybRX9Og82G7H1Rvdu+7n9o0y00EmwSI/wm1fax0XBDpyOn5eTNsz+7yLC66GO19Y/bPP4ZleUVqfr+nx+WV3ONvXXAc6Q3/t0tqeH6WfL1Onw1uL4dc/dKcxo5EMn+9xoFvIzZ/r/jsaxbY9MtkG3dbQ16xshaf/x61Qjt7R/cy70SmLr72SaezaYPxiEW77lttBQz/43/m5jF1M28Ptzo/S+7y+AZ7NqdZ0aW3Pj9LPl3WGwCVz4B9/dZkL0UiGzzcY5rIUXnjC6S/RKLbtkcn2u/RiIH3+17PzXcrSVfdBfY8Th5ee7Ta/R50fNnZ9MH6xWEyY7WusCZPOdEpubZ1brdfVwUt/hr89B1POCxu7mLYvJszu/CitzwetBROnwrXT3WrryztDvwFOkW5dkWns0tqeH8mYL0M2hJ/cCOdPclk7J/0g0yuS4/OzLoHly5zgHe3babFtj0xWn+RB6bdX03Z4dK6rYLTBxrDu+qt/9pvk8l/DnbOomKXlMtoOcPDxcML5cOc1MOnrMHk3uP9W+HrG4lxFsz2S3V1cfCocut3qnxlTM72i9D4/9CTn87tvgKN3cD9XXQjHnwtbbRf2ytLbnjvJmC8A6w+FS26EZx6COb/M1Ds5Ph86PBsBEIpsezbkohrNAS7Cl9Zx8Uz/K3be1/2kpwWYnYMt2TKHdLZ3sfsBUdXQLuKwfQ6Z7J71WLZjms8zM4dMtkO2vi/9fEm1d6NNYc4TmcYsvc/T+bm2Du7/V9iYcdkeiVz2rGbm+LpMdsThlHK1vVztBrM9FZsv4ZSz7ZHI+pcLjtJdjvv0KAQtwGVxHNErV9vL1W4w21Ow+ZKBcrY9Krl+okzH1avMtyJ+RzDOxXmOkw3lanu52g1mO9h8yYZytj0jOQXdoCL7OFy9ylwd01XvclycZdfK1fZytRvMdmy+ZEU52x6FnPdOgsLAY3H1KrP9KvBZ8LqSFBguV9vL1W4w27H5khXlbHsm8tqwDn6hMcAVuMTjTM5pCfpdgSssXDKHlKvt5Wo3mO3FtdBPudoN5W17GIW8DXgwq2/r3Bx31rkDdxKkHnfT6GxgdpI2taF8bS9Xu8FsLwXlajeUt+2pFCzo9ho0uJced9a5FViclMTkTJSr7eVqN5jtpaBc7Ybyth2KFHQNwzAMP8Uq6GEYhmF4sKBrGIYRIxZ0DcMwYsSCrmEYRoxY0DUMw4gRC7qGYRgx8v8CYbLPqO6s1wAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "rbt = RedBlackBST()\n",
    "for (value, key) in enumerate(list(\"ABCDEFGHIJKLMN\")):\n",
    "    rbt.put(key, value)\n",
    "showTree(rbt)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAADnCAYAAAC9roUQAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAgAElEQVR4nO3deZgU1bn48e87GzsoCLIozkUYXNBEwzVuMYrEaxwSFb0qKhEwidExKlyN5ueCeNGbaxDUBHcciBqMC6AwJhhwN27ELWh0UO9EQZBVBIZmZnrO749Tw0B3V3f1Vt3V/X6eh0fpqjr9crrmneqzijEGpZRS/ijJdQBKKVVMNOkqpZSPNOkqpZSPNOkqpZSPNOkqpZSPynIdgFLKf1JXXwZUAh2BENBgqqtachpUkRAdMqZUcZC6+l7ABGAcMBhoAlqx33g7ACuA2cAsU121MTdRFj5NukoVOKmrrwAmA5OwSbZznNMbsUl4OjDFVFc1ZT/C4qJJV6kCJnX1A4ElwADiJ9tIjcAqYKSprvo8G7EVK026ShUoJ+EuA3oCpSkUEQY2AsM18WaOJl2lCpDTpLAcGERqCbdNGPgMONhUVzVnIrZip0PGlCpMk7FNCukkXJzr+wM3pB2RAvRJV6mC44xSWIkdDpYpIWCAjmpInz7pKlV4JmBHKbgcHQHv/q397y/Wwdn/Dv94M16ZrU65Kk2adJUqPOPwOlJh6Xy45ya48V445Ih4Z3Z2ylVp0qSrVAFxZpoN9nTyX/4Es34DNz0ABx7u5YohTvkqDVqBShWWSuxMs4q4Zz0zFz78O0ydA4MO8Fp2s1P+J2nEV/T0SVepwtKReO25bd55FYZ+Cyqrkik7TGY754qSJl2lCktIjEk8TKxmCqxqgDuvBe8jmEqxoxhUGjTpKlUIRASRo0OnDbupvKW5S8Lz9+gFN8+GD/4Od93o9V3KgYZUQ1SWJl2lgkykCyI/B94BXu3Q0jxm/9UeZ+z22htumQNvvwz33+LlihW6/GP6NOkqFUQiQxG5A/gSuBf4Vtuh8Uvm0Sm03Vs5vfvBzXPg1cUw+7Z4ZzYCtakHrNrojDSlgkKkDPgRUAOc6Hbaxq49GDDnJUIdMtjnFQ43U1raV2ekpU+fdJXKdyJ9Ebke2546jzgJF6Dn1s1cuujhxvLmpswsUBNqhMfvLWfU0OvFJn6VBk26SuUj2zH2PUQeBb4AbsIuYJPIa8DYXlu+3ru5vKIBO8wrdeEW2PAVzJ0JcAWwUER6pFVmkdPmBaXyiUg34DzgEuAQj1dtBx4B7sKYd3YWle56uuEW2LIZJp4B61bveuQj4EfGGJ0kkQJNukrlA5GDgIuBC4BuHq9aAdwFzMGYTTGLTXXnCGMa2bSuhf86q3tEwm2zETjTGPO85zIVoM0LSuWOSDkiZyLyPPABcCmJE24rsAA4CTgAY253S7gAzo4Pw4AZ2IkNjQnKbwRCiExn6zd7sW71lUCsJ7OewLMiclGC8lQEfdJVym8i/YGfAT/HLhDuxVrgfuA+jElp6xypq+9J+27AQ7BrKYSxTQ/l2CfnWqB211EKIlINzMX9F8LvgEnGGB3D64EmXaX8ICLA97FttafjfbGpV7BNCPMwZkfGwrGrhVVi11IIAQ3xJj6IyMHAQuDfXE55FjjbGPN1pmIsVJp0lcomke7AWGyyPcjjVduAh4G7Mea9bIWWLBHZC3gSOM7llI+xHWwr/IsqeDTpKpUNIsOwiXYs0NXjVR9hn2r/gDGbsxVaOkSkAhvjhS6nbAL+0xiz1L+ogkWTrlKZYhPS6dhk6/Y0GCkMPAXMBJ4nAD+QYptKLgduI3ZnfBi4zBhzl6+BBYQmXaXSJbIPtlPsZ0Bfj1etAe4D7seYldkKLZtE5IfAo0B3l1PuAq4wxujW7bvQpKtUKuzT3gjsU+2peJ988BL2qXYBxjRlKTrfiB1fvBAY5HLKUmxzg+uwtmKjSVepZNgpsBdgk+1Qj1dtBR7Czhhbnq3QckVEegFPAMe7nLIC28H2sW9B5TFNukp5IfItbKI9H+8zuz7EfsV+CGO+yVZo+cDpYPsdtpkllq+Bs4wxf/UvqvykSVcpNyIdgDOwyfYYj1e1APOxTQgvBaFjLFOcDrZfYme/uXWwXQHMNEVUL5E06SoVSWQgcBHwU6CPx6vaFhN/AGO+zFZoQSAiJwGPAW6rkd2DHd1QlB1smnSVAhApwa5TW4NdKNzruiTPY59qn6ZIk0gsInIAtoNtsMspz2M72Db4F1V+0KSripvInrR3jA3xeNUWYA52xtiH2Qot6ESkJ/A4dpRHLJ9iO9j+6V9UuadJVxUnkcOwT7XnAp08XvUPbMfYwxizNVuhFRIRKQfuBH7hcso32DUb/uJfVLmlSVcVD5GOwJnYZHukx6uasesNzAReLaaOsUwSkRrgDmKPZ24FJgF3FkMHmyZdVfhEKmnvGNvL41Urae8YW5OdwIqLiPwA28G2h8sp9wOXmgKYNBKPJl2Vc8kuM+itUCnBLvRdA1QD4vHKJdgmhIXo+rAZJyJV2A62KpdTXgTOiNfBlpX7xUeadFVOSF19L9oX1B4MNGG/ZpYAHbCzmGYDs5La9tt23ozHbn2zv8erNjvvdTc6ayrrxHZePgaMdDnlM2wH285OyqzdLzmgSVf5SurqK4DJ2Da8VuLP7mrE/lBNB6aY6ir3r50iw7FPtedgn4C8eA/bVvtHjNnm8RqVAc5W7jOwWxTFsgU4h0UfLyEb90sOadJVvkl5k0T7w7QKGOns+eUUKJ2As7DDvY7wWFYTdhjTXcBr2jGWWyLyC+D3xOpg692vlTsXbKBrjy6IpH+/5AlNusoXaW8HbqeQbgSGm1FDy7BDkC50yvPic+xMqFkYszaF91dZIiIjsAvm7Lnzxd79YMaT0K0HlHrd2Wg37fdLniVeTboq65wmheXY5f9SSbi2nNbW1v4b127/7MITO1eEW7x2jC3GPtXWYUw41fdW2SUiQ7AdbEMpK4eZi6DvPqkm3DZhbPvwwaa6Km9mC+oW7MoPk7FNCiknXABTUlKyqWv3LjeNqUmUcL/GtutVYczJGPO0Jtz85uyrdiTwLGNqoFefdBMu2PutP3BDugVlkj7pqqxyep1XEq9z68U6eGo2/GsFdOwEe+8DJ54Gp5wLEp1fO+4IseqC4+i5NWobsbexHWOPYkxjxv4Ryjdy9zN96L/fl5SVR/+CnjACNq6FOS9Bj11alX55KvzfRzBrqb13ooWAAfkyqkGfdFW2TcD2Osc270G4/2YYfSE89Ao8/DeomQIfvg0tsb8RijHM+sEZbX/dAfwB+5Q0HGMe1IQbYAMHX0BZuftW83sPgJfq2v/e8DE0hRKV2oq9D/OCJl2VbeNwG6mwbQs8cidcPBmOPRk6d7VPtvsfBFfdBuUVMS/b3rETD5x8VjNwNbAPxlyAMW/oSISCMI54I1tOOBWeW9D+96ULYMRpicrs7JSbFzTpqqxxZg65Le0HH70DzU1w5IlJl13fv9LIoo+nY8z6NEJUeSTh/QJwwLehcSt88SmEw/DyM3DCj70UP8QpP+c06apsqsSOi43tm03Qfc/dO0yuPAfOHg6jD4Xlb7mXLNLslK8KRyXx7pc2J5xqn3DffRX2GQS99vZSdt7cL3mR+VXB6ki89txue9jEG25pT7zTHrX/veA4aHW/FDscyOvMMxUM8e+XNiNOhavPh69W2v/3Jm/uF33SVdkUIt49dsBhtt329aWplF3qlK8KR/z7pU2fAXaUwrIX4eiTvJadN/eLPumqbGoAYveGAXTtDmNq4O4pYAx853vQoZPtkQ5tT1R2uVO+KhwNxLtfdnX5zbB1M3TsbL8pJZY394smXZU1prqqRerqPwEOcj3pzJ/ZNrknH4AZV9uk23dfGH8lHHhYvOJXBGk5P5WYp/ulTb+ByRafN/eLJl2VXcbMJhyeSlmZ+xPMCT/22gPdphGoTTc0lZdmAzcSa9jYg8/FvqK0DBbFXZEzr+4XbdNVWSMi5Yw//kDCLd6+MnrV0lLBpnWzM1qmyhezyHxeKkGTrip0ItILWMz6NeNZUAuhDE0SCzXCE/eVMfbYe0WkS2YKVfnCmao7Hft0mgmNwLR8mQIMmnRVFojIAcAbwAkAzJ0JG9Z67fBwF26BDV/Z8uAM4GUR2Te9QlUemoIxqwiH051hGMauq3tTBmLKGE26KqNE5D+A19l1q5yWZrhuHGzZDK0p/iCFW+z1143fNXkfBrwpIt9NL2qVT0x1VROTfzaDLV9Lyr+ow2GDMRuxC5nnzbKOoElXZYhYlwPPAD2iTli3Osz/XHY9JaWfkOxXR2O2sfWbjUw8A9atjjzaF3hRRM5NLXKVb0SkK2+/fC0Tz4A1K5Nvmgo1wprPhesvnJpvC5iDJl2VASJSgd2u/HZi31NfAz80y9+aCgzD7o0VInHybQRCiMygR8++rFt9NrEHuHcAHhGRm8XuAqyC7XpgAOtWQ80oeGoO7AhBOOy++hjYZLsjBAtmwyWj4N1Xfy0i0Q8AOabr6aq0OB1mTwLfdzmlHruza/1u19XV96R9d9ch2LnxYezMoXLs7q61QO2unSBiN6B8Crs4dSzzgZ8YY7am+E9SOSQiBwLvEzmcdc/ei3nolSW43S+NW1cz9/f78dd5dtJEu9uNMRP9iN0rTboqZSJyEHaLlUEupywBzjLGbIpbjl39qRI7Nz4ENMQbyC4i/bGJd7jLKe8BPzbG5N1XS+VORAR7z4yIOLQDOMgY8xm43y8i8iQwOuLaMHC4Meb9bMaeDE26KiUicgrwKNDN5ZSZwERjTFY6McTuDvsgcLbLKWuB04wxr2Xj/VXmicjZ2Hsq0o3GmCkerh8IfAR0ijj0CnCcyZNkp+1fKilOh9kk7BNurIQbBi4xxlyarYQLYOzuEGNw3/+qD/CCiIzNVgwqc0SkG3Z8bqTPgFu9lOF8s/nvGIeOBc5PPbrM0idd5ZnTYXY37lufbALONMa4zNfMDhE5E7tlT+QTTpv/Bf6fMSbxsoEqJ0Tkt8CVMQ6NMsbUxXjdrZwO2DbhqohDa4GhxpivU48yMzTpKk9EpDe2w+x7Lqd8jO0wW+FfVO1E5HDgaeyuw7E8DZxvjNniX1TKCxE5GHiX6LVgnjbGeF4wd5fyTgIWxzh0pzHm8hRCzChNuiohERmGbU6odDnlWeDsXD9FiEg/YAFwhMsp/8D+YviXf1GpeJzOs+eA4yMOhbCdZ/+XYrmPA2dGvNyK7VR7L5UyM0XbdFVcIjIKeA33hHsnUJ3rhAtgjFmN/eH9o8sphwBvicgxvgWlEjmH6IQLcEuqCdcxiehx4CXATCfR54wmXRWT02F2JfZredcYp7QAFxljLjfG5MU6pQDGmO3YTpNrXU7pDTwvIuN8C0rFJCLdgdtiHPoU+G06ZRtjviD2mgvHADntXNXmBRXF6Yy4B/dtqzdiO8ye9y2oFIjIaOAh3Lf0ngZcY4wJ+xeVaiMit2GfSCOdYoz5cwbKr8B2qg2NOJTTTjVNumo3ItIHmId9Iojln9iJB5/4F1XqROTb2Kd1t9XIFgHnGWO+8S8q5fQTvIudUbarBcaY0zP4PiOBv8Y49DtjzGWZep9kaNJVO4nIodgEtZ/LKX8GxhhjNrscz0si0hc7PfhIl1M+wHawpdOGqDxy2lRfAI6LOLQd23nWkOH3+xNwVsTLrcB3jDHvZvK9vNA2XQWAiPwYeBX3hDsDm5gClXABjDFrsGv7PuxyysHYJSLdhsOpzDqX6IQLcHOmE67jv4BtEa+1dar5ngM16RY5p8PsauxQq1gdZs3AT40xk4Lc9mmMCQE/AX4NxPp6txewVETcJn6oDHA6z6bFOPSJy+tpM8asBGJNIz4ae0/4SpsXipiIdMQuyeh2420ARhtjXvIvquwTkVOBRwC37X6mA78K8i+ZfCUi04FYq3790Bjzlyy+bwV2IaQDIg6tw3aqxV2UKaOxaNItTiKyN7ad8yiXUz7ENid85l9U/nHarxcCbnt5B7L9Op+JyCHAO0R3ns03xkSuDpaN9z8Ru4pZpJnGmEuz/f4749CkWxiSWR7RQ4/+M9iEU9A9+s4vnnnYr5mx/BP7i+dT1zKSXJayGMSqE0YNDQMvEj2NfDtwoF+zBEXkUaJXpmsFhhtj3vHj89SkG2BSV9+L9oXABwNN2BuoBLubwgpgNjCrbSFwETkd26HkNnb1NuDqYvlq7YxJvg/3JpaNwBnGmBd2XpNCvRe6hHWydfNaHrt3AM8+EbnI+LXGmFt8i1NkAHadkPampW57wGnj/8VZF21DJOufpybdAJK6+gpgMnZgeSvuCRTsVMgSjJnOfx4eItTotjNqM3aGWW1mo81/zhCmK7GrkcWaItoCXMKij+eQbL3b9uEpprqqKaNB54mk7sXQdhCBBbV2R+eW5hXAIcaY+NvwZJgz0/K3lJXDmBo4bTwYAx3dFqkDMvh5atINGKmrH4htlxpA/B/63TXtaGHd6jKuGxdrc8f1wOnGmFcyFWcQiciPsOs2RI/i6N0PZjzxNT16VWAXUPeqEbsN+Mh83CQxHSnfi6FG2LAW5tw21ry62G0YX9aISDl99/2AKQ8MoVcf6JjMx5n+56lJN0Ccm3wZ0JPozojE2rYx331X3eXYdsuGTMUZZE5nz9PsusBP734w40no1gNKI1cf9CSMbaYYXiiJN/17MWwoLV1PDupE6uoH0tz8HiWyRy4+T026AeF8jVuO3Y8s+Zu8TbgF1nxhd0sNtyzEToHVNWZ3sdvawWXlMHMR9N0n1YTbJozdBeFgU12VtR01/JCxezEHdZIPsevkiOCYjP0al86NYhNHr73hyml/wzYpaMKNYIxZB4wEHmRMDfTqk27CBfu59cd9e6Egycy9mJs6yXns+qQbAE7P8ErsMJbYJoyAr9dDyS730omnw8Wu90QIGFAsveupkCfe6UVFhzWUlsXPuBNGwGVT4dtuI892E+h693wveq8P8KlOEsY+YQQ0heCBJe3tvIsfh+efht885FZs0rHrk24wTMD2DMd3wz3wxDvtf9wTLk55OuU1nk5dJlBalulRB0Gvd2/3YnL8qpPEsYfD8PQfkikz6dg16QbDOJLpHfamM+7r5SprHFrvkcYR3DoZR6LYR18I8x6ErZ7nBSUduybdPOfMkBmcpeKHOOWrCFrv0YJcJ55jHzIMDjkC5s9KpvikYtekm/8qsTNkEptaA2cPb//zl8cSXdGM+95nxa4Sr/WevKDWeyXBrZNKvMZ+3mWw8GHY7LmZNqnYA/fbtgh1xGsb2nUzk+m8ADvsxb1DpLh5r/fkBbXeg1wn3mOvrIJ/Px4evw/23d/LFUnFrk+6+S9E9j6nUqd8FU3rPVqQ6yS52M+7DBY/Bhu+8nJ2UrFr0s1/DUBFlsoud8pX0RrQeo/UgNc6aWmGph3tf8IJF+rKdp00kMzn2X8/+N4psNB1qNiukopdk26ec5aV87YJ5E2/gDMPa/8ztSbRFSuKfRlCN0nVe/ICWe9J1cmNP4fRh7b/+ePvEl2R1TpJ6fMcU2PXiUgsqdi1TTcYZpeGW6aGS8vcf1M/+FyyZTYCRbeiWJJmAzeSaJhRcnUf9HqfTaI6yd97cTbxYo+Mu3c/mP+PRGUmHbs+6eY7kZJPLzyxd3lLS6a/6pYQ7B9+P8wi8z8jQa/3INdJXsSuSTefiXQBHhv01cqrJi2opbO3rzpeNALTgjoV1S9O/UzH1lcmBL7eg1wn+RK7Jt18JbIP8DJwBsDkuTMZsGEtpYk7JOKzO0KsAtwWM1e7m0JL81ceOoISKaR6n4L9t6S7u0gu6iTnsWvSzUci3wXeAg5re6mipZkl142j55bNlITDqa1SFG6B7Y1N2AWYA728oF9MdVUTvzztQ7Zs9tIDH1s4bDBmIwVS786uCSOxa8qmmrza1qT1tU7yIXZNuvlG5FzsBn59Iw8NXLeaRVMuur21pOQTkv2KFGq06+jWVHdg1NCemQm28InID/jik2omngFrVnrtzW4XaoQ1nwuTfzqlUBYwB3D+LcOxa8om+3V9m3NdThZ1z3XsmnTzhUgJIjcDj2A3w4sUAs45ov79iYgMA2Y4r8W/aULbYUcIFsy2C5evW10CzBQR/ewTcDat/D1gd9qoGQVPzbHjTo3ZHvfiUOPu9f72K9eKSLfsR+0fJ+l4vxft8ZBz/sG5/CWUy9h1Pd18INIV+ANwussZXwKnYsyy3S6rq+9J+w6sQ7BzwMPYGTLlwAqef7qBe6dWR+zACjDeGDM7U/+EQiQi1wD/E3Vg4JBLuGtRF9zqfduWNTw6cyB/nRe58+1txpgrsx54Dni6F20vf22+dST6Hbsm3VwTGYjdk+tbLmcsA07DmFVxi7GrHFVi54CHgAZTXdUiIhXAe8ABEZesA4YaYzalEX3BEvu5/JPoMZ2vAMcZ5wcnTr0vAE6NuDYMfNsYszybseeaW53kNCiP/Ihdk24uiRwFzAf2djnjT8AEjElriIuInIjdtTXSTGPMpemUXahE5AmckSO7CAOHG2Pe93B9JTZpRy6E8iJwgtEfvKKl7Xq5IjIWeAH3hHsDMCbdhAtgjFmKTeCRLhaRw2K8XtRE5CSiEy7A770kXABnd+WbYxz6PnBO6tGpoNMnXb/ZDqxbgKtdztgO/ARjnsjs28o+wEdAl4hDrwHHGmOytWRfoDidZ+8DVRGHvsI2x0Q1jscpqyN259nI9QFXAwcYYzxvT6AKhz7p+sn2Xs/HPeGuAo7NdMIFMMasxA4Mj3QUcEGm3y/AJhGdcAGuSibhAhhjQsAvYxzqh92VVhUhfdL1i8h+wELgEJcz3sKOUFidvRCkAngXODDi0Hqgqtg71ZzOs4+AThGHdus8S6Hc+cBpES8XRaeaiqZPun4QOQabVN0S7lzg+9lMuADGmCYgVsfZXsDUbL53QMwgOuGGgZo0O74mYpuNdlWKHS8taZSrAkiTbraJXAA8B/R2OeM64LyEg+0zxBjzHPBojEMXi8h3/IghH4nIycDoGId+57XzzE2cTrXjgHPTKVsFjzYvZItIKXZg/VUuZzQCYzFmnn9BWSIyAPs1umvEoTeAo4utU83pPFtO9G6xa7AdXkm15ebqPVQw6JNuNtgOswW4J9wvgGNykXABjJ1ocWOMQ98FxvsbTV64ktjbc1+ZqWRojNlB7E61vsT+LFSB0ifdTBP5N+wMs2EuZ7wOnI4xa/wLKpqIlGM71Q6KOLQB26mWV1M1s8WZxPAh0W25LwHHZ3oSg4g8SXQzhudJFyr49Ek3k0S+B7yJe8J9GDgh1wkXwBjTDMTaRK0XsdsfC1W2Os/caKdakdOkmykiE4Cl2JEAkQzwa+ykh7zZetsY8wLwxxiHLhKR4T6H4zsROYXooVwAd2RrKJcx5nPgv2McOhY4PxvvqfKLNi+ky3aY3YodVB/LNuzohKf8C8o7EemP7VSLXHbwLeDIQu1Uy+VssTiz3tZiZ719na33VrmnSTdCUqsMiXTHjrE9xaW4z4EfY8x7mY80c0RkInbvqEg/N8bcD8FdOSrOKmDXE3urlXONMXOzHpdd32FxjEN3GmMuh+DWuYpPky4gdfW9aF9PczDQBLRim186YNfTnA3M2rmepsgg7AyzyI6oNn8DRmPMV1kMPSOcTrW3iWyL7r7nJu5+5g569DwLr/WSBxJ+ns1N/+LhOytZ/FhZxHq3LwAj/FoBTEQeB87c7cVue7Ryyx/u4N+G/kfM2PO0zpV3RZ10pa6+AjsHfhL2xo5cO3VXjdgbf/qa845+bu/NG/6E7XSK5Q/Az7HDhAJBRI7DLjsIZeUwpgZOGw8lJS2UV5TFuXRnvQBTnD2ociKpzzO0HURgQS3MnQktzS3Yabkf+BMtiMi+2KadzrvVuUgrFR3i9bfkTZ2r5BVt0pW6+oHYNWYHED/Z7qaspaWp8quVFUuvG8fAdVGzdg12MZtpBLBiReRhevc7j6mzoVcf6Oi5WsAmglXYzfp834Yl1c+TUCNsWAu3TrzPfPLBRdmKz42IXEPvfv8TxDpXqSnKpOv8gC4DemKH6ySlNNxCzy2bWTbxjF0T71bgXIxZmLlI/SW/uGE4x53yJl27C6XxHm5dte2S6uuGg+l+noRboKRkPVLyHb+Tl9y7eH+67/kxXbqWBqnOVeqKLuk6X0GXA4NI5QfUURpuYdCaL/jgklGUh1sasB1m/8hQmL7bWS+trftTUpLOUMIwdrfUg/3YWjtTnyc+xw271fkgSkoCFbtKXTGO052M/Qqazk1OuLSMVb325oqf/foL4IggJ1yHrZf0Ei7Yeu2P3fnCDxn5PPE/bmiv8yDGrlJUVE+6Tq/2SqL3rUqdMSFEBgS5Jzkr9WKHOGW1XoIaNwQ7dpWeYnvSnYDt1Xb3wkK4YjSceRiMPRYm/xQ+WOZ+vkirU26Qxa+XCSNg9KG2Ttr+bEg4Es6Pekkc97t/2/21JfPgV2PilenX55n4XgS4ZiwsftxrmYVwLxa8lFruA2wc8Xq259fCE/dBzRQ4/Fg7dOrvL8MbS+Fg11mxnZ1yp2U6WB+NI1GP/w33wLePTqZMP+plHMmMVPDGr89zHMGNXaWhaJ50ndk9sZbvs7ZtgUfuhItvgKNPskN3ysrhuyNggtuWZjsNccoPnIT1kp6s1UtQ44Zgx67SVzRJFzud0n0Q+UfvQNMOOOoHqZTd7JQfRJXEq5f0ZLNeKglm3BDs2FWaiuk3YkfitaF98zV035M0xkpmskPET/Hrpc3UGih1OtkPOQKuu8tL2dmsl+TjBmhphv3dZm7vlO3P01vsqQnyvVgUiinphoj3ZN99D/hmkx0on3ziLXXKD6L49dLmupnJtulCdusltbiXzINnE3ZMZfvz9BZ7aoJ8LxaFYmpeaAAqXI8ecBhUdIDXlqRSdrlTfhA1EK9e0pPNemkgmHFDsGNXaSqapOssifeJ6wldusF5l8E9N9nEG9puv4ouexEevDVR8SuCuuRewnpJT9bqJahxQ7BjV+krmqTrmI1dJCS208fDhdfAn+6C846CccfDokfgqJHxymwEajMapf9mE69eUuNHvREm7DsAAAweSURBVMwmmHFDMrF738SnEO7FgldsM9J6Yldl0llAuwhqvQQ1bkgi9stPh3NqEv3ibxP4e7EYFNWTrnMzTidzT0eNwLSg3+RBrZegxg0eY//XCvjiU9j/QC9FFsS9WAyKKuk6pgCraG1Nd8hOGPukEmvLlyCy9WL/Xenwu16CGjfEi732t3D9BBh3JfQZkKicQrsXC1pRNS+0kWvuOIRDv/teyuvGtoZbKSndQIGtYZr2urRBXU83h2vSBjl2lZpifNKF/73iIq4YLaxZaXcOSEaoEVZ/UcIDvxlTaDe58+8Zjl2bNdmv7Nuc63z/4Q9q3BDs2FVqii7pisjhwMWsWw01o+CpObAjBM074n89DTXa8xbMhkuqYUHttSLivV85IJwf3mHADGzHTKJE0OicNwO7iHZOfviDGjcEO3aVvKJqXhCREuBV4MjdDnTrsY3fPTWdvfqNBoZg56+HsV/3ytm0fjPzHujNX+cRsXvsGGPMo/5E7z+nh71tV93oerE709YCtfnUgRPUuCHYsStvii3pTgBmxTh0lTFmGuxcAaoSO5QnBDQwamgZ8AF2S5hdrQaGGmO2ZC3oPBGrXoIwCD+ocUOwY1fuiibpikhP4GNgr4hDH2K33o67t5SIVAOLYhy6zRhzZWaiVEoVumJq051KdMIFuDRRwgUwxtQBT8U4dIWIDEs3OKVUcSiKJ10R+Q7wFtETKucaY85NopxK4J9EzyJ6ETjBFENlKqXSUvBPuk7n2V1EJ9ytQFLNAsaYBuDmGIe+D8TdeEsppaAIki62J/iIGK9PNsZ8mUJ504i9QtRtItI9hfKUUkWkoJsXnM6zeqBXxKEPgMO8tOW6lHsy8OcYh2YYYyalUqZSqjgU+pPuzUQnXICaVBMugDHmL8D8GIcu0041pVQ8BfukKyLDgTeJbsv9ozHmvAyUvx+2U61TxKGXgOO1U00pFUtBPunG6TzbAlyVifcwxvyL2J1qxwGeR0QopYpLQSZd4ELg32O8nmrnmRu3TrVpItIjg++jlCoQBde8ICK9sJ1nPSMOLQcOT6ct1+X93DrVbjfGTMzkeymlgq8Qn3RvITrhQpqdZ26cTrV5MQ79UkQOzfT7KaWCraCedEXkCOB1ottyHzbGjM3i+w4EPiK6U+0V4DjtVFNKtSmYJ10RKQVmEp1wvyFDnWdujDGfA/8d49CxwPnZfG+lVLAE7knXbbk7EbkIuCfGJVcYY+7IelwiHYD3gaqIQ2uxyz9+rUv1KaUCkXSlrr4X7Qs7DwaagFbsk3oHwi2f8fCdA/nzo50iFhn/B7bzzJfEJiInAYt3e7HbHvCTia/ww3N6xozdLko9G5ili1IrVfjyOulKXX0FMBmYhE1UnV1PDm0HEVhQC3NnQksz2PbUl30J1iEijwNnUlYOY2rgtPFgDHSMbO7dTSM2CU8HppjqqiY/YlVK+S9vk66zS+oSYADxkm2kUCNsWAu3XPqkaag/M1vxuRGRfend/2Om1naiVx/o6D10bPJdBYzUfa+UKkx5mXTT3pY63AJSsoGSksNzsqV2aPuHlJd3SWl7d91SW6mClndJ12lSWI7djyz5hNsujN2e+mBTXZXx8bmx7IzdmEHY0RSp8j12pZQ/8nHI2GRsk0I6SQvn+v7ADWlH5J2NPb2EC7mJXSnlg7x60nVGKawkejucdISAAdkeGRDk2JVS/kmp0TGLJmBHKbgcHQFfr4eSUigtgwMPg5op0LtfvDJbnXKnZTbU6OjwEntpqY1/38Ew4lQ4+Wwocf3C4VfsSimf5FvzwjgSjVS44R544h146BXYoxfcG2si2G46O+Vm2zi8xP74O/Dg8/CfP4Mn74c7r413hV+xK6V8kjdJ15mtNdjzBRUd4JiT4fNPvZw9xCk/K5KOvUs3+O6J8KvbYel8aKiPd3ZWY1dK+Stvki52eqz3SQGh7fDyMzD0W17ObnbKz5ZKkom9zdBDYa++8OGyeGdlO3allI/y6QmqI/HaRNtMrbHtotsbYY+ecNMsL2WHyWwHVyRvscfSsw9s2RzvjGzHrpTyUT4l3RBenryvmwnfPhrCYXhjKVwzFu6ugz17x7uq1Ck/W7zFHsuGr6Bb3E0msh27UspH+dS80ABUeD67tBSOPsn2/H/w90RnlzvlZ0sDycTepv59m3QP+k68s7Idu1LKR3mTdJ0lDmPtN+ZygYHXl8DWb2Df/ROdvSKbSygmHXvjVnjzebh1Ehz/Y6gcGu/srMaulPJXPjUvgF3i8EbiDb266Rd2nKsAvQfAxN/AfkPildkI1GYwRjez8RJ7aSlIiR2ne9p4+OE58cr0K3allE/ybUZaT+wqW4Gb1RXk2JVS/smb5gUAJ7lMxz7hZUIjMM2PpBXk2JVS/smrpOuYAqzCmHCa5YSxT543pR+SZ1Oc9wxi7EopH+Rd0nV2TRjZqSm0vTSccv9R25q0I/1cGrEtdue9U028OYldKeWPvEu6AGbU0B0fXnyKGbRmJZ1DSX9b34ZdizYni4A77znciSHZ4HMau1Iq+/Iy6QK3Vq79stvymlFc8dQcOu4I0Sm0PdE1jdiOpxnYxb9zlrSc9x7mxBIicfLNm9iVUtmVV6MXABD5HvDSri9t7NqD68+/7PW7Rp3fDRiCXY8gjJ2tVY7dUbcWqM23jidnVEPbTsaBil0plXn5lXRFyoC3gUMijmwEhmLMemfFrUrs0KwQ0BCUyQNBjl0plRn5lnQvB26PceQXGHOv3+EopVSm5U/SFekHfAR0jziyDDgyA0PIlFIq5/KpI+1WohOuAS7RhKuUKhT5kXRFjgPOj3Hkfox5y+9wlFIqW3LfvCBSju08GxZxZCNQhTEb/A9KKaWyIx+edC8lOuECXKMJVylVaHL7pCvSH9t51i3iyJvAURiT2hY4SimVp3L9pPtbohOuAWo04SqlClHukq7I8cC5MY7cizFxt8dVSqmgyk3zgu08exc4KOLIBmznmU6HVUoVpFw96f6S6IQLcLUmXKVUIfP/Sdd2nn0MdI048gZwtLblKqUKWS6edKcRnXDbZp5pwlVKFTR/k67ICcCYGEfuxpi3fY1FKaVyICvNCzGXMBw1VID3gAMjTl+P7TzblPFAlFIqz2Qs6UpdfS/aF+seDDQBrdin6Q57bd648VdPPrD3hc8+Qc+tm3e9dALG1GYkCKWUynNpJ12pq68AJgOTsEm2s9u5nULbMSJMWlDL5LkzqWhpfg04VttylVLFIq2kK3X1A4ElwADiJNtInUON9N+wlkkLak+5+Jm5f045AKWUCpiUk66TcJcBPbH7fSWlpDVsWktK16M73yqlikhKSddpUlgODCKFhLuLMHbL8YNNdVVzGuUopVQgpDpkbDK2SSGdhItzfX/ghjTLUUqpQEj6SdcZpbASOxzM3TVj4f8+godfhfKKRMWGgAG6BblSqtCl8qQ7ATtKwd1XK+HDZSACbyz1UmarU65SShW0VJLuOBKNVHhuAQz9Fpx4Oixd4KXMzk65SilV0JJKus5Ms8EJT3zuKTj+R3DCj+DtV2DTei/FD3HKV0qpgpXsk24ldqaZuw+Wwdov4dgfwuBh0G9feHGRl7KbnfKVUqpgJZt0O5KoPXfpAjjsGOjR0/79+6Ng6XwvZYdJ1DmnlFIBl+zX+RDxEvWOELzyZ2hthfOPsa81N8G2b+Czj2DQAfHKLnXKV0qpgpVs0m0A3Md/vb4ESkrh9wuhvLz99d9cYTvXBl0Tr+xyp3yllCpYSTUvmOqqFuAT1xOWzoeRo6FPf9izd/ufUefBCwsh3BKv+BVO+UopVbBSmRxxFXAjSSxw40EjcIOprrotg2UqpVTeSWWc7qwUr0sUh66pq5QqeEknT2eq7nTs02kmNALTdAqwUqoYpPrEOgVYhR3mlY6wU85NaZajlFKBkFLSNdVVTcBIYCOpJ96wc/1IXdZRKVUsUm6bdRYeH45dDzfZpoZtznW6gLlSqqik1SHmJMxhwAzsxIZEybfROW8GduFyTbhKqaKSyd2Ae9K+G/AQ7FoKYexMs3JgBXaEQq12mimlilXGku5uhdrVwiqxaymEgAad+KCUUllKukoppWLL9CQHpZRScWjSVUopH2nSVUopH2nSVUopH2nSVUopH/1/RcbJqJ/3N3UAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "rbt = RedBlackBST()\n",
    "for (value, key) in enumerate(list(\"NMLKJIHGFEDCBA\")):\n",
    "    rbt.put(key, value)\n",
    "showTree(rbt)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Auch hier erhalten wir in beiden Fällen wieder einen gültigen Rot Schwarz Baum. Im Gegensatz zum Binären Suchbaum degeneriert dieser nicht zur Liste. \n",
    "\n",
    "#### Übung: \n",
    "\n",
    "* Erstellen Sie einen Baum, der nur Rote Kanten hat\n",
    "    * Nicht möglich per Definition. Falls beide ausgehende Kanten von einem Knoten rot sind werden diese durch die flipColors Funktion beide schwarz.\n",
    "* Erstellen Sie einen Baum, der nur schwarze Kanten hat\n",
    "* Was passiert wenn sie als erstes Element zusätlich noch den Buchstaben O einfügen?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAADnCAYAAAC9roUQAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAgAElEQVR4nO2deZgcVdW43zMzWViCgbAlgRAiGbawR0AWhYCoBCFsAoKSBPXjRwQU+RA/EQiCIigoWxAICYiyEwQGiYZNg7IEAVmUiUDYZd+SySSznN8ftyaZqanqrqruqq7uPu/z9APpe+vW6TOnT986995zRFUxDMMwsqGh0gIYhmHUE+Z0DcMwMsScrmEYRoaY0zUMw8gQc7qGYRgZYk7XMAwjQ8zpGoZhZEhTpQUwjLhIS2sTMBoYDLQDi3Ric2dFhTKMiIgdjjCqAWlpHQZMBSYDmwDLgW7c09ogYCEwG5ipE5vfr4yUhlEcc7pGrpGW1oHAGcBJOCe7aoHubTgnfAEwXSc2L09fQsOIhzldI7dIS+soYB4wksLO1k8b8Dqwt05sfiUN2QwjKeZ0jVziOdwFwFpAY4IhuoD3gfHmeI08YU7XyB1eSOEZYAzJHG4PXcCLwJY6sbmjHLIZRqnYljEjj5yBCymU4nDxrh8BnF6yRIZRJszpGrnC26VwEkEx3KkT4Mm/9X1v3m1wyhGFhlwNOFlaWtcqn5SGkRxzukbemIrbpVBOur1xDaPimNM18sZk4u1UiMKq3riGUXHM6Rq5wTtptklKw4/1xjeMimJGaOSJ0biTZgNDe5w9DRp7ra91dsCnt4gydoc3/n9KkM8wSsacrpEnBlMsnnvapbDtLiv/Pe82+NPNUcbu8sY3jIpi4QUjT7STnk02euMbRkUxp2vkiUUUCi2UxgBvfMOoKOZ0jdygE5s7Wdb+WkrDL7T0j0YesGPARi4QEQGO4+Bv/oojvtPE4FXKN3hHRyfa/SM9cKvzyjeoYSTDZrpGxRGRNYFbgUuYe3MTIuW9QXdXE1P2+JqIjC3vwIYRH3O6RkURkV2AJ4EDAVj8Edw+C9rbynOD9jaYczV89P42wD9E5GvlGdgwkmFO16gIItIgIj8E/gKM6tN4/aXw3tvQ1VVa7KurE957y43nWB34nYhcLSKrlTS2YSTEnK6ROSKyPjAX+ClBmcQ6O+DcE6+loeFd3P7a+HR3d/PJR3DaFOd8+zIFWCAiWyca2zBKwJyukSkisg/wFLB3SJcPgYP1xX8djch4XD7cuLGGJTQ0vMBvL9yPd958IaTPZsCjInKst4hnGJlgTtfIBBEZICI/w81w1w3p9ndgO1W9DcCr+DAOuBB3sKGY823z+l0IbKn33NQCbA9cH9J/EDADuFlEhsb4OIaRGNsyZqSOiIzGOb6dC3Q7FzhdVQMrPHj5cHuqAY/F5VLowoUnBuCqAc8CZvmrAXsz2SnAJUDYXrSXgcNV9eEon8kwkmJO10gVETkImAmEzSTfBr6uqn+KPKbLFjYal0uhHVgU5eCDiGwB3IibPQfRBfwIOF9Vy53T1zAAc7pGSojIYOCXwHEFus3DOdz/ZiMViMgquBLtxxbo9ifgG6r6VjZSGfWEOV2j7IjIZrgZZdjugC7gNOC8Ss0oReRQ4ErgUyFd/ov7QZiXnVRGPWBO1ygbXuz0aOBSwqs/vAIcoap/C2nPDBHZGBdr3imkiwI/A85QVcvbYJQF271glAURGQL8FreYFeZw5+B2J1Tc4QKo6kvA7kBYTgYB/g94UERGhfQxjFjYTNcoGRHZHhdOCCu1swxX4XeG5tTgRORLwLXAOiFdPgCmqurt2Ull1CI20zUSI44TcPtrwxzu88DOqnpZXh0ugKreA2wD3BfSZU1gjohc7C0SGkYizOkaiRCRYcAfgF8Tnnh8NjBeVZ/MSq5SUNU3gX1wi3xhx4+/A/xdRDbNTDCjprDwghEbEdkd+D2wQUiXJcCxqnpddlKVFxHZDfcZNwzpsgQ4TlWvzU4qoxawma4RGRFpFJEfAw8Q7nCfBLavZocLoKrzgW1xs/kgVgOuEZFrRWT17CQzqh2b6RqREJERwHXAngW6XQScoqrLspEqfbxtcN8BfkF4GKUVOKxawihGZTGnaxRFRL4MXEPhlf0pqho2K6x6RGQ73A6NsOoTy4HvA5fmecHQqDwWXjBCEZGBInI+cDfhDvchYJtadrgAqvoEsANuL3IQA4GLgdtEZK3MBDOqDpvpGoGIyBjcaa0dQ7oocA4wvd5Oa4nIN4DLcHHdIF7Fnbp7KDupjGrBnK7RDy8vwVXAGiFd/gscpar3ZidVvvC2jN2I29sbRBdwOvBzVU1W/cKoSSy8YKxARFYVkd8ANxHucOfiwgl163ABVPV5XH7gS0O6NOKeBOZ65YkMA7CZruEhIlviZm5bhnTpxOUh+KXlmu2LiBwIXE3hnMHfUNW52Ull5BWb6dY53lHebwKPEe5wFwG7qaol9w5AVefg9vSGJfJZF7hHRH4uIgOyk8zII+Z06xgRWQO3WHYl4WVsbsFlBnskM8GqEFV9Gfg8rsJx2OPjKcBfvfJFRp1i4YU6RVyl3RuBMSFd2oHvAlfYvtN4iMjeuIMk64V0+Qg4RlVvzU4qIy/YTLfOEJEGETkJ9ygc5nD/Beyoqr8xhxsfr9rENriyP0F8CrhFRGZ45YOMOsJmunWEiKyDy/y1b4FuM4ETVXVJJkLVMCLSAPwvbhdDY0i3p3FHiP+VmWBGRTGnWyeIyB7A74ARIV0+Af5HVa/PTKg6QUQ+i4udbxTSpQ04HphlTxa1j4UXahwvM9h0XHLuMIf7OC4zmDncFFDVv+N2N4TFcFfFPWFc5y1uGjWMzXRrGBHZADe7/VyBbhcCp6rq8mykql+8jGXH4nQ+KKTbf4DDVfXxzAQzMsWcbo0iIvvh4rfDQrq8B0xW1bsyE8oAQES2xu0c2SykSwdue9mvLdxQe1h4ocYQkUEiciFwJ+EO9y/AtuZwK4Oq/hMYj6ucHMQA3Gz4DhFZOzPBjEywmW4NISKbADfgUhAG0Q38BPiJJWHJByJyJHA5EFZ94nXga6r6l+ykMtLEnG6NICJHAL8BhoR0eQM4UlUfyEwoIxIiMhb3Y7l9SJduYDpwjv1YVj/mdKscEVkNVyZnaoFuLbj47bvZSGXERUQGAT8HTizQ7QHcD+cbmQhlpII53SpGRLbCLchsHtKlAzgVuNAWZKoDEdkfF+sNqz7xLnC0qt6dnVRGObGFtCrEywx2LPAo4Q73RWBXVb3AHG71oKp34I4Q/zWky9pAi4j8QkTCCmUaOcacbpUhIkNxScZnAINDut2Aywz2WGaCGWVDVV8DJgBnEZ6x7PvAfK+sklFFWHihihCRnXAOdXRIl6W446RX2+y2NhCRPXEHXIaHdPkY+Laq3pidVEYp2Ey3CvAyg50CzCfc4T4DjFfVmeZwawdVvR8XbvhjSJc1gBtE5AoRWTU7yYyk2Ew354jIusC1wBcLdLsC+K6qLs1GKiNrvIxl3wPOBZpCuj2Hy1j2TGaCGbExp5tjRGQvXDLssMKGHwPfUtWbspPKqCQisiMuxLRxSJd24ATgKnviyScWXsghItIkImcDfybc4T6KO8prDreOUNVHge1wi6lBDMY9+VwvIp/KTDAjMjbTzRkiMgr4PbBrgW7nA6dZZrD6xctY9k3cwZiwXSwv4TKWPZqZYEZRzOmmhLS0NuEWvQbjHvkW6cTmzoLXiEzClfJeM6TLu7hS3mGLKkadISLjcAdktgjp0snKAzIFKzknsVkjPuZ0y4i0tA7DHcedDGwCLMedm2/A5U9diEu3OFMnNr+/4jqRwcB5uO1eYdwPHGVHQA0/3q6FXwHfKtDtj7iTbO/0uTahzRrJMadbBqSldSBwBnASzmALbd1pwxn0BcB09tt0NG6msm1I/25v7J9ZshOjECJyGC6eG1Z94k1c7ob7S7FZndhsYa0SMKdbItLSOgqYB4yksOH6aWPJJx9z/P5r8PYbYde9hkvrF3Yk1DD64J1QuwH4TEgXZexWv+aCmyciEt9mXarJvXVi8yslilq3mNMtAc/hLsAlJwmr9hpOVyd88hF872B4501/6x3AVFV9r2RBjbrCy8nwU9xR4b6sMxwuvBWGDFUaGyXB8F3A+8B4c7zJMKebEO/x7BlgDEkcbg9dnfDfV+G4/dz/u5ja/wIX2z5LoxREZF/gGlySHGgaAJfeBetvAI1h5ysi0YVLqLSlTmzuKFnQOsP26SbnDFxIIbnDBWf8w9aDI6aBK0r4WVW9yByuUSpe+sdtcXl4nY0NW7dUhwvO5kcAp5c6UD1iM90EeCu+rxG+PzI+nR1d/PnWMXrJ6fbIZpQVEWlk+KifcMmdP2RQ+UwWt61spO1qiIfNdJMxFbfiG9I6AQ7aGg7dDg4bDycfDndfD90Ftkk2Ni3jy4d/tfyiGvWOqnZx5Z8/oGlAe8GOUyfAk3+LM3Q3hSuWGAGY003GZIqt+p5+Odz8BFx9Pxz6Lbj1SrjoR+H93V7LyWWU0TB6M5nGxrJOc3HfgcllHrPmMacbE+/UziaRL1htCOy0F5zyK7h3DixqLdR7rDe+YZSN2DYbD7PZmJjTjc9o3A6DeGy6Nay9Pjy3oFCvDsLz5RpGUkaTxGajYTYbE3O68RlMoXhuIdZa1+3LDaeLci7OGYYjuc0Wx2w2JuZ049NOUr299xYMKZhtr9Eb3zDKSXKbLY7ZbEzM6cZnERC/CmvrP53T3WKHQr0GeOMbRjlZRBKbjYbZbEzM6cbES3X3n8gXtC2GR++H806CPfaH0ZsW6r3QUukZ5SaWzXZ2wPJlK19dRc3RbDYmtuqYjNnAmRTaNnbWsdDYCNIAG24Ck6bAlw8vNGYbMKucQhpGL2ZTzGYBzvx2338fdix8/Xthvc1mE2An0hIgLa1r4bItlXMBwU73GKlhNpsfLLyQAM/ILsD90peDNuAXZrxGWpjN5gdzusmZTnf3mxFiXoVxiclfB84qh1CGUYDpqL5OV1dpj7dmsyVhTjchOrF5OSdMephPPoqy2BBMVycs+aSL5cv2thR5RtroxOblnHToXXzyoZRks4s/Vt5764tms8kwp5sQEfkii54/ku8dDP99DdpjPrW1t7k8usfvP5CDtp6QjpSGsRIR2YGFTx9fss2ecEATR3/usHSkrH1sIS0BIjIUl8B8JOCSQx8xDQ6cAk0Dl9LQsEroxcuWKogw52q4/tKeWfLHwDhVfTUD8Y06xCt+ugDYElhps5OmwIAB7TQUSIazrF0Bv812ADuo6tPpS19bmNNNgIhcA3yjX8PIjU/hN/coLvPSWJxhduFO7QwAFvL4Xxdw/vePZnG/48DzgH0sebmRBiLyc+CUfg3rjfwFM+97i0I2++8n7+fMb09j8Uf+8j5PAjupqhWqjIE53ZiIyCRgTkDTvTin2Q0rMjuNxm3RaQcW9WwiF5HfAkcFjHGcqs5IQ26jfhGRXYD5gN9pPgXs2OM0i9jsebgyUn5+oqpWQSIG5nRjICLr4MIK6/qaPsGFByJVfRCRNb1xRvia2oCtVfWFUmU1DAARWQ03I/WnduwAxqvqPyOOMxh4HNjC19QF7KyqBdPnGSuxhbSIiIgAM+jvcAFOjOpwAVT1A+CYgKZVgdkiUlrdNcNYyc8IzqV7RlSHC6Cq7biQWpevqRG41nPKRgTM6UbncODggPfvwh2xjIWq3gNcEdC0G/DduOMZhh8RmQAcH9D0CHB+3PFU9XHg7ICmzYGfxB2vXrHwQgREZAQuHLCmr+l9XFjhzYTjDgH+Sf8k0MuA7VX1uSTjGoaIrAE8DYzyNbUD26rq8wnHHYBz2tv5mhT4nKrOTzJuPWEz3SJ4YYUr6e9wwS18JXK4AKr6CcE1pgYB13gGbhhJuID+Dhfg1KQOF0BVO3BhBv+OBcHZ7OpJx64XzOkWZyqwb8D7N6vqjaUOrqoPAr8OaBoPnFrq+Eb9ISITCV4zeBC4uNTxVfUZIGjHwhjg56WOX+tYeKEAIrIR7hFtiK/pbWBLVX23TPdZFXgCaPY1deK29DxRjvsYtY+IDMOFwtb3NS0BtlLVl8p0n0bcNrSdA5r3UdU/l+M+tYjNdEMQkQbgavo7XIBvlcvhAqhqG3A0/etYNeEe2QaV615GzXMx/R0uwEnlcrgA6pLeHA0sDWi+WkQK1qWqZ8zphnMcEJQT4RpVvaPcN1PVhwl+NNsKOKPc9zNqDxE5FDgioGkubl2irKhqK/CDgKYNgF+V+361goUXAhCRsbjTOv4cCq/hHtE+TOm+g4DHcI62N93Arp5jNox+iMh6wLPAMF/Th7gdNq+ndN8G3BH2PQOaD0hjglLt2EzXhxeruob+DhfgmLQcLoCqLsOtDPvz7jXgwgyFS60YdYm3w+Zy+jtcgOPTcrgA3rH3qbhTmX6u8GLMRi/M6fbn+8BnA96foap/SvvmqvokMD2gqRn4adr3N6qSo4BJAe/PAX6X9s1VdREQVEhtPeDStO9fbVh4oRciMg53vtxfrvpFYBtVXZyRHE3A34DPBDRPUNX7s5DDyD8isgFut4J/4epd3A6btzOSQ3CnM4O2Vx5eju2VtYI5XY8iJ20+r6p/zViezXHbyPw7F17GxZWDHueMOsJzdPcA+wQ0H6yqt2UsT6GTm1uq6n+zlCevWHhhJT+iv8MFuDBrhwugqv/CyeRnI+CXGYtj5JNvE+xwf5+1wwVQ1TeA7wQ0rQVc6f1I1D0208UrY+Jmuf7sXv/G5UAI2ouYOt6i3gO4JDh+9lXVP2YrkZEXRGQMLm/Har6mN3G7FSpSpddzrDcTnBxqiqrOzlai/FH3TrdfGZOVdAG7qOqj2Uu1EhH5NO7L5d+58Abuy/VB9lIZlcTbpvUAsHtA80RVvTtbifri5Z1+FljH1/QxLjQWOQ1qLWLhBbdTwO9wAX5WaYcL4CU0PzmgaQRwUcbiGPngRIId7lWVdrgAqvoOLvThZw1gpvejUbfU9Uw3ahmTSuM9ss0FvhDQnPmCiVE5iiywbq2qH2cvVTAici3w9YCmaap6Wdby5IW6dbrlKmOSFSKyIW5leA1f0zu4MEMmW4OMylFtWwm9slRP01M1eyVtuC2Y/8leqspTz9P8cylDGZOs8MqznxDQtA4ww1aG64IfEOxwL8qbwwUrSxVGXc50RWQv3HlxP48Au6mq/xhuLvAc6+3A/gHNR6lq6qePjMogItvg8nL4E9svxFWCaMteqmiIyOXA/wQ0nayqdbf9se6crpdy7p+UuYxJVojI+rgwQ6aJTYzKISIDcQ53a19TN26S8PfspYqOV5bqKWBjX1NdlqWqx/BCWBmTH+bd4QJ4p3qOC2gaClxlYYaa5HT6O1yA8/PucGFFWaopAU11WZaqrma6IrIfcGdA04O4hQh/EvHcIiI3AIcFNH1bVcueO9WoDCKyE27xzD9BehbYwctMVxWIyIUEV7o+XVXrpppw3TjdrMqYZIX3eZ7FZXLqzWLc51mUuVBGWRGRVXDbwzb1NXUCO6nqP7KXKjlFPk/dlKWqp/BCJmVMskJV3wO+FdC0OjCr3jeg1wjn0N9BAfyk2hwugHecPqws1bX1UpaqLr6YWZcxyQpVvROYFdC0B8GJR4wqQUQ+T/Cj+OPAzzIWp2yo6iO47Zp+xgFnZitNZaj58EKlyphkhbcb42lgQ19TVezGMPpTZLV/B1V9Nnupyoc3o32UKt2NUSo1PdP1VvKvoAJlTLJCVT/ClUvxMxi3Ab0pY5GM0jmf/g4X4LRqd7jQpyxVh6+pLspS1bTTxZ37DjpIkEkZk6xQ1XkEl0XZmeBkOUZOEZEvEnyQ4CHgwozFSQ1VfYrgslRjqeLwSRRqNrzg5Sp4mgqXMckKL5fEU8CnfU0duEfSp7OXyoiDiAzF7bCpi1wF1ZZLolzU5EzXCyvMpL/DBTi21hwugKouwa0M+39FB+BWhv1134z88Wv6O1yAU2rN4QJ4x+2PxsWq/czyYts1R006XdzjWVAaxN+r6q1ZC5MVqvoQwaV8tgVOy1gcIwYiMgkX5/RzLzAjY3EywytL9X8BTTVblqrmwgt5LWOSFV4ljH8Am/uauoCdVXVB9lIZhfAqLTwDrOtr+gRnszVdacHLNnY/wYnZa64sVU3NdL0DAbPp73ABvlnrDhdAVdtxM6YuX1MjLswwOHupjDC8UNgM+jtcgBNr3eECqGoXLjfDkoDmmSKyVsYipUpNOV1yXsYkK7zZ7DkBTZsDdXPGvUo4nOAijnfhJhB1QYGyVMOpsbJUNRNeqKYyJlngLZw9TP+y8gp8TlXnZy+V0RsRGYELK6zpa3ofF1Z4M3upKkeRslSH1Mp6TE3MdL2tJ9fQ3+GCK/tcVw4XwKvvdjTgr/MmuA3oq2cvldGD52CupL/DBTiu3hwugLoZ4DHARwHNl4tIUAim6qiqma60tDYBo3GnrdqBRTqxuVNEfgScHXDJRap6YoYi5g4R+QHBZ90vU9VpEK7XzISsYQrY7DHAVQGX3KSqQSk76wYR+QZuEuXnduAgVdVqttncO11paR2GO+Y6GVfTbDnujHYDMIhl7a/y+4s3Yu7NjSzu8wOZ+zImWeCtDM/HnU5byZCh8KNLrmTcZ3YlSK9Of7OBmTqxueYXIMtJUZvtWL6I3100intuGuSz2bdwYYV3MxY5V3hPAXOAA/o0DBkK3zv3enbccxuq2GZz63SlpXUgcAZwEk6x4eex25eCCNw+C66/FDo76iJxRlREpBlX+XgVmgbAEdNg0hQAZdDgQpUm2nAGfQEwXSc256IkfV4p0WYBDlDVOzIRNuf0SVTVx2YVBq1S6NLc22wuna60tI7CFY4cSSHD9dPeBu+9DeedNEP/80xQSZu6RUROYJ3hv+bs2TBsXRgcK6dIG/A6sLdObK75LUxJKNlmf3r8Lbro+UPTkq8aEZFDWWf4TbVms7lzup7xLgDWwu0tjUdXl9LQ8C4i4/Om7EoiNz2+Edq9kFVWG0BjosRjXbhVddOrj9JtthOk4V0aGnYw3a5EWlpHseSTVgavMqiWbDZXTtd7PHsGGEMS411JF/AisKVObPanj6s7VuhVdQwuxpsU06sPs9l0qGWbzduWsTNwj2elKBnv+hG4KqpGj15LM14wvQZhNpsONWuzuZnpeiu+r+G2gPRn6gT48F1oaITGJth8O5g2HdYZXmjYdmBknlcy06aoXqGvbnv4zT0wzF/zcgV1r1eIqFuAU78Oe+4PX4wUsq173UbyBcvb4ap5K+O8c2+G+++Ac38bNmxu9Jqnme5U+hes68vpl8MtT8Bv58PQYfCboidauwmuqlBPFNcrrNRtzyvc4YLptYdouo2H6TaKXru64I5r44yZG73myelOJuqq78BBsOuX4JUXivVc1Ru3nplMnNX0aJheHZMx3abBZIrp9aBj4LarYXHkw6a50WsunK53umSTyBe0L4W/3g2bbhOl91hv/Lojtl7jUbd6BdNtWkTW69hxsNWOMGdmnOFzodeKC+AxGne6pHB1g7OnQWMjLG2DoWvBWZEU3uGNX3OZ9yMwmih6hZW6BWfMp11W7Ip61ivE0W186lm3o4mq1yNPgFOOgP2Pjjp2LvSaF6c7mCixsdMuhW13cfGcR+51CxQzWmDNdQpd1UWxhY7aJZpeYaVuo1PPeoU4uo1PPes2ul5HN8Nn9oCbr4AN/aUBA8mFXnMRXsCtLEaXpbERdtkHGhrg2ceL9vbGr0fi6TUe9axXMN2mRTy9HnkCzL0J3nsrSu9c6DUvTncRcR7TVOHheS6IXvwXboA3fj2yiHQef6G+9Qqm27RYRBy9jtgIdt8X7gzdKtabXOg1F07XS8lWPM5y1rFwyHbw1e3h2l/B986FjcYWu2phtaR8KzeR9ZqMutUrJNBtobRC/alb3Say2SOmuRwWxcmFXvMS0wWXku1MwraKXH1fkjHbgFlJBaoRZlNIr5BEt6ZXx2yK6RZg6WIYEpSrPBDTbVxfsM5wmPN0sTFzo9dczHQ9ZlJ+eRrIiaIriOk1PYrr9uWF8OoL8Gl/ceZQTLc1brO5cbre8bwLcL9I5aAN+EUejv1VEtNrehTV7azz4cdTYfLJsO7IKEOabql9m81N7gWwjE1pYXpND9NtOtSyXnMz0wXwsrzvjcuB2ZVwmJ4cmnvnRcmVxvSaHqbbdKhlvebK6QJ4yYbH09nxSsQVyd4swf2q5SppcR5YoVd4kY7l8VZwu7vaMb2GskK33V2LzGbLRx+b7eyI5zS7OpeRU73mzumCp+zDd7yCP1wDy9pdroVCtLe5VG/tbZfiHiNypeS8oBObX2H+PVtzx7XtkfW6rB3m3/MUpteC6MTmVzhip5/Estll7fD+OzMx3Ybi6WUcd1//fiy93veH/5BTveYqptsbEVkA7MDqn4IvHAx7HwQbjOmisbEd1S6WLV2DxiZ442WYdyv8+TZY/NHXVPX6SsueZ0RkD+D+PnodsRE0DViCSBedHYNQHeTT6+vAKFVN69hrTSAidwL79bXZjbtpbFqKahfL24fQ0Cg+3X5fVS+otOx5RkQ2Bf7dz2Ybm9poaOikq3Mg3d2DfXpdAqyby2rgqpq7Fy7LkPZ7rbn25tz1/Cbc9fw4mre+noZGf5/bKy173l/AjH56bWq6c4VefzxjBxoaOwL0v1ulZc/zC1gTl6ilr95WHTJhhW7HfeaiAJt9pNKy5/2Fq/rQV2+NTY+t0OvMezensfH9AJs9tNKyB36eSgsQouQfBijwCV+fCQF9lgFrVFr+vL5wh2HeDtDbkb5+dwf0ubjS8uf5hcvV6tfZG0Bjrz6bB04mYHSl5c/zC7eLwa+zk319Zgb0ubnSsge9chnTBQ4LeO9G378fxDmQ3gwEDkhFotpgD8Cfkm0ZcIfvPb+uAQ6R0utV1TJBNnuzqq5YeVfVfwFBR6e+mppUVY6IbAlsGdB0s+/fQTY7UURWL79UpZE7p+vFb4Kyk9/U+x+eMd8S0C/I+A1HkG7uVtVPfO/djntU7s36wOdSkarKEZFhuO1Nfm6K+J7ZbDhBunlYVV/2vXc/8J7vvVWAr9+0hkYAABGqSURBVKQiVQnkzukSrOQFqvpiwPtBv277iEjkg+71gogMAA4KaOqnQ1X9CLgnoK85h2AOon8ek9eAvwf0DbLZ7UUkrSoUVYuICNGeelHVDuDWgL65s9lqcbpBhgowHxc3680A4MCySlQb7A2s5XuvDbgrpH+Qzg8WkTwlScoLQTZ7kwbs9lDVhcATEceod7YBmn3vKf1DCz0E2eyXReRTZZWqRHLldEVkHLBFQFPQIxmeUQf9AcyA+xOkk7tUdUlI/zvpn/B5bdwCpuEhIusBewY0hU0UwtrMZvsTpJP5qvp6SP8HAX8289yt8+TK6RKs5L+raqENzkEGvJeIFKzhU0+IyCBgUkBTqGPw4rwtAU226NOXg+n/PXoJeKzANUGTiK1EJHIqslonTmihh2pZ58mN002iZI+HAb9TbiQ4flmvfBHwP2ItBv5Y5Log3R8kImlVTKhGwkILoaeOVPUl4NGIY9Ur44GNfe91E+xUexO2zuMPrVWM3DhdYFvAXwaiUPzGdXDGbSvChQnSxR9UtciZSu6mf3q9NQleqa87RGQEsHtAU7GJQlifw7zJhxFssw+oarFiaA8B/vBDEzla58mT0w1S8l9V1b9QFkSQAX9eRNYvUaaqR0RWAfYPaCrqGLx4750BTfaD5jiU/oV4FgJPRrg2aDKxGbBVqUJVOyLSQHAYK4rN5n6dJxdOt4TQQg+P4zIK9aYBOKQUuWqEfQH/BvGPgD9FvD7obzBJRCpeyjoHBNpsodBCD6r6Km5WFmXMemNnYEPfe13AbRGvD7LZCXlZ58mF0wU+A4z2vddN8L67fnhGbivCwQTpYI6qLot4/R8B/+GJNXBx4rpFREYBnw1oijpRCOtrIYZgm52nqu9GvP4RwH94ohG36Flx8uJ0g5R8f4T4TW+CDHg3EdkgoUxVj3cEcr+ApsiOQVXbgT8ENNX7D1rQ4+9zqvpMjDFuwa1b9ObTwPaJpapyvKPmhwY0xbHZXK/zVNzplhK/8fFP4PmA94P+gPXCfrijkL15D7g35jhBf4v9RaRwFdzappRwGACq+iZub2mUseuF3YDhvvc6cEfT4xC2zuMfO3Mq7nRxj2j+2Wgn0eM3gIUYQgj67Ld5Rybj8CfgQ997q+HixXWHiHwat6XJT9yJQtg1X63jEEOQzc5V1Q9ijvMP4AXfe0IO1nny4HTD4jf+5BVRCDLgnURkdIKxqhoRWQP4ckBTbMegqsuBOQFN9fqDFvRk9pSqBj1pFeNW+tcA2wjYKcFYVY13xDzIKSax2dxOwirqdMsRv+mNqj6Hy73ppx5PUR0ADPK99zbBj7NRqJrUeRlQcmihB1V9B7gv4j1qnT2Ilno0KkF/k11FxL8zIlMqPdPdHZcysDfLiR+/6U0uf90qQNBnvkVV4xWlXMl9VEnqvDQpkHo0kdMtcO2h3npHPRGWevTjhOM9Dfw74P2KrvNU+o8aNAOdq6r++GEc6j51npfacp+ApsSOoZpS56VMkM2GpR6NyhzcOkZvRgK7lDBmVREn9WhUCoQYKvrkWzGnW874TW8KpM6rpxDDJFyKy968iUuFWQpVkTovZcoWWuhBVd8n+LBKPf2g7UX/1KNLCU89GpWgrWMVXeep5Ex3D4LjN0HHTuOS2z16GRFWOqbUar5VkTovLWKUjklCkM3WU4mkuKlHI5HHdZ5KOt1yx296E2TAW4vIZmUYO9eIyNoEJ6QpaTYG1ZM6L0Wilo5JQt2WSPJSjwYlpCnZZguMUzGbrYjTTSN+0xsvvhaUz7QenMNBuCOPvXkVlwKzHOQ+dV4alCE/SEHqvETSPgSnHr27TOPnap2nUjPduKVjklCv59ojl45JSO5T56VE3NIxSajXEklBNntHhNSjkchbiaRKOd1U4jc+gkIMmwPjyniPXOGVjtkjoKlcj2lVkTovJeKWjklC3ZVI8lKPBq0JlM1mC4xXH043SemYJHip8/4W0FTLzuEQ+v9NXwQWlPk+uU6dV27SDi30UKBEUi3b7JcJTj06t8z3yU2JpErMdJOWjklCvYUYYpeOSUiuU+elQNLSMUmotxJJQTZ7e4zUo5HIU4mkSjjdpKVjkhCUOm8TYLsU7lVRRGQkLkOTn3I/puU+dV4KJC0dk4QWwB9mGwp8IYV7VRQRWY0SU4/GJBeTsEydbimlY5Lglfr5S0BTLTqHoNIxrcBTKd0vt6nzykkZU49GQlXbqJ8SSfsB/vSg7wPzUrpfLkokZT3TLbV0TBLqJXVe4tIxCclt6rwyU2rpmCTUS4mkcqUejUReSiRl7XRLLR2ThFtx8bfejAZ2TPGemSIiG+Gcg5+0HtNynTqvzJRaOiYJ9wD+Q0JDgC+leM9M8VKPBuVjTs1mC4yfaYghM6dbjtIxSVDVt6n91HlBj7/PquqzKd83LHVeTZRIKnfq0ajUSYmk/emfevQd4IGU71vxEklZznTLVTomCWEhhkpnWSsXqW9nCiGXqfPKSLlKxyQh6O/3lRoqkVTu1KORyEOJpCydTqbxG/99qNHUed5Rxh0CmlJ3unWwi6FcpWOS8GfAf5/VgIkZ3DtVvNSjQdWks5gohN0ns3WeTJxuOUvHJMFLnffngKZacA5BoYUnVbU1o/vXZImktFKPRqXGSySllXo0KhUtkZTVTLfcpWOSEPRlqYXUeZUKLQD5TJ1XJvagvKVjkhBWImlIhjKkQVjqUb8jTIVKl0jKyukGfQFTj9/4CEudt3uGMpQVL1Xl1gFNQY/8aVKLuxiCbLZcqUejch/g3yUxmOAF6apARIaRUurRmFSsRFLqN8hB/Aao2dR5QY7hsRJLxyQhV6nzSsVLPRp0pDlrm+2k9kokpZ16NCoVK5GUxUw3LH4TtEk5bYJmgNWcOi8w10LWQuQtdV4ZCCsdE5SMJm2C/p7VXCIpraomsajkOk8qzkZaWptwBxAGs/FmU3h5IXT3CddkFr/xcQcudd7Kkz0Njeuw5/5HSkvr417bIp3YnGXYIxYrdHvbzHEMH7UFb73u123mTtfjRvw5LRqbDpOW1htx+s61bvvY7NitvskLz/n1epeqLq6AaD0lktbr9d5ABg0+UFpa51NNun3kvpEMH7VngM1mHVrofd++C/yNjYfIDY9dzJBPDSQlvUq5TolKS+swYCowGZdUZjnarbQvHULTQHjzZZh3G/zpFlj80a6qGpR2MXVE5FaGDD2ILxwMex8Ew0eBaicDB7XhZv6DgIXAbGCmTmx+vxJy9iZQt8uXDaCrc1Af3d53+2P6wbsVOWknIhsDLzJkKH1029jURkNDJznUbbDNajftS9egaYDfZg9R1aBH/fTlFLkEmNZHtyNGK01NS3CnLatDtx3Lm+jsGNzHZufd9jIff7BxisfVw2V0TwtvM2TowD4229C4lMbGDlLSa8lOV1paBwJnACfhDCB883b7UmhoUJoG/IyGhuk6sdm/sJUq0tI6kGcX3MAm4w5EFQb7z2r0occJXwBkLisk0O2AAZ00Np1HBeSVltaB3HndS+xzyIi86za+zQog5zFw0I8rYgdrrr0nX/n6fUyaQs3ptqmpk6YBlbPZuTc/wx5fGZulXktyutLSOgqXEWgkhZTbnzZcyZe9dWLzK4kFiMEKWVVHEu9UT+ayQpXqtrNjI5oGxMn7WjlZq0Cv4MmrOo/l7ZswaJU4m/dNtwVYabOdo2hq8m9nLUTJsiZ2up7QC3ALDkn2unbh0riNT1vR1SQrVJe8Jmt6VJO8JmuM+ydxut4jxDPAGJIJ3UMXrpzMljqxOZXjwNUkK1SXvCar2QGYrHFlTbpl7AzcI0Spp7kagRHA6SWOU4hqkhWqS16TNT2qSV6TNQaxZ7requRr9N52FcSpX4eX/g3XPQTFw3ztwMhyr7hGlvWBO+H2WfDaS7DKajBmM/jqsbDl+MxkjSTv1Anw4bvQ0Mte9joQ/l/Bv3vldPtgC/xhNry80C1SrLcB7DUJ9v0aBOcWqawdgNPxCWfDtkX3yFfWDnrL+GALXHYmnHYpbBW6eSV73U6dAO+/Ddf8BT7Va9vz8Qc43zDzXmcTeZC1t8w937HBq8D4z8P/nOb8QjCxZU0y051K/6TgfXnrNXhugftiPRIpc2O3N265KS7rnFlw5U+dk73uIZh1v3MK4XKnJStEkff0y+GWJ1a+CjtcqJRub7sarjwHDjoGfjsfrvsbTJsOz/0DOkOfxipnB/GprB30cO8cuPwsOPM3hRwuVEq3642Ev/Q6U7LoeVjurzLfj8raQc937FdzoPVpuHFGod6xZU3idCdTbGXyvtth023cLOzeSKlHV/XGLTeTKSTrkk/gdxc5x7XLPjB4VWgaADtNgKk/CLsqLVkhim7jk71uV+j1DNjtS7Dq6u4H+NNbwP/+stCTT2XsIBmVt4N7boSZ58JZV8HmRXNwV0a3ex7g/EEP994OEyYVGzMfdrD2ejB+d/ekFk5sWWM5Xe9kSfHz9Pf9Afb4Cuz5FfjHfPggUmWTsd74ZSGSrP9+ApYvg8/GLrRaVlkhhm6Tka1u//0EdCyHnfdKMnz2dpCcytnB3dfDdb+Gs6+BsZHrKmav2822hbbF8OoL0NUFf70b9gyqTduPytvBO2/Cgr/AmM2L9Ywla9yZ7mj6Z+rqy7ML4O03YLcvwybjYPiG8OBdUcbu8MYvF6MpJuvHH8Iaa0Jj7L9tuWWFKPICnD0NDhu/8nVPpFO/2er24w/66/Xkw528B20NzzxWaOzs7SA5lbODJx5yT5Ojm+OMXRnd7nmAm+E++RBsMAaGrVf0EippBz3fsVO+BuM+40KPhYkla1xvM5hiMZF7b4ftdl0ZOP/8fi7uNGlysbG7iLLQEZ3isq4x1DmIrs64jrfcskIUecEtlhRf5PGTrW6HBOj1Fze4/x79Oegu+DGzt4PkVM4Opk2HGy6Di34EJ/40bGHST2V0O+EA+MFRbq1nwgFRx66cHcT/jsWSNe5Mt73gNcvaYf4f3UzmqF3d6/Zr3Erli0GltPrQ6I1fLgrLCrDZdjBwEPx9Xtyxyy0rRJE3OdnqdrPtXNz24UTl77K3g+RUzg6GDoNzZsOzj7udC9GojG7XHel2KSx40K2dRKNm7SDuTHcREL7/6+F5bqvFJXfCgF7ZHM/9rgumjzm10NgDvPHLxSIKyQqw2hA48gS3+tvY5GboTU3w5N/gn4/A1FOykhWiyJucbHW7+hpwxDSYMd3lCthhdxi0ilu5bl9abOzs7SA5lbWDYevBT6+BU490O3C+9X/Frqicbk88BxZ/5BaruyIl7apZO4jl+b0UZ/8J7XDvHJepZ90RsOY6K1/7Hen2whZW9sJyplArKmsPB06BY06FGy+DIz8Lk/eAu34Hnw1Kbr+CssoKMeQ961g4ZLuVr7OnRRk+e90e8i2n11uvgqN2ca9LTocpJ8Pm2xW6sjJ2kIzK2UEP6wyHc66Bh+bC7F8W61053Q4fFWfBD2rYDpKsDs4GziRo68VZM4Ov2H1f9wqnDZiVQJZizCZM1t7suX/UFVVIT1YoJu/VQWWdilI53cbTK1TaDiCOjvNjB+tvCLOLlhvMXrdhumxsgrueLzRm5ewg/ncstqxJYhwzE15XTI40lFxNskJ1yWuymh2AyRpb1tgCeMfdLsB5+HLQBvwijeOU1SQrVJe8JqvZAZisJJA1qdefjsspWWrJnS5vnLNKHKcQ1SQrVJe8Jmt6VJO8JmsMEjldL2v63rickkmF78lJuXeaKfKqSVaoLnlN1vSoJnlN1ngkjm94yXvH43JKxp2uL/GuyyQZdDXJCtUlr8maHtUkr8kanZKCyt5NxwEX4jYHF/sAbV6/C3HJfzMre1JNskJ1yWuypkc1yWuyRqOc1YDXYmX1z7G488hduNMaA3AVNWcBs3JQqbRqZIXqktdkTY9qktdkLXC/NCofr6hz784jp1I7vlxUk6xQXfKarOlRTfKarL57VKDcvGEYRt2SVgIIwzAMIwBzuoZhGBliTtcwDCNDzOkahmFkiDldwzCMDDGnaxiGkSH/HzsN06k8kYEPAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "rbt = RedBlackBST()\n",
    "#rbt.put(\"O\", 0)\n",
    "for (value, key) in enumerate(list(\"ABCDEFGHIJKLMNP\")):\n",
    "    rbt.put(key, value)\n",
    "showTree(rbt)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Als letztes schauen wir uns noch an, wie sich die Höhe verändert, wenn wir immer mehr Schlüssel in den Baum einfügen. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "def randomlyFilledRedBlackBST(num):\n",
    "    bst = RedBlackBST()\n",
    "    keys = list(range(0, num))\n",
    "    random.shuffle(keys)\n",
    "    for key in keys:\n",
    "        bst.put(key, \"value\")\n",
    "    return bst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy\n",
    "\n",
    "Ns = [100, 1000, 5000, 10000, 20000, 50000, 100000]\n",
    "\n",
    "numRuns = 5\n",
    "heights = []\n",
    "\n",
    "for N in Ns:    \n",
    "    avgHeight = 0    \n",
    "    for i in range(0, numRuns):\n",
    "        bst = randomlyFilledRedBlackBST(num=N)\n",
    "        avgHeight += bst.height()\n",
    "    heights.append(avgHeight / numRuns)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pylab as plt\n",
    "fig, ax = plt.subplots()\n",
    "ax.plot(Ns, heights)\n",
    "ax.plot(Ns, 2 * numpy.log2(Ns))\n",
    "plt.legend(['Höhe Rot-Schwarz Baum', '2log2(N)'])\n",
    "plt.show(fig)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Wie erwartet wächst die Höhe logarithmisch und bleibt weit unter des theoretischen Worst-case Bound von $2 \\log_2(N)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}