tries.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Die Hilfsklasse Alphabet"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Auch hier benötigen wir wieder die Hilfsklasse Alphabet, die wir schon im Notebook zum Thema Stringsortierung kennengelernt haben. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Alphabet:\n",
    "    \n",
    "    def __init__(self, chars):\n",
    "        self._inverse = [None]*len(chars)\n",
    "        \n",
    "        self._alphabet=dict()\n",
    "        for (i, c) in enumerate(chars):\n",
    "            self._alphabet[c] = i\n",
    "            self._inverse[i] = c\n",
    "    \n",
    "    def toChar(self, index):\n",
    "        return self._inverse[index]\n",
    "        \n",
    "    def toIndex(self, char):\n",
    "        return self._alphabet[char]\n",
    "    \n",
    "    def contains(self, char):\n",
    "        return self._alphabet.contains(char)\n",
    "        \n",
    "    def radix(self):\n",
    "        return len(self._inverse)\n",
    "    \n",
    "lowercase = Alphabet(\"abcdefghijklmnopqrstuvwxyz\")\n",
    "uppercase = Alphabet(\"ABCDEFGHIJKLMNOPQRSTUVWXYZ\")\n",
    "ascii = Alphabet([chr(i) for i in range(0, 128)])\n",
    "extendedAscii = Alphabet([chr(i) for i in range(0, 256)])\n",
    "DNA = Alphabet(\"ACGT\")    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die folgende Klasse implementiert die wichtigen Operationen zum einfügen / löschen und suchen in einem Trie."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Trie:\n",
    "    \n",
    "    class Node:\n",
    "        def __init__(self,rChildren):           \n",
    "            self.value = None\n",
    "            self.children = [None] * rChildren\n",
    "    \n",
    "    def __init__(self, alphabet):\n",
    "        self._alphabet = alphabet\n",
    "        self._root = Trie.Node(alphabet.radix())\n",
    "    \n",
    "    def get(self, key):\n",
    "        node = self._get(self._root, key, 0)\n",
    "        if (node == None):\n",
    "            return None\n",
    "        else:\n",
    "            return node.value\n",
    "    \n",
    "    def _get(self, node, key, d):\n",
    "        if node == None:\n",
    "            return None\n",
    "        if d == len(key):\n",
    "            return node\n",
    "        c = self.alphabet.toIndex(key[d])\n",
    "        return self._get(node.children[c], key, d + 1)\n",
    "            \n",
    "    def put(self, key, value):\n",
    "        self._root = self._put(self._root, key, value, 0)\n",
    "        \n",
    "    def _put(self, node, key, value, d):\n",
    "        \n",
    "        if node == None:\n",
    "            node = Trie.Node(self._alphabet.radix())\n",
    "     \n",
    "        if d == len(key):\n",
    "            node.value = value\n",
    "            return node\n",
    "        \n",
    "        c = self._alphabet.toIndex(key[d])\n",
    "        node.children[c] = self._put(node.children[c], key, value, d + 1)\n",
    "        \n",
    "        return node\n",
    "        \n",
    "    def delete(self, key):\n",
    "        self._root = self._delete(self._root, key, 0)\n",
    "    \n",
    "    def _delete(self, node, key, d):\n",
    "        if node == None:\n",
    "            return None\n",
    "        \n",
    "        if d == len(key):\n",
    "            node.value = None\n",
    "        else:\n",
    "            c = self._alphabet.toIndex(key[d])\n",
    "            node.children[c] = self._delete(node.children[c], key, d + 1)\n",
    "\n",
    "        if node.value != None:\n",
    "            return node\n",
    "        \n",
    "        nonNullChildren = [child for child in node.children \n",
    "                           if child != None]\n",
    "        if len(nonNullChildren) > 0:\n",
    "            return node\n",
    "        else:\n",
    "            return None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Visualisierung"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Der nachfolgende Code dient zur Visualisierung eines Tries. Die Details sind für das Verständnis nicht wichtig und können beim lernen übersprungen werden. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "ename": "ModuleNotFoundError",
     "evalue": "No module named 'graphviz'",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mModuleNotFoundError\u001b[0m                       Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-3-de3aa272efd6>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[1;32mfrom\u001b[0m \u001b[0mgraphviz\u001b[0m \u001b[1;32mimport\u001b[0m \u001b[0mGraph\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      2\u001b[0m \u001b[1;32mdef\u001b[0m \u001b[0mplotTrie\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mtrie\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      3\u001b[0m     \u001b[0mdot\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mGraph\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mcomment\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;34m'Tree'\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      4\u001b[0m     \u001b[0m_plotTrie\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mtrie\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_root\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;32mNone\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m' '\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mtrie\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_alphabet\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mdot\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      5\u001b[0m     \u001b[0mdisplay\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mdot\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mModuleNotFoundError\u001b[0m: No module named 'graphviz'"
     ]
    }
   ],
   "source": [
    "from graphviz import Graph\n",
    "def plotTrie(trie):\n",
    "    dot = Graph(comment='Tree')\n",
    "    _plotTrie(trie._root, None, ' ', trie._alphabet, dot)\n",
    "    display(dot)\n",
    "\n",
    "def _plotTrie(node, parent, char, alphabet, dot):                         \n",
    "    \n",
    "    if node == None:        \n",
    "        return \n",
    "\n",
    "    if node.value != None:\n",
    "        dot.node(str(node), str(char) +\":\" +str(node.value))\n",
    "    else:\n",
    "        dot.node(str(node), str(char))\n",
    "    \n",
    "    if parent != None:\n",
    "        dot.edge(str(parent), str(node))    \n",
    "    \n",
    "    labeledChildren = [(alphabet.toChar(p), child) for (p, child) \n",
    "                       in enumerate(node.children) if child != None]        \n",
    "    for (n, (charChild, child)) in enumerate(labeledChildren):                  \n",
    "        _plotTrie(child, node, charChild, alphabet, dot)      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = Trie(lowercase)\n",
    "for (value, key) in enumerate([\"she\", \"sells\", \"sea\", \"shells\", \"by\", \"the\", \"sea\"]):\n",
    "    t.put(key, value)\n",
    "plotTrie(t)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Experimente"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ausgestattet mit einer Funktion um Tries zu visualisieren, können wir nun mit Tries experimentieren. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Als erstes schauen wir uns die Sequenz von Tries an, die entstehtn wenn wir die Schlüssel she, sells, sea, shells und by einfügen. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"206pt\" height=\"476pt\"\n",
       " viewBox=\"0.00 0.00 206.00 476.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 472)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-472 202,-472 202,4 -4,4\"/>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e15f8 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e15f8</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"63\" cy=\"-450\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"63\" y=\"-446.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\"> </text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1b38 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1b38</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-378\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-374.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">b</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e15f8&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1b38 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e15f8&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1b38</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M54.2854,-432.5708C48.6253,-421.2506 41.2784,-406.5568 35.6343,-395.2687\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e19b0 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e19b0</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-378\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-374.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">s</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e15f8&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e19b0 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e15f8&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e19b0</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M71.7146,-432.5708C77.3747,-421.2506 84.7216,-406.5568 90.3657,-395.2687\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1dd8 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1dd8</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-306\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">y:5</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1b38&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1dd8 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1b38&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1dd8</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M27,-359.8314C27,-349 27,-335.2876 27,-324.4133\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1ac8 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1ac8</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-306\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">e</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e19b0&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1ac8 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e19b0&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1ac8</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M99,-359.8314C99,-349 99,-335.2876 99,-324.4133\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1be0 -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1be0</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"171\" cy=\"-306\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"171\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">h</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e19b0&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1be0 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e19b0&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1be0</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M114.2693,-362.7307C126.488,-350.512 143.5398,-333.4602 155.7527,-321.2473\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1c50 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1c50</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a:3</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1ac8&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1c50 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1ac8&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1c50</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M83.7307,-290.7307C71.512,-278.512 54.4602,-261.4602 42.2473,-249.2473\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1a20 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1a20</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">l</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1ac8&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1a20 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1ac8&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1a20</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M99,-287.8314C99,-277 99,-263.2876 99,-252.4133\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1b70 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1b70</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">l</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1a20&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1b70 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1a20&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1b70</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M99,-215.8314C99,-205 99,-191.2876 99,-180.4133\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1b00 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1b00</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">s:2</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1b70&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1b00 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1b70&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1b00</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M99,-143.8314C99,-133 99,-119.2876 99,-108.4133\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1fd0 -->\n",
       "<g id=\"node11\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1fd0</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"171\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"171\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">e:1</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1be0&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1fd0 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1be0&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1fd0</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M171,-287.8314C171,-277 171,-263.2876 171,-252.4133\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1d68 -->\n",
       "<g id=\"node12\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1d68</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"171\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"171\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">l</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1fd0&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1d68 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1fd0&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1d68</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M171,-215.8314C171,-205 171,-191.2876 171,-180.4133\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e19e8 -->\n",
       "<g id=\"node13\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e19e8</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"171\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"171\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">l</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1d68&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e19e8 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1d68&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e19e8</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M171,-143.8314C171,-133 171,-119.2876 171,-108.4133\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1a58 -->\n",
       "<g id=\"node14\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1a58</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"171\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"171\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">s:4</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e19e8&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1a58 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e19e8&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1a58</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M171,-71.8314C171,-61 171,-47.2876 171,-36.4133\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x7f0e5a2e1860>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "t = Trie(lowercase)\n",
    "for (key, value) in [(\"she\",1), (\"sells\", 2), (\"sea\", 3), (\"shells\", 4), (\"by\", 5)]:\n",
    "    t.put(key, value)\n",
    "plotTrie(t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Als nächstes löschen wir wieder einige Schlüssel."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"206pt\" height=\"476pt\"\n",
       " viewBox=\"0.00 0.00 206.00 476.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 472)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-472 202,-472 202,4 -4,4\"/>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e15f8 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e15f8</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"63\" cy=\"-450\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"63\" y=\"-446.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\"> </text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1b38 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1b38</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-378\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-374.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">b</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e15f8&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1b38 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e15f8&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1b38</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M54.2854,-432.5708C48.6253,-421.2506 41.2784,-406.5568 35.6343,-395.2687\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e19b0 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e19b0</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-378\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-374.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">s</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e15f8&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e19b0 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e15f8&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e19b0</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M71.7146,-432.5708C77.3747,-421.2506 84.7216,-406.5568 90.3657,-395.2687\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1dd8 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1dd8</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-306\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">y:5</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1b38&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1dd8 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1b38&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1dd8</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M27,-359.8314C27,-349 27,-335.2876 27,-324.4133\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1ac8 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1ac8</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-306\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">e</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e19b0&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1ac8 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e19b0&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1ac8</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M99,-359.8314C99,-349 99,-335.2876 99,-324.4133\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1be0 -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1be0</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"171\" cy=\"-306\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"171\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">h</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e19b0&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1be0 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e19b0&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1be0</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M114.2693,-362.7307C126.488,-350.512 143.5398,-333.4602 155.7527,-321.2473\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1c50 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1c50</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a:3</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1ac8&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1c50 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1ac8&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1c50</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M83.7307,-290.7307C71.512,-278.512 54.4602,-261.4602 42.2473,-249.2473\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1a20 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1a20</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">l</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1ac8&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1a20 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1ac8&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1a20</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M99,-287.8314C99,-277 99,-263.2876 99,-252.4133\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1b70 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1b70</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">l</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1a20&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1b70 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1a20&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1b70</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M99,-215.8314C99,-205 99,-191.2876 99,-180.4133\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1b00 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1b00</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">s:2</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1b70&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1b00 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1b70&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1b00</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M99,-143.8314C99,-133 99,-119.2876 99,-108.4133\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1fd0 -->\n",
       "<g id=\"node11\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1fd0</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"171\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"171\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">e</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1be0&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1fd0 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1be0&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1fd0</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M171,-287.8314C171,-277 171,-263.2876 171,-252.4133\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1d68 -->\n",
       "<g id=\"node12\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1d68</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"171\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"171\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">l</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1fd0&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1d68 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1fd0&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1d68</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M171,-215.8314C171,-205 171,-191.2876 171,-180.4133\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e19e8 -->\n",
       "<g id=\"node13\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e19e8</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"171\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"171\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">l</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1d68&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e19e8 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1d68&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e19e8</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M171,-143.8314C171,-133 171,-119.2876 171,-108.4133\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1a58 -->\n",
       "<g id=\"node14\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1a58</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"171\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"171\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">s:4</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e19e8&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1a58 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e19e8&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1a58</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M171,-71.8314C171,-61 171,-47.2876 171,-36.4133\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x7f0e5a2c9fd0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "t.delete(\"she\")\n",
    "plotTrie(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"170pt\" height=\"404pt\"\n",
       " viewBox=\"0.00 0.00 170.00 404.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 400)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-400 166,-400 166,4 -4,4\"/>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e15f8 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e15f8</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"63\" cy=\"-378\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"63\" y=\"-374.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\"> </text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1b38 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1b38</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-306\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">b</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e15f8&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1b38 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e15f8&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1b38</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M54.2854,-360.5708C48.6253,-349.2506 41.2784,-334.5568 35.6343,-323.2687\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e19b0 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e19b0</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-306\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">s</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e15f8&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e19b0 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e15f8&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e19b0</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M71.7146,-360.5708C77.3747,-349.2506 84.7216,-334.5568 90.3657,-323.2687\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1dd8 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1dd8</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">y:5</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1b38&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1dd8 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1b38&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1dd8</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M27,-287.8314C27,-277 27,-263.2876 27,-252.4133\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1ac8 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1ac8</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">e</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e19b0&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1ac8 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e19b0&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1ac8</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M99,-287.8314C99,-277 99,-263.2876 99,-252.4133\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1c50 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1c50</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"63\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"63\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">a:3</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1ac8&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1c50 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1ac8&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1c50</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M90.2854,-216.5708C84.6253,-205.2506 77.2784,-190.5568 71.6343,-179.2687\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1a20 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1a20</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"135\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"135\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">l</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1ac8&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1a20 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1ac8&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1a20</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M107.7146,-216.5708C113.3747,-205.2506 120.7216,-190.5568 126.3657,-179.2687\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1b70 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1b70</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"135\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"135\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">l</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1a20&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1b70 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1a20&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1b70</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M135,-143.8314C135,-133 135,-119.2876 135,-108.4133\"/>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1b00 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1b00</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"135\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"135\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">s:2</text>\n",
       "</g>\n",
       "<!-- __main__.Trie.Node object at 0x7f0e5a2e1b70&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1b00 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>__main__.Trie.Node object at 0x7f0e5a2e1b70&#45;&#45;__main__.Trie.Node object at 0x7f0e5a2e1b00</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M135,-71.8314C135,-61 135,-47.2876 135,-36.4133\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x7f0e6835fbe0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "t.delete(\"shells\")\n",
    "plotTrie(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Zeichenbasierte Operationen"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nun erweitern wir den Trie um zeichenbasierte Operationen."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Folgende Methoden wurden in der Vorlesung nicht besprochen und sind nicht Teil vom Vorlesungs/Prüfungsstoff. Wenn Sie Lust haben, können Sie sich trotzdem anschauen, wie diese zeichenbasierten Operationen funktionieren. Alle Methoden nutzen die Baumstruktur vom Trie aus. Es ist deshalb auch eine gute Übung um Tries zu verstehen.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TrieST(Trie):\n",
    "    \n",
    "    def __init__(self, alphabet):\n",
    "        super().__init__(alphabet)\n",
    "    \n",
    "    def keys(self):\n",
    "        return self.keysWithPrefix(\"\")\n",
    "    \n",
    "    def keysWithPrefix(self, prefix):\n",
    "        queue = []\n",
    "        self._collect(self._get(self._root, prefix, 0), prefix, queue)\n",
    "        return queue\n",
    "\n",
    "    def _collect(self, node, prefix, queue):\n",
    "        pass\n",
    "    \n",
    "    def longestPrefixOf(self, s):\n",
    "        l = self._search(self._root, s, 0, 0)\n",
    "        return s[0:l]\n",
    "    \n",
    "                \n",
    "    def _search(self, node, s, d, length):\n",
    "        print(s, d)\n",
    "        if node == None: \n",
    "            return length\n",
    "        if node.value != None:\n",
    "            length = d\n",
    "        if d == len(s):\n",
    "            return length\n",
    "        c = self._alphabet.toIndex(s[d])\n",
    "        return self._search(node.children[c], s, d+1, length)\n",
    "    \n",
    "    def keysThatMatch(self, pattern):\n",
    "        queue = []\n",
    "        self._collectWithWildcard(self._root, \"\", pattern, queue)\n",
    "        return queue\n",
    "    \n",
    "    def _collectWithWildcard(self, node, prefix, pattern, queue):\n",
    "        \n",
    "        if node == None:\n",
    "            return\n",
    "       \n",
    "        d = len(prefix)\n",
    "\n",
    "        if d == len(pattern) and node.value != None:\n",
    "            queue.append(prefix)\n",
    "        \n",
    "        if d == len(pattern):\n",
    "            return \n",
    "        \n",
    "        next = pattern[d]; \n",
    "        \n",
    "        labeledChildren  = [(self._alphabet.toChar(p), child) \n",
    "                            for (p, child) in enumerate(node.children) \n",
    "                            if child != None and (self._alphabet.toChar(p) == next or next == '.')]\n",
    "        \n",
    "        for (char, child) in labeledChildren:\n",
    "            self._collectWithWildcard(child, prefix + char, pattern, queue)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir bauen uns wieder einen Trie auf und testen unsere neu implementierten Methoden. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = TrieST(lowercase)\n",
    "t.put(\"she\", 77)\n",
    "t.put(\"sells\", 88)\n",
    "t.put(\"sea\", 88)\n",
    "t.put(\"shells\", 88)\n",
    "t.put(\"by\", 88)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Als erstes geben wir alle Schlüssel aus:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for k in t.keys():\n",
    "    print(k)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Als nächstes suchen wir nach Schlüssel, die einem gewissen Muster entsprechen, also zum Beispiel mit s beginnen und 3 Zeichen lang sind."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for k in t.keysThatMatch(\"s..\"):\n",
    "    print(k)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Wir können uns auch alle Schlüssel ausgeben lassen, die mit einem bestimmten Präfix anfangen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for k in t.keysWithPrefix(\"sh\"):\n",
    "    print(k)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Und zum Schluss experimentieren wir noch mit der Methode ```longestPrefixOf```."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(t.longestPrefixOf(\"shegoesforalongwalk\"))\n",
    "print(t.longestPrefixOf(\"shellsort\"))\n",
    "print(t.longestPrefixOf(\"seagull\"))"
   ]
  },
  {
   "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}