{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Binäre Suchbäume"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In diesem Notebook schauen wir uns die Symboltabellenimplementation mit binären Suchbäumen an. Binäre Suchbäume verlangen, dass auf der Menge der Schlüssel eine Ordnungsrelation definiert ist. Bevor wir binäre Suchbäume besprechen, diskutieren wir deshalb kurz, wie wir in Python eine Ordnungsrelation auf einem Datentypen definieren können."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ordnungsrelationen"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bei den von Python vordefinierten Datentypen, ist die Ordnungsrelation, falls diese Sinn macht, direkt von der Sprache unterstützt. Zum Beispiel können wir bei Strings die folgenden Vergleiche machen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"AA\" < \"AB\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"AB\" > \"AA\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Für benutzerdefinierte Typen weiss Python natürlich nicht, wie eine Ordungsrelation definiert sein müsste. Entsprechend gibt uns Python eine Fehlermeldung, wenn wir einen Vergleichsoperator nutzen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Date:\n",
    "    def __init__(self, day, month, year):\n",
    "        self.day = day\n",
    "        self.month = month\n",
    "        self.year = year"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d1 = Date(1, 1, 1970)\n",
    "d2 = Date(1, 1, 2018)\n",
    "d1 > d2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Um diese Operation zu unterstützen, müssen wir die Python Methode ```__lt__``` implementieren und die Klasse mittels der Annotation ```@total_ordering``` als geordnet kennzeichnen. \n",
    "\n",
    "*(Alternativ können wir auch alle funktionen ```__lt__```, ```__le__```, ```__gt__``` und ```__ge__``` implementieren)*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import total_ordering\n",
    "\n",
    "@total_ordering\n",
    "class Date:\n",
    "    def __init__(self, day, month, year):\n",
    "        self.day = day\n",
    "        self.month = month\n",
    "        self.year = year\n",
    "        \n",
    "    def __eq__(self, rhs):\n",
    "        return self.day == rhs.day \\\n",
    "            and self.month == rhs.month \\\n",
    "            and self.year == rhs.year\n",
    "    def __lt__(self, rhs):\n",
    "        return self.year < rhs.year \\\n",
    "            or (self.year == rhs.year and self.month < rhs.month) \\\n",
    "            or (self.year == rhs.year and self.month == rhs.month) \\\n",
    "            and self.day < rhs.day"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nun stehen uns die üblichen Vergleichsoperationen zur Verfügung."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d1 = Date(1, 1, 1970)\n",
    "d2 = Date(1, 1, 2018)\n",
    "d1 < d2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d1 >= d1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Repräsentation binärer Suchbäume"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nun können wir die Implementation der Symboltabelle mittels einem binären Suchbaums besprechen. Wir nehmen an, dass die Schlüssel wie oben besprochen, eine Ordnungsrelation unterstützen. \n",
    "\n",
    "Die Klasse ```BST``` zeigt die Implementation. Intern wird die Klasse ```Node``` für die Repräsentation der Knoten benutzt. Wir speichern uns auch in jedem Knoten die Grösse des entsprechenden Unterbaums. Der leere Baum wird durch das Symbol ```None``` definiert. \n",
    "Die grundlegenden Operationen einer Symboltabelle, ```size```, ```isEmpty```, ```put```, ```get```, ```contains```, ```keys``` können wir jeweils mit wenigen Zeilen Code definieren. Beachten Sie, dass wir für jede Methode in der Symboltabelle jeweils eine Hilfsmethode definieren, die eine Referenz auf den Wurzelknoten des Baumes bekommt, und die Operation dann rekursiv (der Datenstruktur folgend) implementiert. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BST:\n",
    "    \n",
    "    class Node:\n",
    "        def __init__(self, key, value, count = 1):\n",
    "            self.key = key\n",
    "            self.value = value\n",
    "            self.left = None\n",
    "            self.right = None\n",
    "            self.count = count\n",
    "    \n",
    "    def __init__(self):\n",
    "        self._root = None\n",
    "    \n",
    "    def root(self):\n",
    "        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 != 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",
    "    \n",
    "    def _put(self, key, value, node):\n",
    "        if (node == None):\n",
    "            return BST.Node(key, value, 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",
    "        node.count = 1 + self._size(node.left) + self._size(node.right)\n",
    "        return node\n",
    "        \n",
    "    def keys(self):\n",
    "        return self._keys(self._root, [])\n",
    "        \n",
    "    def _keys(self, node, keylist):        \n",
    "        if node == None:\n",
    "            return keylist\n",
    "        else:\n",
    "            self._keys(node.left, keylist)\n",
    "            keylist.append(node.key)\n",
    "            self._keys(node.right, keylist)\n",
    "            return keylist\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": [
    "Um die Implementation zu testen, schreiben wir uns einen kleinen Testclient:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "string = \"SEARCHEXAMPLE\"\n",
    "st = BST()\n",
    "for (pos, char) in enumerate(string):\n",
    "    st.put(char, pos)\n",
    "\n",
    "for k in st.keys():\n",
    "    print(\"key: \" +str(k) + \" Wert: \" +str(st.get(k)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Übung:\n",
    "* Schauen Sie sich die Methoden ```get``` und ```put``` genau an und stellen Sie sicher, dass Sie diese verstehen. \n",
    "    * Beachten Sie insbesondere wie beim ```put``` nach dem Einfügen jeweils wieder die Verweise richtig gesetzt werden und wie das Feld ```count``` aktualisiert wird. \n",
    "    * Falls Ihnen etwas unklar ist, instrumentieren Sie den Code mit ```print``` statements und testen Sie die Methoden an einfachen Beispielen. \n",
    "* Schauen Sie sich die Methode ```keys``` an. Welche Traversierungsstrategie (inorder, postorder, preorder) wird hier gewählt? Weshalb?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Experimente mit Binärsuchbäumen"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Um die Funktionsweise von Binären Bäumen besser verstehen zu können ist es hilfreich, diese zu visualisieren. \n",
    "Dazu definieren wir uns die Visualisierungsfunktion ```showTree```, welche den Baum zeichnet und in den Knoten den entsprechenden Schlüssel anzeigt. Sie müssen die Details davon nicht verstehen, sondern können die Methode ```showTree``` einfach als Blackbox verwenden."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "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, id, left, right):\n",
    "        self.key = key\n",
    "        self.value = value\n",
    "        self.id = id\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, newN + 1, leftNode, rightNode), rightN )\n",
    "\n",
    "def _buildTreeGraph(g, t, parentNode, depth):\n",
    "    if t == None:\n",
    "        return\n",
    "    _buildTreeGraph(g, t.left, t, depth + 1)\n",
    "    g.add_node(t.id, pos=(t.id, -depth), label=str(t.key))\n",
    "    if (parentNode != None):\n",
    "        g.add_edge(t.id, parentNode.id)\n",
    "    _buildTreeGraph(g, t.right, t, depth + 1)\n",
    "\n",
    "def showTree(bst):\n",
    "    g = nx.Graph()\n",
    "    (tt, _) = _augmentTreeWithId(bst.root(), 0)\n",
    "    _buildTreeGraph(g, tt, None, 0)\n",
    "    pos=nx.get_node_attributes(g,'pos')\n",
    "    labels = nx.get_node_attributes(g, 'label')\n",
    "    \n",
    "    nx.draw_networkx_nodes(g, pos, node_size=1000, node_color='#00b4d9')\n",
    "    nx.draw_networkx_edges(g, pos)\n",
    "    nx.draw_networkx_labels(g, pos, labels)\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nun können wir visualisieren, was passiert, wenn wir Schlüssel in einen Binärsuchbaum einfügen. Folgender Code gibt jeweils nach dem Einfügen den entstandenen Baum aus. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "string = \"SEARCHTREE\"\n",
    "bst = BST()\n",
    "for (pos, char) in enumerate(string):\n",
    "    bst.put(char, pos)\n",
    "    showTree(bst)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Übung\n",
    "\n",
    "Nun sind wir bereit, erste Experimente mit dem Baum durchzuführen. \n",
    "\n",
    "Probieren Sie folgendes aus:\n",
    "* Was passiert, wenn Sie einen Schlüssel (mit unterschiedlichen Werten) zweimal einfügen?\n",
    "* Was passiert, wenn Sie eine bereits sortiere Liste einfügen?\n",
    "* Können Sie einen perfekten Baum der Höhe 2 kreieren?\n",
    "* Erstellen Sie zufällige Sequenzen und geben Sie die Höhe des entsprechenden Baums aus. Was beobachten Sie?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Sortieren mit Binärsuchbäumen\n",
    "\n",
    "Schauen Sie sich die Methode ```keys``` etwas genauer an. Diese führt eine inorder Traversierung durch und speichert den Schlüssel jeweils in einer Liste. Wie wir leicht überprüfen können, sind die Schlüssel aufsteigend sortiert."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "bst.keys()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dies führt zu einem einfachen Sortieralogrithmus. Wir starten mit einem unsortierten Array, fügen die Elementen der Reihe nach in einen Binärbaum ein, und nutzen dann die Methode ```keys``` um die sortierten Schlüssel zu erhalten. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "array = ['c', 'x', 'a', 'q', 'b']\n",
    "bst = BST()\n",
    "for k in array:\n",
    "    bst.put(k, '')\n",
    "sortedArray = bst.keys();\n",
    "print(sortedArray)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Löschen von Knoten"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nun zeigen wir noch eine Implementation der Löschoperationen nach Hibbard.\n",
    "Der Code ist etwas trickreich. Zum Verständnis sollte man sich nochmals die drei Spezialfälle in Erinnerung rufen, die in den Folien besprochen wurden. Als weiterer Schlüssel zum Verständnis ist zu beachten, dass die Verweise auf den linken und rechten Teilbaum jeweils auf dem \"Rückweg\" neu gesetzt werden (analog der ```put``` Methode). Um ein Blatt zu löschen genügt es also, beim entsprechenden Node ```None``` zurückzugeben. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BSTWithDelete(BST): # Wir erben von BST, und ergänzen diesen um die Delete Operation\n",
    "    \n",
    "    def min(self):\n",
    "        minNode = self._min(self._root)\n",
    "        return minNode.key\n",
    "        \n",
    "    def _min(self, node):\n",
    "        if node.left == None:\n",
    "            return node\n",
    "        else:\n",
    "            return self._min(node.left)\n",
    "        \n",
    "    def deleteMin(self):\n",
    "        self._deleteMin(self._root)\n",
    "\n",
    "    def _deleteMin(self, node): \n",
    "        if node.left == None:\n",
    "            return node.right;\n",
    "        node.left = self._deleteMin(node.left);\n",
    "        node.count = self._size(node.left) + self._size(node.right) + 1;\n",
    "        return node;\n",
    "    \n",
    "\n",
    "    \n",
    "    def delete(self, key):\n",
    "        self._root = self._delete(self._root, key)\n",
    "    \n",
    "    def _delete(self, node, key):\n",
    "        if node == None:\n",
    "            return None;\n",
    "        \n",
    "        if  key < node.key: \n",
    "            node.left = self._delete(node.left, key)\n",
    "        elif key > node.key:\n",
    "            node.right = self._delete(node.right, key);\n",
    "        else: # key == node.key (zu löschender Knoten)\n",
    "            if node.right == None:\n",
    "                return node.left\n",
    "            if node.left == None:\n",
    "                return node.right            \n",
    "            t = node;\n",
    "            node = self._min(t.right)\n",
    "            node.right = self._deleteMin(t.right)\n",
    "            node.left = t.left\n",
    "            \n",
    "        node.count = self._size(node.left) + self._size(node.right) + 1;\n",
    "        return node"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Der folgende Code illustriert, wie sich der Baum ändert, wenn wir einen Knoten löschen, welcher zwei Kinder hat. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "bst = BSTWithDelete()\n",
    "for (num,key) in enumerate(\"SEARCH\"):\n",
    "    bst.put(key, num)\n",
    "showTree(bst)\n",
    "\n",
    "bst.delete(\"E\")\n",
    "showTree(bst)\n",
    "bst.delete(\"S\")\n",
    "showTree(bst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Übung\n",
    "* Probieren Sie verschiedenen Spezialfälle aus und versuchen Sie nachzuvollziehen, wie der Algorithmus funktioniert, indem Sie print Statements in den Code einfügen. "
   ]
  },
  {
   "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"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": false,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": false,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}