{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1><center>cs1001.py , Tel Aviv University, Spring 2020</center></h1>\n",
    "<img src=\"http://www.pngall.com/wp-content/uploads/2016/05/Python-Logo-PNG-Image-180x180.png\" width=50/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Recitation 10"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We discussed Binary search trees and Hash Tables \n",
    "\n",
    "#### Takeaways:\n",
    "- Important properties of Binary Search Trees:\n",
    "    - Insert and find take $O(h)$ time where $h$ is the height of the tree.\n",
    "    - When a tree containing $n$ nodes is balanced, $h = O(\\log{n})$.\n",
    "    - Many methods in this class are implemented using recursion.\n",
    "- Important properties of Hash Tables:\n",
    "    - Hash tables can be useful for many algorithms, including memoization. \n",
    "    - Insert and find operation run in $O(1)$ on average, but $O(n)$ in the worst case (where $n$ is the number of elements in the table)\n",
    "    - Make sure you understand the complexity analysis for hash tables (see the links below)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Code for printing several outputs in one cell (not part of the recitation):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.core.interactiveshell import InteractiveShell\n",
    "InteractiveShell.ast_node_interactivity = \"all\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  Binary Search Trees\n",
    "\n",
    "Recall the (recursive) definition of a binary tree:\n",
    "* A binary tree is an empty tree (a tree which contains no nodes), or\n",
    "* Is composed of a root node, a Binary Tree called the left subtree of the root and a Binary Tree called the right subtree of the root\n",
    "\n",
    "A binary search tree is a binary tree whose nodes have values, with the additional property that if $v$ is a node then all nodes in the left subtree of $v$ have keys smaller than $v.key$ and all those in the right subtree of $v$ have keys larger than $v.key$.\n",
    "\n",
    "Binary search trees support operations such as insertion, deletion, search and many more."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "## This file contains functions for the representation of binary trees.\n",
    "## used in class Binary_search_tree's __repr__\n",
    "## Written by a former student in the course - thanks to Amitai Cohen\n",
    "## No need to fully understand this code\n",
    "\n",
    "def printree(t, bykey = True):\n",
    "        \"\"\"Print a textual representation of t\n",
    "        bykey=True: show keys instead of values\"\"\"\n",
    "        #for row in trepr(t, bykey):\n",
    "        #        print(row)\n",
    "        return trepr(t, bykey)\n",
    "\n",
    "def trepr(t, bykey = False):\n",
    "        \"\"\"Return a list of textual representations of the levels in t\n",
    "        bykey=True: show keys instead of values\"\"\"\n",
    "        if t==None:\n",
    "                return [\"#\"]\n",
    "\n",
    "        thistr = str(t.key) if bykey else str(t.val)\n",
    "\n",
    "        return conc(trepr(t.left,bykey), thistr, trepr(t.right,bykey))\n",
    "\n",
    "def conc(left,root,right):\n",
    "        \"\"\"Return a concatenation of textual represantations of\n",
    "        a root node, its left node, and its right node\n",
    "        root is a string, and left and right are lists of strings\"\"\"\n",
    "        \n",
    "        lwid = len(left[-1])\n",
    "        rwid = len(right[-1])\n",
    "        rootwid = len(root)\n",
    "        \n",
    "        result = [(lwid+1)*\" \" + root + (rwid+1)*\" \"]\n",
    "        \n",
    "        ls = leftspace(left[0])\n",
    "        rs = rightspace(right[0])\n",
    "        result.append(ls*\" \" + (lwid-ls)*\"_\" + \"/\" + rootwid*\" \" + \"|\" + rs*\"_\" + (rwid-rs)*\" \")\n",
    "        \n",
    "        for i in range(max(len(left),len(right))):\n",
    "                row = \"\"\n",
    "                if i<len(left):\n",
    "                        row += left[i]\n",
    "                else:\n",
    "                        row += lwid*\" \"\n",
    "\n",
    "                row += (rootwid+2)*\" \"\n",
    "                \n",
    "                if i<len(right):\n",
    "                        row += right[i]\n",
    "                else:\n",
    "                        row += rwid*\" \"\n",
    "                        \n",
    "                result.append(row)\n",
    "                \n",
    "        return result\n",
    "\n",
    "def leftspace(row):\n",
    "        \"\"\"helper for conc\"\"\"\n",
    "        #row is the first row of a left node\n",
    "        #returns the index of where the second whitespace starts\n",
    "        i = len(row)-1\n",
    "        while row[i]==\" \":\n",
    "                i-=1\n",
    "        return i+1\n",
    "\n",
    "def rightspace(row):\n",
    "        \"\"\"helper for conc\"\"\"\n",
    "        #row is the first row of a right node\n",
    "        #returns the index of where the first whitespace ends\n",
    "        i = 0\n",
    "        while row[i]==\" \":\n",
    "                i+=1\n",
    "        return i\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "              4              \n",
       "       ______/ |______       \n",
       "      2               6      \n",
       "   __/ |__         __/ |__   \n",
       "  1       3       5       7  \n",
       " / |     / |     / |     / | \n",
       "#   #   #   #   #   #   #   #"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n"
     ]
    }
   ],
   "source": [
    "class Tree_node():\n",
    "    def __init__(self, key, val):\n",
    "        self.key = key\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "    def __repr__(self):\n",
    "        return \"(\" + str(self.key) + \":\" + str(self.val) + \")\"\n",
    "    \n",
    "    \n",
    "    \n",
    "class Binary_search_tree():\n",
    "\n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "\n",
    "\n",
    "    def __repr__(self): #no need to understand the implementation of this one\n",
    "        out = \"\"\n",
    "        for row in printree(self.root): #need printree.py file\n",
    "            out = out + row + \"\\n\"\n",
    "        return out\n",
    "\n",
    "\n",
    "    def lookup(self, key):\n",
    "        ''' return node with key, uses recursion '''\n",
    "\n",
    "        def lookup_rec(node, key):\n",
    "            if node == None:\n",
    "                return None\n",
    "            elif key == node.key:\n",
    "                return node\n",
    "            elif key < node.key:\n",
    "                return lookup_rec(node.left, key)\n",
    "            else:\n",
    "                return lookup_rec(node.right, key)\n",
    "\n",
    "        return lookup_rec(self.root, key)\n",
    "\n",
    "\n",
    "\n",
    "    def insert(self, key, val):\n",
    "        ''' insert node with key,val into tree, uses recursion '''\n",
    "\n",
    "        def insert_rec(node, key, val):\n",
    "            if key == node.key:\n",
    "                node.val = val     # update the val for this key\n",
    "            elif key < node.key:\n",
    "                if node.left == None:\n",
    "                    node.left = Tree_node(key, val)\n",
    "                else:\n",
    "                    insert_rec(node.left, key, val)\n",
    "            else: #key > node.key:\n",
    "                if node.right == None:\n",
    "                    node.right = Tree_node(key, val)\n",
    "                else:\n",
    "                    insert_rec(node.right, key, val)\n",
    "            return\n",
    "        \n",
    "        if self.root == None: #empty tree\n",
    "            self.root = Tree_node(key, val)\n",
    "        else:\n",
    "            insert_rec(self.root, key, val)\n",
    "\n",
    "\n",
    "    def minimum(self):\n",
    "        ''' return node with minimal key '''\n",
    "        if self.root == None:\n",
    "            return None\n",
    "        node = self.root\n",
    "        left = node.left\n",
    "        while left != None:\n",
    "            node = left\n",
    "            left = node.left\n",
    "        return node\n",
    "\n",
    "\n",
    "    def depth(self):\n",
    "        ''' return depth of tree, uses recursion'''\n",
    "        def depth_rec(node):\n",
    "            if node == None:\n",
    "                return -1\n",
    "            else:\n",
    "                return 1 + max(depth_rec(node.left), depth_rec(node.right))\n",
    "\n",
    "        return depth_rec(self.root)\n",
    "\n",
    "\n",
    "    def size(self):\n",
    "        ''' return number of nodes in tree, uses recursion '''\n",
    "        def size_rec(node):\n",
    "            if node == None:\n",
    "                return 0\n",
    "            else:\n",
    "                return 1 + size_rec(node.left) + size_rec(node.right)\n",
    "\n",
    "        return size_rec(self.root)\n",
    "    \n",
    "    def inorder(self):\n",
    "        '''prints the keys of the tree in a sorted order'''\n",
    "        def inorder_rec(node):\n",
    "            if node == None:\n",
    "                return\n",
    "            inorder_rec(node.left)\n",
    "            print(node.key)\n",
    "            inorder_rec(node.right)\n",
    "            \n",
    "        inorder_rec(self.root)\n",
    "\n",
    "\n",
    "t = Binary_search_tree()\n",
    "t.insert(4,'a')\n",
    "t.insert(2,'a')\n",
    "t.insert(6,'a')\n",
    "t.insert(1,'a')\n",
    "t.insert(3,'a')\n",
    "t.insert(5,'a')\n",
    "t.insert(7,'a')\n",
    "t\n",
    "t.inorder()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<b>Claim:</b> An inorder traversal of a binary search tree prints the keys in ascending order.\n",
    "\n",
    "<b>Proof, by complete induction on the size of tree:</b>\n",
    "* Base - for $n = 1$ the claim is trivial\n",
    "* Assume the claim holds for all $i \\leq n$\n",
    "* For a tree of size $n+1$ with root $v$ consider the following:\n",
    "    * Both the right and the left subtree of $v$ have size at most $n$\n",
    "    * By induction, all keys in $v.left$ are printed in ascending order (and they are all smaller than $v.key$)\n",
    "    * Next, $v.key$ is printed\n",
    "    * Finally, by induction, all keys in $v.right$ are printed in ascending order (and they are all larger than $v.key$)\n",
    "    * Thus, the keys of the tree (which has size $n+1$) are printed in ascending order\n",
    "\n",
    "\n",
    "More information on complete induction: https://en.wikipedia.org/wiki/Mathematical_induction#Complete_(strong)_induction"
   ]
  },
  {
   "attachments": {
    "image.png": {
     "image/png": "iVBORw0KGgoAAAANSUhEUgAAA+gAAAGQCAYAAAA9TUphAAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAADsMAAA7DAcdvqGQAAEvmSURBVHhe7d19kBXVve//NUPd3+8qFWZIVcScciZwquKUygxQFeGnw4ClBjWKJrHIiQkQbkJyTECsxGgUgUTFZ28sOZJExRMLMKkjldQR1ANErZIHBf1VyYN6GFP3ShyrZPKPA97S+7t/MD8+i7XGnp7ee/Zsuves7v1+TXXt3mv2Q3evftjfXk8Nn376ab8BAAAAAACjqtE9AgAAAACAUUSADgAAAABAAAjQAQAAAAAIAAE6AAAAAAABIEAHAAAAACAABOgAAAAAAASAAB0AAAAAgAAQoAMAAAAAEAACdAAAAAAAAkCADgAAAABAAAjQAQAAAAAIAAE6AAAAAAABIECvQn9/v52ANPj9iX0qe8NtY/IAAAAAo6lkgF7EH6o+CCo1Ver00083v/rVr9wzoHpPPfWUGTt27KjsUyPZ54vg3XffNV/84hfNiy++6FIG8/9//fXXXQoAAABQW4kB+htvvGHOPPNM96wYooGQJs1Hp+nTp5s//elP7tXlNTQ02Ak4VYsWLTKffPKJueCCC1xK7Vx77bXm4Ycfds+K77777jPnnXeeufTSS13KYGeffba58MILza233upSAAAAgNpKDNCPHj1qjh075p4VQzQQuuWWW+y8nw4fPmy+853vmAULFlQUpOs9lKAj7/r6+uxUD1Rq/sc//tEsWbLEpSS77bbbzGuvvVbxzToAAAAgTYMC9Hh17+jz6JQKfcxIp4ycccYZ5qc//am5++67S5aejXQ7xF8XfR5NL2ek7yn12qQ0L/q/av5/KpI+OzqfJPr64V4bNdL3lXptqfS4+OviUzkjeW014p8b/a74/6JKvaZUelz8deVeG1Xt+6L+8Ic/mLPOOst885vfdCnJzj//fFuKfu+997oUAAAAoHYGBeiLFy+21b2vueYa+zxeDVyTXpOGF7/6f5stk/9rxdOri/4v987stLe3mw8++MA9G6ytrW1gG6iK/CWXXOL+k8xvS722t7fX3HTTTbZ9q9L0WSqBLxdoqATvBz/4waDvVZXkcu1j/et8e2Z9vkoOVaVX6fr+3//+9+7VJ+nzfbV/zcdF/1+qavBIabm0HGpW4JdZn63q1lrnUrUTtC7R92jSc31W2tvSbzOtt89rtVHW5/jP+NnPfmbT43x+R79P81ovTfruUrSs0XXUd6fZJlrr4D9bJcUPPPDAwPPopNfF3XHHHQP/13YRravWye/bWl6lxVWTd0r/9a9/PWg7atL20+eVy/MorYtKz+fOnetSyps/f755++23aYsOAACAmhsUoD/55JO2+vbmzZvt82g1cD/pNalQE+6RThnSj/2dO3ealpYWlzKYfuT7baAq8sPRdvLb8aqrrrKPO3bssO//zW9+Yx577LGSgagCVVW1bW1tNU8//bR9j6rhd3R0mKuvvjoxeBK/fL49s4JElQSqWq/St2zZYj83+n7Nq8RQ65T0uUrT//Sal156yaWeGgW22gZaFr/Mv/3tb23TCgVSSRS4KnDSuuzbt2/gffoMrVepwLDabal11Wt9XiuQ/O53v2tmzZpl369p165dtm+DKAV1U6ZMMePGjTPPPffcwHLquz/++GMbEJeqVq5SXrWTji6ngkotZ1rBotpZ+2VKau7hJ70uTvur/uf3ay2T9m31x+D37UmTJpnly5fb/3vV5p32E+0P2ibaFnqPHrU99N5SN0jidu/ebR+/9rWv2cfhdHZ22sdS+yIAAACQlYZPP/10SDGUSqcUGJz4n0spjosvvth0dXUNCo4VpCk4UtC8cePGYUuKf/nLX9pg/uWXX3Ypyfx2VPCpNvBRf/7zn82Pf/zjxMCkHL/8Ks0sRa955513bLt6lUAOR8upAGr//v1mwoQJLvUkLZ8Czkq2S6VOO+00G5glfZ5KqHWTJJo/fhn0HlVBTqKqy6oBUW67xFWyLZXX2i/UuZgCNjWHKOfLX/6yuf3224fkt6egUkGm8j9Ky6IA/vnnnx/yHaXec6oqWf8kfr+ePHmyvdFSKk+k2rzTd+j4UHCdtM3//ve/m5kzZ9rvH26//P73v2/zbiTnM3WSee655w57jAMAAABpSuwkriZ0W2CkU0ri1XqnTZtmHnzwQVvCpkAhbUnBmkpYy3XEpxL9pKlSlQbnogBHAaiCnTillev5uhoKvPS5ujESXz/VPIjXLHjhhRdssPSVr3xlyOv9pL4Dfve737l3DJb0ek2V0g0DlagPF5yrpFhKBeeiPCkVaGv/S/qOz33uc0F25qabCeWCc6k273TDTPvwF77whcT3KP36669P3GfjdHNjpLTMquYOAAAA1NKoBeij2QY9qVrvK6+8YqvqqrRvtNueqtRRQWpSm12VjFdCQd1IqMqwSoqjJfqaV5r+lyYFqSq5VZXx6Lqp9DypyrkCLLWXjm6L+HTRRRfZEui4Wm7LAwcOlGwiUUTD3bCQavNO7yvVPt5PK1assM0islK0kSwAAAAQvtErQU9qYz7clCGVBKr09p//+Z9HdRxkBZRq16v2zQqMFaj4mwgqLcwqAEwqRVdbaH1fmqXnnnrN13j7ft00r/XWlHSDRO2l/WvLTVGjtS0xWDV5J6Xax0entPpFSNLU1OTmAAAAgNoYtQD90r/8f2buW/+74unCp/6Pe2e2VLKrEr/Roqq9KrFV4KG2udFSSt1EGGnJ+EjES9HVdn64caOroSrKSbS+6hBMnYBFqVaDSrv9clWq1tty4sSJpqenxz0rrdT6F1G1eTd16lTbz0MalC8jpertquYOAAAA1FLZAD0pkPBtQItqtKspq62xgpo4bXOVLFcSAFbLl6Kr5Fy9lqvKf7n21NVQr+oKjkvtQ0npCq61XLqBUO598f/VelteeeWVtqq2qvAnLaf/Xg1JVqr3+FpS/iZJ2pbVqjbvVItFgf1ww7CV+l+U71dCHc9VQnmj6u26WQcAAADUUmKArkBNQaraBHd3d9sfwXrUj2X9T+138yj6Y97/uPeTSvgUWKndq0pxo+Kv9UqlSzQt/v/4/6IUFKgU2wcmmhTUacg0lSz7trrx9/nXRtOjadH0clRirpLze+65Z8hwWWlQ0KzSSe1H6lQtunwKoPT98e0v6oX74MGDdkiu+Pu0fdTOXIFvVLXbUvzrPf88OsWphF69lWsf0vJon/Kv1brpeNL3av2iw5hFPyv+ueX+d6oWLFhgt090e2o5/Zj98c7s/Gv8ckSfR9Pjqsk7vy0V2Gu76XXR92k5NR56uTHlPd04EXVqVwk/LJuaRwAAAAC1lDjMmqgUSaVYW7dutc/V67jGwlaAUaq36ZBpvOqf/OQn7lkyX9KnUr8oBRbDVXs/66yzBpWKKgD74IMP3LOT7WkViIgeFcR5ag8dLalWYKTxy30v0vpsBQvqtVo9oPtl0ZjSPtCLf2YSjV9dSXtyDRWm0tUsSnlVgq6qyxrWTQGT5v12uvzyy216fPt7GlpL20rv89tG+6XyTdtHnc7F98tqtqWCv3g1+7hofsZpu91///2D1k3LqBsG+t5ocJ60X6pttXf66ae7uZPi+8qpUn7ohkx8Oa+77rohPbTHlyVObc1LtQmvJu8kaVsqDzXEm/Ko0m2hodb0GX/9619dSmkafk77f5bt2wEAAIAkJQN01K/hxvIG8kY3XTR2u8bzL1fqrhsCahahZh6lbhQBAAAAWSFAxyAKZFSKfeTIEZcCFIOqyr/33nvm5ZdfdilDfeMb37Dtzyk9BwAAwGgYvWHWEIRou15NanuuoeY0DxTJL37xC9vxnIb0S6LSczV5SOoDAQAAAKgFStDrXLm265W2WQcAAAAAnDoCdIxItSXrpYb0wsiRBwAAAEAxUcUdI7J48WIzduzYEU9q2450kAcAAABAMVGCDgAAAABAAChBBwAAAAAgAAToAAAAAAAEgAAdAAAAAIAAEKADAAAAABAAAnQAAAAAAAJAgA4AAAAAQACCCtD7+/vthNrw27vW2zz6vaPx/XlyKttopO858S32r5xqlwUAAADA8EoG6KPxI/xXv/qVOf30090zZJ0Hl156qRk7dmzNt/nixYvt9/qJPC/tjjvuGNhGL774oksd3p/+9KcRbdcN72wwpz9yup00X4ry7gc/+IF7BgAAACBNiQH6G2+8Yc4880z3rHYaGhrshNrkwUsvvWQ2b97sntXOk08+aT755BM7jcb354luWmk7jYRu7Nx6663mF7/4hUspT6XmD7zxgFl1wSqXUtr1119v/vjHP47oZgEAAACAyiQG6EePHjXHjh1zz2qnmmCkqEYrD5B/Oo4++OAD85Of/MSllLf0paVm7H8Za26bfptLKe388883V1xxhb0BAAAAACBdgwJ0377UV62OPo9OaRvp58dfG33u04aT9J7ofJLo64d7rZR6bal0iadHn0enrFTzPfH3VPq+aozku+KviT6Ppg+n1Pv8Y1z8tX6qRDXvifvDH/5grrvuOnPGGWe4lNJe+/A1s+ndTWbF/7PCpQxPgf/bb79tq9EDAAAASM+gAN23Db7mmmvs82g7YT/pNWl66qmnBn3+cG1t33333YHXqaRQr50+ffrA+6+99lrz+uuvu1cPpaDn97///aD3qC32ww8/bNvW6jOTxL9Hk57rs0oFUtE23pdccolN0/Lre/xn/OxnP7Pp3mjkgaeAK7qOmv/1r39dcv26u7vt//16ampra7PbsNrgshzl60033TRkGUsFin5bavv39vba937xi1+seDn1P61f9Pv0fuWfvjOpCYK+R3nqvyf6HuV9Kfqu+H6p+XL7VxK9XqXnV111lUspb+WulWbe2fPMVf9Y2etF+X3WWWeZjRs3uhQAAAAAaRgUoPu2wb5dsG8nHJ30mjQtWrRo0OcP5+yzz7avu+CCC8wLL7xgS/Nuu+02m3b48GEzfvx4c/XVV9tAKYmCp9/85jcD79H029/+1lYpV9vaJArG5s+fb5YsWWL27ds38D59xpYtW2zwnfR9auOt191yyy32uYKn7373u2bWrFl2WTXt2rXL3qTwRiMPRMum9dE6+u/Rc20TrV9SkDh79my7/HqP1kXv0bZVvsRvPJwqtclXviqf7r333oFl1HdrSgrStZ38dvQB644dOwaW87HHHit5Q0b5qQBZ66fX+u/T+9vb2+13xpsgaBvpe/72t7/Z4DX+Hv1P2zmJAnjtS9Hv0vbX5+h/ldq5c6d9/OY3v2kfy1n/znrzP/r+h7npKze5lMp1dXWZrVu3mr///e8uBQAAAMCpavj000+HRF4qLZ47d6458T+XUjunnXaaDVRUSlfOxRdfbD7++GPz/PPPD6nKq3ay3/nOd8xPf/pTl/KZcp+vQKilpWVQ0KZAbcqUKfY9+twkCoYUgKnH7SS//OUvbTB43nnn2YC3kqrHtcoD/z1abwWj8WVTAHbllVear33tayXXL24ky57Gemr7KjB9+eWXXcpn/OfrJoxuBkX9+c9/Nj/+8Y8Tb658//vftx0WlroZovfq5tCRI0dcysnlOHjwoP1fEt1k0LLs37/fTJgwwaUaW0qvbV/qfdq//uM//qOi4+LLX/6yzcukbRH1P4/+T3PxMxebm8+/2SyZusSlnjg+HjnNPP7Vx82Ccxe4lGSqcbJ8+fKKlgkAAABAZRI7icsLBY1Jwe7nPvc509fX554NpoBMpZSqbqwSz+ikYCxeoqrS4HPPPdd85StfGfJ6P6nDrN/97nfuHckUNKlEvZLgfDTcd999icumNJXkllq/pO2RpWq/Lx6cy7hx4xI74tNNCd1IKdcLuoLmaHAuavut/StpGTVpH1LND70uSjcPtI1LUd5UStXbK/Hf/9//bs4ce+ag4HwkdENKdEMCAAAAQDpyHaBXQ6WVqp6rqubRtr6l2gir6vZrr7028Nqk6aKLLrKl+eXopkHIylWJ1v8UyKoEOEql02rzH29vXS7YrJYCXFUPV2ltdNurLXk84D1VBw4csI9qTjESCo7Vd0B0+eLTtm3bbDV9T9tU7ytVO0NGuhzD2fPhHtsx3MMXPWyHWIv+SXR+OKVuhAEAAAAYuboL0EVV3xUY+ba+mlf7YE1JHcyp1NO/ttxUTxQsq11+R0eHrebst4GCWzUvSJtuoKjt+YIFCwb1A/Dcc8/ZGy6hUJt3v2ylplLt3mvlrx/91fyv//O/zCWbLjFjHxk7aJLr/3K9HXqtEs3NzW4OAAAAwKnKJECPVusNTallUimxqhKrI7IotT9/5513SnY6VxSlekIX3bRoamoaVMqrav3qwEzBZjRdVeJ99ee06AaKmhqonbaqqkdLlDWv5gNpam1ttY/lel2X+L40efLkgU7aKqVtp+UvN/LAcMsRpd7Vh6P25Z/c+EniJI999TGz9pK1dr4UX8sg7bwGAAAA6lnZAD0pmB0u8Fb7XQUdGtpKjyH18qyOrbRMpZY/KV2Buzp3U7Xtcu8rt01ORdLnZvF9Wr+kmxD6Ht24uP76613KSarynhSc6fXquC9NqhKuwPMLX/iCS/mMlnmkQfFwFPRfeOGF9iZEqe2v71XTiGgP/CrhV2eACrZL5U9SutqtaxuX+i4tR6WUJ2qSkbW33nrLPtJBHAAAAJCexABdP7pVqqdqxRrrWkGCHn0bYAUmpahk7e2337bzevQlbaXos6NTqbSoaFr8/+X+p/ayWiatg0qM9X8/qT21hs5K6pBLHYapMywNNxZ/n4IxlSKr7XWcf40XfV/8f3GnkgeVii6DeuRWVXF9vk/Xuuq7NHRdvFq2AtjrrrtuYNkUsOq9Wi4foEc/3/Np0SkpPUrV6NVOW0O36Xv0f32v+hNQDYeenh77uvj7op8VnZf4/+KU5/pctbGPdijo81vfq+0V7XxO28rXwtBr/LbRpOXW9tT20Y2iKDW50Db2Y/j790S3v/j0cnwNEL13JE588kC78+h8KbopcsUVV7hnAAAAANKQOMyaKChRyZ3GOhb1eK2gTAFAqd7TxQ/LpUBYJc9Jw6B5CorjVcqTqNd1HwipxFLDW0WpXa+nkntPpa7R6sEKjBRYqO20lkvzvtfryy+/3KaX6ixN66Xl0Pv8DQhtE62j2q6r07noelaybhofPR74RlWbB5XSDQdf2qptqGG+VArs10/rppsWST2ga3uo1F3bw/eErm2oZdN29+uuID46VJnW94EHHnDPSlM782hVdlVz17JFt4X2M32+qr77z4zuK3p/tFfz6PaOL0f0fV5SnmvdFJjrexU8J1He632vvvrqwLbRttSNhnLv0769du3axO3v9+v4Pp1EQ61pGf/1X//VpZR37+v3mrteu8s9O+m/Tf5vJau5a/00XBxDrAEAAADpKhmgA8gn3Xy4//777QgE0fHW06Ix4lWjRDdNAAAAAKSHAB0oINUeUGn9HXfc4VLSoSr4s2fPpvQcAAAAyAABOlBAaq6gpiBHjhxxKelQnwgSbbYAAAAAIB0E6AAAAAAABIAAvQCG69m7lIaGBjcHAAAAABhtZcdBR/jU8/fYsWNHPKXdNhkAAAAAcGooQQcAAAAAIACUoAMAAAAAEAACdAAAAAAAAkCADgAAAABAAAjQAQAAAAAIAAE6AAAAAAABIEAHAAAAACAAQQXo/f39dkL62K61w7YGAAAAUI2gAvRf/epX5vTTT3fPslNvAdS7775rvvjFL5oXX3zRpSQjsBxqpNvEb+vXX3/dpQAAAABAZYIK0BsaGuyUtWuvvdY8/PDD7lnx3Xfffea8884zl156qUsZSttD2wWfeeONN8yZZ57pnlXm7LPPNhdeeKG59dZbXQoAAAAAVCa4EvRPPvnEPctOX1+fneqBSs3/+Mc/miVLlriUZPW0TSp19OhRc+zYMfescrfddpt57bXXzJ/+9CeXAgAAAADDGwjQVZXXT140Lf6/uFKvS0qLi76m3Ou8+Gujz31akvj/o++J/y+q1GtKpcfFX1futVHVvi/qD3/4gznrrLPMN7/5TZcyWPxzo98V/19aSn12qfSo6Gui03BG8p74a6LPo1Mp559/vi1Fv/fee10KAAAAAAxvIEC/4447zNixY20bcJW6alKVZ6VpamtrMzfddJPp7e117xjMv07vV0m4Ahh9hqpVK13tcn//+9+7V3/mqaeeGnivf3+5ttJq4xv9Hr12+vTpA+/XMie1//Xv06TSzQceeGDgeXTS6+L8ttHk28hrO+j7tV5Kv+SSS4ZsG22DX//613bb+fdr0jJquUsFedW+L07rotLzuXPnupSh/Hdoe2i7RL/PT8qjtGj5/ef6vNb6aN/wy6LHpDzU67TNo/mt1yqt1H4p+t8PfvCDQdtTn6HvTNqWixcvtq+55ppr7HP/nuik15Qzf/588/bbb9MWHQAAAEDFBgJ0BTm+evnzzz9vA4yrr77aHD582Kbv2rXLtLS0mK6ursQgVq/RdMEFF9jnCuZVgqiq1UrfsmWLrfobf++iRYsG3qtpOGrj67/nhRdeMD/5yU/s5ypNyzp+/Hi73PGAzb/Pv/eWW24ZeB6d9Lo4v202b95snyvouuqqq2x7+R07dtj/TZo0ySxfvtz+3/vZz35mA2S1AffbUY9aPi2z/p+k2vfF7d692z5+7Wtfs49JlB/6fG0PbRfNxyflUVp0w8Z/rqgaudK0fz399NM2XdtR+1+U8lNBtba59k//GVr+5uZm853vfCcxSFdeaZ+dNWvWwLpq0mccPHjQBu7xIP3JJ5+0r/H57d8TnfSacjo7O+2j8hEAAAAAKtHw6aefDopOTjvtNNPU1GQDalXVjVNp6vr1683LL7/sUga7+OKLzTvvvGMDJpUCj5S+X99drkMz0fd8/PHHNtA644wzXOpJWm59/09/+lOXMpjeq6BNJeMjodJelUZPnjzZ/OY3v0ncPp5e++Mf/9gGyfHlk7///e9m5syZ9nOi61rt+5J8//vftwHiiTx2KaX98pe/NDt37iyZr1lQXuumjwLy4W4CfOMb3zBTpkyxN0uS/PnPf7Y3hNSxm6eAXdvqt7/9bcltpZsdCtCTOg30+V3J9kuiDubOPffcmm5TAAAAAPmV2EmcgttSwacCKQXg5aruVhucj5RKhpOC2M997nOZdnimmwLlgnNR229thy984Qs2AIxPSr/++uttoB1V7fuSqNQ9dKolMFxwrpLvrVu32toSpaiNvfI82jGbaliodL3cjQxty9/97nf2xkfaFJyrmjsAAAAAVCIxQC9XJVoUePjq00kUIBdZ0k2BOAXHpdq5+2nFihW2indUte/Lq3Hjxrm50t5//31b/X647a7S+AMHDrhnJ7flcPuyb9IQfV+aqukFHgAAAEB9SgzQkY5S7dyj00svveRe/Zlq34fwqLkIAAAAAFQiMUBXFe5yVMVdbXtR2tSpU22b7pGq9n1JJk6c6OayF62Gn7bW1lbbw3xSJ3BRPT09tp26p/VXNfdyfKeFHR0d9jFNqt6u2iYAAAAAUInEAF0di5VqY66hqc4777xh22CHTD2BJ0kzwLz11lvtjYxSQ3lJ0vdV+74k7e3t9lGdnQ2n1DaR4b5P+4o6RNOwaeoVPW2qhn7FFVfYdvdJy6E09Xmg9ubR8d6vvPJK2xSg1Prrfdre6pSvXPX5Ut+ZlO4p8Ff1dnVGCAAAAACVSAzQf/GLX9hhrhQkqtRSgYge1dO1giT1ih3lg5VowBJNi6bHJb0uKS0qmhb/f7n/eQsWLDCPPfaY7VBMr9GkIE5Dw2lcc/UIHuVf4z8v+jyaHqWAzw8tp6BVQWz09fo+jWuuKara9yVRgCrD1YgQdUy3Z88eG+j6PNd367nGD9e2KUWf79taDzesWHRd4s+j6XHqyE2l4VoOBb/+tVpW9eyu742vp7alhm5T53LR9dKkz9A21LB8pTo0VOdyateufOju7rbv06OOC/1Pw76V4vto0HB8AAAAAFCJxGHWFCCq7ayGrVLv2XLWWWfZYEMljvHSRgVI6tisHI0pHe9NW8GmxvYejm4K+J6+NcxbvDdvtcn2VIrraZl9FeY43WzQjYYPPvjAPletAJV2XnfddUNqB0Q/M4k6MCvVJlzff//999tq6/67tFwaqk3rXqoH82rfF6eh1vQZf/3rX11KacoP3RjwPY/r+7RNFOhHS6bjNLSZhiNTkK7tV26M8EsuucRWVy8nmp9x2tcUiEeXUTcXtE+UKgVXD+1ar+i2VH5rjP5KepDXPu+PA3Vqd+GFF9o8KDWKgGgoP9VKoK8AAAAAAJUqGaCXG5oK+aGgW8Hzxo0bKyp1x6lTUK+28Cq9L3djAwAAAACiCNDrgKpov/fee+bll192KcjSN77xDVubgNJzAAAAACMx0Abdt82NzvvnyDf1KaCO51QVHdlS6bmq8N93330uBQAAAAAqM1CCXqod+b59+2wv2gAAAAAAIDtDqrgDAAAAAIDaSxxmDQAAAAAA1BYBOgAAAAAAASBABwAAAAAgAAToAAAAAAAEgAAdAAAAAIAAEKADAAAAABAAAnQAAAAAAAJAgA4AAAAAQAAI0AEAAAAACAABOgAAAAAAASBABwAAAAAgAAToAAAAAAAEgAAdAAAAAIAAEKADAAAAABAAAnQAAAAAAAJAgA4AAAAAQAAI0AEAAAAACAABOgAAAAAAASBABwAAAAAgAAToAAAAAAAEgAAdAAAAAIAAEKADAAAAABAAAnQAAAAAAAJAgA4AAAAAQAAI0AEAAAAACAABOgAAAAAAASBABwAAAAAgAAToAAAAAAAEgAAdAAAAAIAAEKADAAAAABAAAnQAAAAAAAJAgA4AAAAAQAAI0AEAAAAACAABOgAAAAAAASBABwAAAAAgAAToAAAAAAAEgAAdAAAAAIAAEKADAAAAABAAAnQAAAAAAALQ8Oabb/a7eQAAAAAAMEooQQcAAAAAIAAN/Se4eQAAAAAAMEooQQcAAAAAIAAE6AAAAAAABIAAHQAAAACAABCgAwAAAAAQAAJ0AAAAAAACQIAOAAAAAEAACNABAAAAAAgAAToAAAAAAAEgQAcAAAAAIAAE6AAAAAAABIAAHQAAAACAABCgAwAAAAAQAAJ0AAAAAAACQIAOAAAAAEAACNABAAAAAAgAAToAAAAAAAFo6D/BzQ+SlNzQ0ODmksXfM9zrAQAYLdVc5wAAQDFEfweEdP0vWYK+YsUK09jYaMaMGWOnlStXuv+U1tXVZd+jSe8HACBER44cMQsXLjSf//zn7TVu4sSJ9rpV4p41AAAokO3btw/ErZpCUnZpOjs7zfHjx+20evVql1ra7Nmz3ZwxkyZNcnMAAIRDwfmcOXPsNevQoUP2GqcLte6ez507170KAAAUlX4HeC0tLW4uDKneLmhubnZzxrS2tro5AADCcfPNN9vgfPHixWbChAk2ra2tzd6Ifv/99826detsGgAAKK6mpib7GFrcmmqAPmXKFDc3eB4AgFC89957JUvKla7/AwCAYps8ebJ9nDZtmn0MRaoBur8LIb5UAgCA0Ozfv9/NDVYqHQAAFIuv/T1u3Dj7GIpUA/QZM2bYx/b2dvsIAEBoVq1aZe655x6zbds22ymcn1S1fffu3WbZsmXulQAAoKh8je+pU6fax1CkGqBLR0dHcCsJAICnjmH+7d/+zXz72982s2bNsj2433jjjeauu+4ye/bsoQYYAAB1QDGrOohV/BqSkuOg33777eaVV14xu3btcikAAOSfenFXB3FPPvnkoGB806ZNZvPmzWbDhg0uBQAAoLZSL0EHACBkvhf3eEn5vHnzzEcffUQv7gAAYNQQoAMA6opqh5UaaUTp+j8AAEBctO+arBCgAwDqyrFjx9xcMpWiAwAAxHV1dZnGxkY7bd++3aWmiwAdAFBXNNb5+++/7559RnfDlf71r3/dpQAAAJzU29trR3uRzs5O2+lsFgjQAQB1ZcWKFbbHdrU1V4dxCswPHTpk0w8cOGA7kAMAAIjasWOHmzs5ZGtWCNABAHWlra3NVkvThfacc84xY8aMMZdddpkdaiWr6moAACDffICeZem5MMwaAAAAAABltLa2mp6eHrNt27ZMA/RhS9AVv/sJAAAAAIB60t3dbYPzrEvPpWSArqp+r776qq36p2nlypXuPwAAAAAA1Ie+vj4bH2fZ9twrWcUdAAAAAADUDp3EAQAAAAAQAAJ0AAAAAAACQIAOAAAAAEAACNABAAAAAAgAAToAAAAAAAEgQAcAAAAAIAAE6ACAQmIUUQAAkDcE6ACAwunt7TXjx48327dvdykAAADhSzVAV2lFdAIAYDSsWbPGjBs3zsyZM8elpI/rHAAA+RVq3JpqgN7V1WUaGxvttGLFCpcKAEDtqPR87dq1ZtWqVS4lG7rW6bsAAEC+qIadj1s1hSTVpZk9e7abM2bSpEluDgCA2tmyZYt9nDt3rn3M0v79+90cAADIi2gNu5aWFjcXhlQD9ObmZjdnTGtrq5sDAKB27rzzTrNkyRIzYcIElwIAADBYU1OTfQwtbk01QJ8yZYqbGzwPAEAtrFu3zhw7dswsW7bMpQAAAAw1efJk+zht2jT7GIpUA3R/F0IouQAA1Jo6h1PVdq5BAACgHF/7W53KhiTVAH3GjBn2sb293T4CAFAr6vDl4MGDdFIKAACG5Wt8T5061T6GItUAXTo6OoJbSQBA8ant+fz5801bW5tLAQAASKaYtaGhwcavIWnoZyBXAEDOqfT8sssuM4cOHapZgK6L+rZt2zIdax0AANSX1EvQAQCotQ0bNpjOzk5KzwEAQK4RoAMAcq27u9ts3LjRrFq1yqUAAACkT5XP/ZQVAnQAQK6tXr3alp5T1RwAAGSpq6vLNDY22knN67JAgA4AyK3e3l5ber5o0SKXAgAAkD795ti9e7edz7JggAAdAJBbGve8paXFLF682KUAAACkb8eOHW7OZNqsjgAdAJBLupO9du1a2p4DAIDM+QA962Z1BOgAgFxav369faT0HAAAZO3ZZ5+1j1kXDBCgAwByafPmzWbp0qXuGQAAQDY0YkxPT09NOqUlQAcA5NLOnTttD+6jpaGhwTQ1NblnAACgqPr6+ux1vxbN6hr6sxzEDQAAAAAAVIQAHcgRDlfgZMl16DhWgdrLw7kBAIZDgA7khNq+nHPOOe5Z9jR0ldrahK6Wy1nrbUIeDKW2X6raHrqFCxfa8dlHKg95XvTjoOjfV428bJOtW7dm3jYUALJGgA4AAAAAQADoJA4AAAAAgAAQoAMAAAAAEAACdAAAAAAAAkCADgAAAABAAAjQAQAAAAAIAAE6AAAAAAABSHWYtfhHNTQ0uDkAlYoeRxxDAACcGn9dHck1ld+0QPGF+ps71RL0rq4u09jYaKcVK1a4VAAj4Y8jPQIAgJHTD++9e/eaBx980EyZMqXia6ret27dOvueMWPG2Gnu3Llm27Zt7hUAimD79u0DcaumkKS6NLNnz3ZzxkyaNMnNAajUM888Y3p6eszy5ctdCgAAGAn98J41a5Z5+umnzcSJE22AXamFCxeau+66y6xcudIcP37cfPjhh2bq1KnmiiuusNdoAMUwZ84cN2dMS0uLmwtDqgF6c3OzmzOmtbXVzQGoRG9vr/nRj35knnjiCZcCAABGSj+8d+7cadasWWPmzZvnUoenwH7Lli320b9vwoQJZvXq1eb++++312hdqwEUQ1NTk30MLW5NNUBXdSAvOg9gePoBoCp40Tt6AACgNnbs2GFL0Nva2lzKZ26++WZz9OhRs3//fpcCIO8mT55sH6dNm2YfQ5FqgO7vQojuOAKozJ49e8yGDRtsuzcAAFB7ulGuUvcklJwDxeNrf48bN84+hiLVAH3GjBn2sb293T4CqMzPf/5zc/vtt3NjCwCAACl47+jooJYbUCC+xrf6mQhJqgG66OQV2koCIVMPsx9//LGtPgcAAMKivmE2btxoHn/8cZcCoAgUs2p4NcWvIUk9QFfbnPXr17tnAMo5cuSIufvuu22QDgAAwqEh1xSc33LLLWbr1q0DNUUBFIM6g9RoDUn9Toym1AN0AJVTqfmCBQvMV7/6VftDwE9edB4AANSGrr/Lli0jOAdQcwTowCg6fPiwWbt2rRkzZsyg6Z577jG7d++28wAAoHYUnKs3d/Xqrk5cCc4BeL4wLctCNAJ0YBRpnFZVrYlPy5cvN52dnXYeAADUhpqeKTg/cOCAHQ89tKqvAEaXhkRubGy0k84RWSBABwAAQN1TcK5e2lW7TT+84yOrZFliBiB8Gm5RNVxFBWlZjepAgA4EJF5lhh8DAACMnL+exq+pSene9OnT7bBLqtp+xhlnDHn9+PHjMysxAxA+nRu8VatWubn0NZw44RABAIH40pe+ZHp6etyzk6jmDgBA5RREX3755e5ZMjUl09jmUaqyOhx1GMdY6EB9uuGGG8yjjz5qS8937drlUtNHgA4AAAAAQBmtra22IG3btm2Z3qijijsAAAAAACV0d3fb4DzLtuceAToAAAAAACX09fWZhoaGTNuee1RxBwAAAAAgAJSgAwAAAAAQAAJ0AAAAAAACQIAOAAAAAEAACNABAAAAAAgAAToAAAAAAAEgQAcAAAAAIAAE6AAAAAAABIAAHaiB/v5+OwEAgHRwbQVQRAToQA10dXWZFStWuGcAAOBU6bqq6ysAFEmqAbq/k8kdTeAz27dvN7t37zYLFy50KenjeAMA1JPe3l6zdu1as2jRIpcSDq7JQD6EGremGqDrLmZjY6OdKC0ETrrzzjvN/PnzTVtbm0tJn469TZs2uWcAABTbmjVrzLhx48zixYtdSji4JgPhUwGaj1s1hSTVpZk9e7abM2bSpEluDqhf3d3dtvR8wYIFLiU7+/btc3MAABTbhg0banJtrRbXZCBsc+bMcXPGtLS0uLkwpBqgNzc3uzljWltb3RxQv1avXm06OzsHnQQAAED11q1bZ44dO2aWLVvmUgBg5JqamuxjaHFrqgH6lClT3NzgeaAeqfR848aNZtWqVS4FAACcKjUdW7JkiZkwYYJLAYCRmzx5sn2cNm2afQxFqgG6vwshnDRR7x599FFbZYbScwAA0qG23T09PZl2vAqgPvja3+rPIiSpBugzZsywj+3t7fYRqFfqXVbt4yg9BwAgPY888kjmHa8CqA++xvfUqVPtYyhSDdClo6MjuJUEai3k3mUBAMgjP2wpIwUBSINi1oaGBhu/hiT1AH3//v1m/fr17hlQf/zYrJSeAwCQnloMWwqgfsybN88cP348uHNK6gE6UO+2bNliH+fOnWsfAQDAqanlsKUAMJoI0IGU0bssAADpYthSACHo7+8fmLJCgA6kiLFZAQBIF8OWAghFV1eXaWxstJP6xcgCATqQInUOp6rtlJ4DAJAOhi0FEAL1M6WmNpJljR4CdCAluot28OBBepcFACAlDFsKIBQ7duxwcybTcxIBOpASepcFACBdDFsKIBQ+QM+6PwwCdCAFe/futVVeli5d6lIAAMCp0rClN9xwg3sGAKPn2WeftY9Z1+ghQAdSoKHVZs6caWbMmOFSAADAqVDTsYaGBrNw4UKXAgCjQ51V9vT01GQ0CQJ0IAUa/mXnzp3uWe3pB0xzc7N7BgBA/ulH8EcffZS7jle5JgPF09fXZ4/tWvSH0dCf5SBuAAAAAACgIgTodYgsT4/upOUBeZ6evOQ5gOpwvhx9RT/Pso+NPq7lCBkBep1R+4lzzjnHPaucxh9Vu4vQ1Xo5jx8/7ubCtW7dOvOjH/3IPasceT6U2h2NZlMGANlTe+eNGze6Z9nLw7m21su4devWwo55npdrcpG/j2s5QkeADgAAAABAAOgkDgAAAACAABCgAwAAAAAQAAJ0AAAAAAACQIAOAAAAAEAACNABAAAAAAgAAToAAAAAAAFIdZi1+Ec1NDS4OdQKeQCMnqTTKccgkA1/vI3kGOMaCaCU6PmhmnPDqb4ftRdqnqVagt7V1WUaGxvttGLFCpeKWtAOtm7dOjNlyhQzZswYO82dO9ds27bNvQJAVnT8HTp0yCxcuNBMnDhx4Bi88cYb3SsApEHH2pEjR8ymTZvs8TZ+/Hizfft299/y9N5ly5aZz3/+8/b41LH64IMPuv8CqFc6N+g8ovPDl770papimN7eXns+IgbKD+W5j1s1hSTVpZk9e7abM2bSpEluDrWgHyp33XWXWblypTl+/Lj58MMPzdSpU80VV1xhnnnmGfcqAGnThV0X4wsuuMBe2HW86RjUtGbNGvcqAGn43ve+Z374wx+aw4cP2+Pu6NGj7j/D003r1tZW89FHH9nj8/XXXzc7duwgSAfqmI7/WbNm2XPB/Pnz7TmiGqtXrzZXX3216ezsdCkI3Zw5c9ycMS0tLW4uDKlWcddOfsstt9h5ldxGVxzZ0R2gb33rW2bv3r2mra3NpZ6kPLn77rtNd3e3mTBhgksFkJYbbrjBXth1HHKMAbWlKomV/N7QtfCVV14xzz33nEs5SaVe559/vvnLX/4y5PoJoP7MnDnTFjjqt3OldA76p3/6J/tb+9prrx3x+zF6mpub7Y1e3VjZtWuXSx19qZagq3q1F51HthQcqAQ96cfFzTffbHe8/fv3uxQAaVFQ/uyzzxKcA4H7l3/5F1vDLE7H7TXXXGMeffRRlwIAI6Pf2rfffju/A3Jo8uTJ9nHatGn2MRSpBuhNTU1u7uRFD7WhajWlqtKqdABANnTcrVq1ivMdEDBdB3t6esyMGTNcymCq0vrmm2+6ZwBQOdXOUfyjIB35oxJ0GTdunH0MRaoBur/4tbe320eMPgXvHR0dNDcAMvD888/bdq2i1kLRCUAYhqtBRo0/ANVQh5Wqyv7QQw+5FOSNP/+r366QpN5lnYLB0FayXj3xxBNm48aN5vHHH3cpANKiau1yxhln2GMtPoKCenUHkA+7d+92cwBQmcWLF5sFCxaUrJ2D8ClmVV8mil9DknqArjvV69evd88wGlR6p4BBHfZt3bqVEweQIfUkrWNNw7No9ARNX//6122HMQTpAAAUjzqG0409hlTLt3nz5tlRPULrJDT1AB2jS8G5AgWCc6A27rnnHnus6U662qJr0rzapf385z93rwIQMprmARgJDff42GOP2Vp0Sc3bovPASBGgF4hOBurNXb2679mzh+AcyJDGPBeNm1rqWAtpyA6gXvk2hhoCKYmGXwutgyAAYfvggw/Mt7/97YGmbX5Sqbpu3GtsdRRT0g2ZtBGgF4Q6qlBwfuDAAds2lvFcgWzpGNO4mQDCplot6ql9586dLmUwNc0LbYgdAGFTteikSb8Lli9fXvJ8g/zr6uoyjY2NdvL9EaWNAL0AFJyrl/bDhw8njsdMNRsgGxpibcuWLfYYjNIxpx/9vod3AKNLvSw/9dRTQ66H6ifihRdeMEuXLnUpAAAk07CdvlNR3YzJapQsAvQCmD59uq3Cp6rt8bYwmsaPH5/ZHR6gnunErJoretQPfR1velSnMariRucxQLri17dSaXHqCEjXQh2v/nU6Vr/1rW/ZkU6odQbUp+i5Q5OXlFZO0vtRPIq1PBXSZIUAvQDUDubpp58e0g7GT8eOHXOvBJC2NWvW2I4ZL7vsMnu8nXvuubapiTqO40c/kC6164xe3zQ8zhVXXDEorZR169bZ13/+85+3r9Mxq2NXnToCqE8rV64cdP549dVXzb333jsobbhCLvVvEX8/bdCLyQfoWZaeS0M/t3gAAAAAAChJ/Zn09PTYYfayDNApQQcAAAAAoATVlFBwnnXpuRCgAwAAAABQQl9fn20mlWXbc48q7gAAAAAABIASdAAAAAAAAkCADgAAAABAAAjQAQAAAAAIAAE6AAAAAAABIEAHAAAAACAABOgAAAAAAASAAB0AAAAAgAAQoOeIhqxn2HqgtjjmgNrjuAOQJs4pyBMC9Bzp6uoyK1ascM8AZK23t9eMHz/ebN++3aUAyJqOt8ZGfp4ASAfXcuRNqldAX8LrJ6RHJ5Xdu3ebhQsXupT0kWfAYGvWrDHjxo0zc+bMcSnp47gDBrvzzjvN/Pnz3bOwcLwC+VOLa3m1OKeMLm1/P4Uk1QBdJby6662Jkt50+R8sbW1tLiV9yr9Nmza5Z0B90x33tWvXmlWrVrmUbOh8qe8C8NnN6BB/Q2jZpkyZ4p4ByINaXcurwTlldGn7+7hVU0hSXZrZs2e7OWMmTZrk5nCquru77Q+WBQsWuJTs7Nu3z80B9W3Lli32ce7cufYxS/v373dzQH3bsGGD6ezszPRm9Kk4ePCgmwOQB7W8lleDc8roidaoaGlpcXNhSDVAb25udnPGtLa2ujmcqtWrV9sfLCFWzQGKSrVWlixZYiZMmOBSAGRJN6M3btwYZEkXgHziWo5ympqa7GNocWuqAXq0mgZVNtLBDxag9tatW2eOHTtmli1b5lIAZI2b0QDSxLUcw5k8ebJ9nDZtmn0MRaoBur8LIdypSsejjz5qq13wgwWoHXUoo+pwnMeA2lA7Ud2MXrRokUsBgFPDtRzD8bW/1YlgSFIN0GfMmGEf29vb7SNOjX6wqD0epedA7ajTELUJo6NLoHb0Q1o3oxcvXuxSAKB6XMtRCV/je+rUqfYxFKkG6NLR0RHcSuaVHxaCHyxA7dRixAQAnwm5l2UA+cS1HJVQzNrQ0GDj15CkHqCrN+L169e7Z6gWP1iA2tMd91CHeAKKipvRANLEtRyVmjdvnjl+/HhwN3JSD9CRjtCHhQCKKPQhnoAi0nFXi2FEAdQHruXIOwL0QDEsBFBbjJgA1B69LANIE9dyZK2/v39gygoBeoD4wQLUHkM8AbXHzWgAaeJajqx1dXWZxsZGO6k5RRYI0APEsBBAbTHEE1B7mzZtMj09PWbhwoUuBQCqx7UcWdM+pv4NJMsbQQTogWFYCKD2GOIJqL1HHnmEXpYBpIZrObK2Y8cON2cybUZBgB4YhoUAaosRE4Dao5dlAGniWo5a8AF61s0oCNADsnfvXvuDZenSpS4FQNb8sJDccQdqRyVdV155JTejAaSCazlq4dlnn7WPWd8IIkAPiIZWmzlzppkxY4ZLAZC1zZs3c1MMqLEXXniBjlABpIZrObKmEQLUb0otOiEkQA+Iep7cuXOne1Z7DQ0Nprm52T0D6oOOOR17o0XHXVNTk3sG1Ifjx4/nspdlrpFAmEb7Wl4tzin50dfXZ3+z1aIZRUN/loO4AQAAAACAihCgJ6j1JtHdmDxguyBL7F/JarldOObqD8ddetiWAMdBmtiW9Ysq7gm+973vmTFjxox4mjhxYmL6cFNWg9ynSe0ukpY9q2nlypXum1Evqj1+qn1fHqxbty5x2bOa8nAuQnqqPa9Xe8zNmjXLfXMxcQ4DOA7SVG08Uu2EcFCCDgAAAABAAChBBwAAAAAgAAToAAAAAAAEgAAdAAAAAIAAEKADAAAAABAAAnQAAAAAAAJAgA4AAAAAQABSHWYt/lGhDnjvl5MB+fMlaVclD8M23OmF/AtTJZcF8i58ebkmIz3RPB9Jfvv3sY/Uj2ryPOnawD5TfCPZV5L2kajQ9pfo8oa0bKmWoHd1dZnGxkY7rVixwqWGQRlw5MgRs2nTJrNw4UIzfvx4s337dvdfhEz59uCDD9r9a8yYMXaaOHGi3cf0P4RLeaTzgc+3+IQwRY+1pEl5yvkzbHv27BmUj1OnTiXPCky/cZS/y5YtM1/60pcq+g3G76L6ozzv7u4269atM3PnzrXn8krwO6z+aF/Zu3evzfcpU6bYvK9Eud98K1eudK8Kg853Wl4/hSTVpZk9e7abM2bSpEluLgzf+973zA9/+ENz+PBhe0I5evSo+w9Cd84555iDBw+aVatWmePHj9vpmWeeMc8995yZM2eOexVC1dnZOZBv8Qlh0g/1rVu3JubZf/7nf9rXKAhAmBScX3755eaiiy4yH374oc23xx9/3GzcuNH+MEex6Af0rFmzzI4dO8z8+fNNa2ur+095/C6qL729vXY/ufvuu+1z5X+l+B1WXxS4al95+umn7Y0Y3cwZiVK/H1avXu1eEYbovtvS0uLmAtGfogceeED1BOy0bds2lxqmPCwjyjty5Ej/iQOq/4knnnApCM3y5cv7TwTo7hmKQMdbe3u7e4YQ6ZjTsZfkRABnz50ornL5Xw6/i+qL8vpUwwB+h9WHkfyWy9t5pKmpyS5zaL9VUy1BVxUILzoPZGHChAm2pOC9995zKQCy9u///u8jvpuO2tq9e/egGm1ROmeuX7/ePQOA6vE7DHk3efJk+zht2jT7GIpUA/SmpiY3d/KgBbLU399v3n///eCaU2Ao5VV8Qv6oiuTzzz9vrr76apeCPHr22WfdHABUT9dyfochSfw3n6YQNTc328dx48bZx1CkGqDPmDHDPra3t9tHIG3+ID906JAtxVNb2cWLF7v/IkTHjh2z7RvVjsl3FKK8UztZ5MuWLVtsOy1/rkeYZs6caV555ZUhP4jUmZPy8K233nIpADAy/A7DcHT90b7hf/P5DgXj16QQ+Brf6kg1JKl3WdfR0RHcSqI4fJB37rnnmr6+PrNt2zb3H4RId9V7enrs0BXqUEadhKjTqq9//evmW9/6FkF6zqh6+zXXXOOeIVQPPfSQuffeewd6WNakjsTU0ZOORToDA1AtfoehHDV5UIeV6oTQd1Kq338HDhywo0WERjGrrouKX0OSeoC+f/9+2rchM3/729/sAa8eiT/++GNz880322q3CJPuqn/00Ue2505f6qrmL0pXb7A///nPbRryQdXb1Us0wqZj7bXXXrM/iP7hH/7BTurBXedNBeoAUC1+h6Ec7R87d+408+bNG2jurGuSam+pZD20oRy1nLqJ0NbW5lLCkHqADmTNB3i6GaSOSUIbtgGV0V1WdWaFfNBYyepnhOrt+eB/EPnhbXS+1A8RifYXAwAjxe8wVEO/+xSkY3gE6Mi1G2+80WzYsME9A5CVzZs303t7AShoVxt1AEgDv8NQb3w/DFm2qSdAR66pJIj2lGEa7uSlfKMkLz8U2NF7e76pLbp+SC9btsylAMCp4XcYvOECVnUa7HtNz7Ouri7T2Nhop6yq7BOgI3ilDnil33nnnWbBggUuBSFRB1XqHVNBQZzy7q677iLvckLV28VXkUb+6DhUlVTdZJkzZ45LBYDh8TsMlVDngU888cSQ/UXP1VGcOg3O+41+9bfgm2d2dnZmdj2tmwBdO0d0KpWGsKhDI/WwqEf1+O3zSge67mCpgxI6PQqTSul0Z3369Olm3bp1NkDweafAXb1mKohH+Kjeni+6o++PN026wXLZZZeZf/zHf6QT1wLy+ewnLyktKvp//5qkNBRHUv4mpUXxO6w+Je0T0bRouqeOA2+55RbbW7vfVzQcn37rffvb37b7SWidsY2Ueqj31NlxZk5svLowc+bM/hMBQdkJYTpxkPcvWLCgv7W1dSCvNH/77bf3n/gR6l6FUD3xxBODjj/yLn86Ojr6T/wYc88QuquuumrQ8abz54kfSe6/KBqdT31+l5q2bdvmXv0ZfhfVn6Q8jk7aJ5LwO6y+6HwR3S+SJuV9El1r4vuKrklJ56A8Wrp0qe5M9Hd2drqUbNiz78lQHQAAAAAAxLW2ttqq+tu2bcu0uRht0AEAAAAAKKG7u9sG51m2PfcI0AEAAAAAKKGvr8/2n5Rp23OHKu4AAAAAAASAEnQAAAAAAAJAgA4AAAAAQAAI0AEAAAAACAABOgAAAAAAASBABwAAAAAgAAToAAAAAAAEgAAdAAAAAIAAFC5AZ1j3/CLv8ou8yyflG3mXT+Rd/SHPUSn2E1SCc0q4ChWgb9++3TQ2Uikgj8i7/CLv8mvFihWmq6vLPUOekHf1R/mtfAfK4ZqMSnFOCVdDf4q3TuIf1dDQ4OZqY+bMmWbSpElmw4YNLiV9Wsdar1c9IO/yK+u88+cV8i5dvb29pq2tzTz00ENm8eLFLjVd5F02apV35Fs4FHRddtll5tChQzbvQ8K+EpZa/J6qBteDsHBOOcnvlxLSvpnqLTbdidFdO021viOjHW337t2Zfq++Y8qUKe4Z0kLe5Vct8k6fvWzZMvcMaVmzZo0ZN25cZgGekHfZqEXe6Xq+adMm9wyj7c477zTz588P7oe06Defbhph9NXimlwtrgdhCfmcUqvrj44XH7dqCkmqSzN79mw3Z+zdu1rSncLOzs7Md7SDBw+6OaSFvMuvWuXdm2++6eaQFuXdggUL3LPskHfpq1Xe7du3z81hNHV3d9ugqxZ5Xq39+/e7OYymWl2Tq8X1IAx5OKfU4vozZ84cN2dMS0uLmwtDqgF6c3OzmzOmtbXVzWVPO9rGjRvNqlWrXArygrzLL/Iuv9atW2eOHTtGaUYOkXf1Z/Xq1Tboiv6YBOK4JqNSnFM+09TUZB9rGbdWItUAPVqFuJbVidnR8ou8yy/yLr9UtW3JkiVmwoQJLgV5Qd7VF4IuVIprMirBOWWwyZMn28dp06bZx1CkGqD7uxBSqx8PavekHW3RokUuBXlB3uUXeZdfatfV09NjFi5c6FKQF+Rd/Xn00Udt1UuCLpTDNRmV4pwymK/9rX5dQpJqgD5jxgz72N7ebh9rQZ3laEfLsrMcZIO8yy/yLr8eeeSRYDuGQXnkXX1R0KU2xZR0YThck1EJzilD+RrfU6dOtY+hSDVAl46OjpqtpHa0tWvXsqPlEHmXX+RdfoXcwy/KI+/qTy1660f+cU1GpTinDKWYVcOrKX4NSeoBunryXL9+vXuWLXa0/CLv8ou8y6+Qh1VBeeRdfSHoQqW4JqMSnFOSzZs3zxw/fjy4a2vqAXot1WqoGaSPvMsv8i6f1DFM6MOqIBl5V3+2bNliH+fOnWsfgVK4JqMSnFPyJbcBOkPN5Bd5l1/kXX7Rw29+kXf1h976UQmuyagU55T09Pf3D0xZyW2Azo6WX+RdfpF3+cSwKvlF3tUfgi5UimsyKsE5JV1dXV2msbHRTuofJgu5DNAZaia/yLv8Iu/yi2FV8ou8qz9qU6xqqARdKIdrMirFOSU9asuvJmeSZc22XAboDDWTX+RdfpF3+aSLCcOq5BN5V39UGnPw4EF668ewuCajEpxT0rVjxw43ZzK9NucuQGeomfwi7/KLvMsvevjNL/Ku/qjKMkEXhsM1GZXinJIuH6Bn3S9M7gJ0/WC58sor2dFyiLzLL/IuvzSsyg033OCeIU/Iu/qyd+9eG3QtXbrUpQDJuCajEpxT0vfss8/ax6xrtuUuQH/hhRfo5CCnyLv8Iu/ySaUsDQ0NtFHMIfKu/mgYpJkzZ5oZM2a4FCAZ12RUgnNKutRpq/p9qMWoKrkL0DWY/Gh2ltPc3OzmMFLkXX6NZt4pSBk/frx7hpFQnn300Uej1jEMeVe9EPKOc2ZtaTi9nTt3umf5oX2lqanJPUMtjPbvqWpwPai9PJ9TQrz+9PX12WWrRb8wDf1ZDuIGAAAAAAAqkste3AEAAAAAKBoCdAAAAAAAAkCADgAAAABAAAjQAQAAAAAIAAE6AAAAAAABIEAHAAAAACAABOgAAAAAAASAAB0AAAAAgAAEEaD39/e7ucHzRVHk9auXvNMjeZcv5F0+FXndhLyrP35b6JHtchL7ylBsk2R+W+iR7XIS+8pQRdsmqQbo2iDRqVJz5841Dz74oJ3v6uoymzZtsvNFsHfvXjN+/Hg7v337djNlyhQ7XxRFzjutl9ZPVqxYYZYtW2bni0L7pfZPaWxsNL29vXa+CMi7/OJ6kF9FzrtqFf1cVI2iHwfVKvJ5vVocP0Nx/CSr9vgZadwafX2l76lGqgG6LsjaKJp0IFWqr6/PTvLWW2+ZpqYmO18ER48etZPs37/fjBs3zs4XRZHzLrpuRcw7v2/6E9qECRPsYxGQd/kVzTuuB/lS5LyrVnSbFDHPq1H046BafrsU8bxeLY6foTh+klVz/OgGh49bNQ2nu7vbjBkzZmCq5D3VSvWTZ8+e7eaMmTRpkpsb3rFjxwbe63e6otD6dHZ22nl/kimSIudddN2Klnf+zuKcOXMKl29C3uUX14P8KnLeVavI56JqFf04qEbRz+vV4vgZiuNnqGqPH73ea2lpcXOltbW1mePHj9tp69atLjUbqQbozc3Nbs6Y1tZWNze8gwcPurmTilRdY9++fW7upGnTprm5Yihy3r355ptu7qSpU6e6ufzTXdeo9vZ2N1cM5F1+cT3IryLnXbWKfC6qVtGPg2oU/bxeLY6foTh+hjqV48fX9BpJ3FoLqQbo0YvxSC/M2kCqaiBFq9bjb1y88sorhayKUg95t3v37sJV1/TrU9T9krzLr3o4p5B39aPI56JqFf04qEbRz+vV4vgZiuNnqGqPn8mTJ9vH0G50pBqgRw+c4S7MvnH9nj177PPp06cPNLbPuuF9Lfh10F0d3ayIrk/e188vf9HzTm0oOzo6hqybf55Hfvl1B1Ynpei65H3dxK8DeZcvfvm5HuSPX/6i5l21/LoX8VxULb/eRTwOquXXu6jX5Gr5def4+Yxfb46fz/j1PpXjx9/sCO5Gx4mFT5U+sr293T0r7fbbb+9vaGiwk97jH/28pm3btrlX50903aLr59NnzpzpXpk/Rc47LXd83eLzWv+80n7n18evU3ReU16Rd/nNO64HXA+KpOjnompFt4PfFtFtkufjoFpFPq9Xi+MnWXQ7+G0R3SYcP59tk+h2Gc7y5cvt65955hmXUhntp3pfVlL/5I6Ojv4FCxa4Z8OLrqA2Umdnp50vCq2P1ku0nkX6oVL0vPP5lfVBOBqi+RXdR4uCvMunop9Tovnl99GiKHreVavI56JqFfk4qFb0mIlun3rH8TMUx89Qp3L8KDBXIH/o0CGXUpms98nU+4dX1Yv169e7ZwAAAAAAhGXevHm2V3b10B6S1AP0SvX3n2wboMk/96LpeRVfBz/v06P/y5v4OkTXJZqeR375/TqUms+r+DrE5/O8fn75/TqUms+r+DrE5/O8fn75/TpE1yWanlfxdfDzPj36v7yJr0N0XaLp9cSvt1/3UvP1Jr7u8W0S/V+9iK93fL6et4lf91Lz9Sa+7vFtEv1fvYivd3w+19vkxMKPitbW1mHbDYy0ukEonnjiiYF1iK5PdH4kzQBCU+S8U774dYiuT3Re+ZtHypPo+vh1iq6b8javyLv85h3XA64HRVLkc1G1in4cVKPo5/VqcfwMxfEz1GgfP1lXcR+1AN2LthvQ/Pz58+18USjzfPsQzRfph0qR8y564Gm+paXFzhdFtI2O5ot0sSPv8qvI5xThelBfin4uqlaRj4NqFfm8Xi2On2QcP0ONxvET3T+zMGpV3KOi4/m1BjZQfBo0/JwfFza0Ng6nqsh5Fx1TsYj7ZXRsUfIuX4qcd1wP8qvoeVeNop+LqlXk46BaRT6vV4vjJxnHz1BFO35GPUD34/l5fgMXwd69e+3jjBkz7KM/0RRFkfNO66YxFb0irZtobNFo3hVp3yTv8ovrQX4VOe+qVfRzUTWKfhxUq8jn9Wpx/AzF8ZOsiMfPqAfofX19bm7oBs67o0ePurmhJ5oiKHLeRdct/sOzCPy+GT/ZFwF5l19cD/KryHlXraKfi6pR9OOgWkU+r1eL42cojp9kRTx+Rj1Ab2hoMLNnzx6YL9rdoJkzZ7o5Y8aPH+/miqHIeaf1ueiiiwbmi3bnVus0Z84cO1/EdSPv8knrxvUgn4qed9XQdijyuahaRT4OqqX9o6jn9Wpx/CTj+BmqiMdPgxqiu3kAAAAAABDjw2b1AXD55ZcPPE8bAToAAAAAACV0d3ebc845xz076fjx424uXQToAAAAAAAEIIhh1gAAAAAAqHcE6AAAAAAABIAAHQAAAACAABCgAwAAAAAQAAJ0AAAAAAACQIAOAAAAAEAACNABAAAAAAgAAToAAAAAAAEgQAcAAAAAIAAE6AAAAAAABIAAHQAAAACAUWfM/w8smvCeXtTw0AAAAABJRU5ErkJggg=="
    }
   },
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Please make sure you go over the following question at home:\n",
    "\n",
    "\n",
    "<b>Question:</b> Assume $N = 2^n - 1$ for some $n$, find a method of inserting the numbers $[1,...,N]$ to a BST such that it is completely balanced (i.e. - it is a complete tree).\n",
    "Specifically, you are requested to add a method to the Binary_search_tree class to support the following:\n",
    "\n",
    "![image.png](attachment:image.png)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "<b>Solution:</b> As we usually do with trees, we give a recursive solution. Our input will be a node and a first and last index to enter into the tree rooted in the node. We start with the root, $first = 1, last = 2^n - 1$\n",
    "\n",
    "- Base case: If $first = last$ then we simply need to create a root with no sons labeled $first$ \n",
    "- Otherwise, we find the mid point $mid = (first + last - 1 ) // 2$. We recursively insert $first,...,mid$ into the left son of the node, $mid + 1$ into the current node and $mid + 2, ..., last$ into the right son of the node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['                              8                                    ',\n",
       " '               ______________/ |________________                   ',\n",
       " '              4                                 12                 ',\n",
       " '       ______/ |______                  _______/  |_______         ',\n",
       " '      2               6               10                  14       ',\n",
       " '   __/ |__         __/ |__         __/  |__            __/  |__    ',\n",
       " '  1       3       5       7       9        11        13        15  ',\n",
       " ' / |     / |     / |     / |     / |      /  |      /  |      /  | ',\n",
       " '#   #   #   #   #   #   #   #   #   #    #    #    #    #    #    #']"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class Tree_node():\n",
    "    def __init__(self, key, val):\n",
    "        self.key = key\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "    def __repr__(self):\n",
    "        return \"(\" + str(self.key) + \":\" + str(self.val) + \")\"\n",
    "    \n",
    "    \n",
    "    \n",
    "class Binary_search_tree():\n",
    "\n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "\n",
    "\n",
    "    def __repr__(self): #no need to understand the implementation of this one\n",
    "        out = \"\"\n",
    "        for row in printree(self.root): #need printree.py file\n",
    "            out = out + row + \"\\n\"\n",
    "        return out\n",
    "\n",
    "\n",
    "    def lookup(self, key):\n",
    "        ''' return node with key, uses recursion '''\n",
    "\n",
    "        def lookup_rec(node, key):\n",
    "            if node == None:\n",
    "                return None\n",
    "            elif key == node.key:\n",
    "                return node\n",
    "            elif key < node.key:\n",
    "                return lookup_rec(node.left, key)\n",
    "            else:\n",
    "                return lookup_rec(node.right, key)\n",
    "\n",
    "        return lookup_rec(self.root, key)\n",
    "\n",
    "\n",
    "\n",
    "    def insert(self, key, val):\n",
    "        ''' insert node with key,val into tree, uses recursion '''\n",
    "\n",
    "        def insert_rec(node, key, val):\n",
    "            if key == node.key:\n",
    "                node.val = val     # update the val for this key\n",
    "            elif key < node.key:\n",
    "                if node.left == None:\n",
    "                    node.left = Tree_node(key, val)\n",
    "                else:\n",
    "                    insert_rec(node.left, key, val)\n",
    "            else: #key > node.key:\n",
    "                if node.right == None:\n",
    "                    node.right = Tree_node(key, val)\n",
    "                else:\n",
    "                    insert_rec(node.right, key, val)\n",
    "            return\n",
    "        \n",
    "        if self.root == None: #empty tree\n",
    "            self.root = Tree_node(key, val)\n",
    "        else:\n",
    "            insert_rec(self.root, key, val)\n",
    "\n",
    "\n",
    "    def minimum(self):\n",
    "        ''' return node with minimal key '''\n",
    "        if self.root == None:\n",
    "            return None\n",
    "        node = self.root\n",
    "        left = node.left\n",
    "        while left != None:\n",
    "            node = left\n",
    "            left = node.left\n",
    "        return node\n",
    "\n",
    "\n",
    "    def depth(self):\n",
    "        ''' return depth of tree, uses recursion'''\n",
    "        def depth_rec(node):\n",
    "            if node == None:\n",
    "                return -1\n",
    "            else:\n",
    "                return 1 + max(depth_rec(node.left), depth_rec(node.right))\n",
    "\n",
    "        return depth_rec(self.root)\n",
    "\n",
    "\n",
    "    def size(self):\n",
    "        ''' return number of nodes in tree, uses recursion '''\n",
    "        def size_rec(node):\n",
    "            if node == None:\n",
    "                return 0\n",
    "            else:\n",
    "                return 1 + size_rec(node.left) + size_rec(node.right)\n",
    "\n",
    "        return size_rec(self.root)\n",
    "    \n",
    "    def inorder(self):\n",
    "        '''prints the keys of the tree in a sorted order'''\n",
    "        def inorder_rec(node):\n",
    "            if node == None:\n",
    "                return\n",
    "            inorder_rec(node.left)\n",
    "            print(node.key)\n",
    "            inorder_rec(node.right)\n",
    "            \n",
    "        inorder_rec(self.root)\n",
    "    \n",
    "    def insert_balanced(self, n):\n",
    "        def insert_balanced_rec(first, last):\n",
    "            if first == last:\n",
    "                return Tree_node(first, first)\n",
    "            mid = (first + last) // 2\n",
    "            root = Tree_node(mid, mid)\n",
    "            root.left = insert_balanced_rec(first, mid - 1)\n",
    "            root.right = insert_balanced_rec(mid + 1, last)\n",
    "            return root\n",
    "        self.root = insert_balanced_rec(1, 2**n - 1)            \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "t = Binary_search_tree()\n",
    "t.insert_balanced(4)\n",
    "printree(t.root)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Hash Tables\n",
    "\n",
    "We wish to have a data structure that implements the operations: insert, search and delete in **expected** $O(1)$ time. \n",
    "\n",
    "Summarizing the insert and search complexity of the data structures that we have seen already:\n",
    "\n",
    "| implementation                | insert                   | search   | delete              |\n",
    "|-------------------------------|--------------------------|----------|---------------------|\n",
    "| Python list                   | O(1) always at the end   | O(n)     | O(n)                |\n",
    "| Python ordered list           | O(n)                     | O(log n) | O(n)                |\n",
    "| Linked list                   | O(1) always at the start | O(n)     | O(1) given the node before the one to delete |\n",
    "| Sorted linked list            | O(n)                     | O(n)     | O(1) given the node before the one to delete |\n",
    "| Unbalanced Binary Search Tree | O(n)                     | O(n)     | O(n)                |\n",
    "| Balanced Binary Search Tree   | O(log n)                 | O(log n) | O(log n)            |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Please read <a href=\"https://github.com/taucsrec/recitations/blob/master/2018b/Michal/rec9/DataStructures_summary.pdf\"> the following summary</a> on the various data structures mentioned in class.\n",
    "\n",
    "A detailed summary on the complexity of insert/search operations using hash tables can be found <a href=\"http://tau-cs1001-py.wdfiles.com/local--files/recitation-logs-2017a/hashtable_find_and_insert_complexity.pdf\">here</a>. Make sure you read it."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise: \n",
    "Given a string $st$ of length $n$ and a small integer $\\ell$, write a function that checks whether there is a substring in $st$ of length $\\ell$ that appears more than once.\n",
    "\n",
    "#### Solution \\#1: Naive\n",
    "The complexity is $O(\\ell(n-\\ell)^2)$. \n",
    "There $O((n-\\ell)^2)$ iterations (make sure you undersand why) and in each iteration we perform operations in $O(\\ell)$ time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def repeat_naive(st, l): \n",
    "    for i in range(len(st)-l+1):\n",
    "        for j in range(i+1,len(st)-l+1):\n",
    "            if st[i:i+l]==st[j:j+l]:\n",
    "                return True\n",
    "    return False\n",
    "\n",
    "repeat_naive(\"hello\", 1)\n",
    "repeat_naive(\"hello\"*10, 45)\n",
    "repeat_naive(\"hello\"*10, 46)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's test our algorithm with by generating a random string of a given size."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "dlotznwapuossuxedpcsvzoufxhqvfonloryhpgsyrzyolkfmfxpwnmeizpdykeckfmgaeaadsgnyzqsxcfhpwouweerlqdsguvygjueogzluetlacuhaimdosiqewcwdmkisskuaqpyoebiinexfxffikzodqwkdofiqcbxhxcvflpylluotyjqndguigmgainmytznmirbeynyebitpcmaaaghaovddmmlcymdgqgjsaxkxrxvqpsvwuoxzddvwbixwdxnxxlmqfwmbozipvfpudijxttjgvkyziljouovunoylhuzlbmcgiiiqnftfxuzuktqsewcucoilfoigtixrlynmlnoxignmulzcajelhzwupblwwtbzgjbpyrsidazfpknzgvqqaajgnbwcbzmeefzkwaytkespouzqrureuwxppxdpyahgqziqsrherqiilcpwrdmtoaeefpabbvvzewfcvnrjifahqbjatyswtylywrdqvuemvhmdrbtvokopegwaljkpeafnysdbcswmavrpjkixrdxoenaebztyiiplhdxizpbyecjfcyirksttntxiihbtyzmsepctluedamzaqcnyvhazbycuygqxstxnhsvjbbgoupkqoocpuepnmnzkecqklxcbmmzlndjbafiqgihqfjzgnkmpzuhishmhytzpyqrtnppnwfnxisinqngbumlrtozmmnuzkbbjacforiuqbgewvtrctdpydsylivhorxjzkuvafvggysstzgjgprfhieebrlhvhurnfeybshvpiuvtpvtyykpkthraeeydqxvlladhcnsofrlaljylkxfqzrdeptbrgumynhdspzfabvgmzscnfmydswhxnmehzyziumeutuxxnshvovyfwovscdrfcqelivceiwujagevnaviolrlypxsplxtmdlkakvhntmwhvxzteabgzfyctntapasbatvqogxripapfdzlgphrno\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import random\n",
    "def gen_str(size, alphabet = \"abcdefghijklmnopqrstuvwxyz\"):\n",
    "    ''' Generate a random string of length size over alphabet '''\n",
    "    s=\"\"\n",
    "    for i in range(size):\n",
    "        s += random.choice(alphabet)\n",
    "    return s\n",
    "rndstr = gen_str(1000)\n",
    "print(rndstr)\n",
    "repeat_naive(rndstr, 3)\n",
    "repeat_naive(rndstr, 10)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For bigger $n$ and $\\ell$, this could be quite slow:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rndstr = gen_str(10000)\n",
    "repeat_naive(rndstr, 3)\n",
    "repeat_naive(rndstr, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The class Hashtable from the lectures"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Hashtable:\n",
    "    def __init__(self, m, hash_func=hash):\n",
    "        \"\"\" initial hash table, m empty entries \"\"\"\n",
    "        ##bogus initialization #1:\n",
    "        #self.table = [[]*m]\n",
    "        ##bogus initialization #2:\n",
    "        #empty=[]\n",
    "        #self.table = [empty for i in range(m)]\n",
    "        \n",
    "        self.table = [ [] for i in range(m)]\n",
    "        self.hash_mod = lambda x: hash_func(x) % m # using python hash function\n",
    "\n",
    "    def __repr__(self):\n",
    "        L = [self.table[i] for i in range(len(self.table))]\n",
    "        return \"\".join([str(i) + \" \" + str(L[i]) + \"\\n\" for i in range(len(self.table))])\n",
    "    \n",
    "    def find(self, item):\n",
    "        \"\"\" returns True if item in hashtable, False otherwise  \"\"\"\n",
    "        i = self.hash_mod(item)\n",
    "        return item in self.table[i]\n",
    "        #if item in self.table[i]:\n",
    "        #    return True\n",
    "        #else:\n",
    "        #    return False\n",
    "\n",
    "    def insert(self, item):\n",
    "        \"\"\" insert an item into table \"\"\"\n",
    "        i = self.hash_mod(item)\n",
    "        if item not in self.table[i]:\n",
    "            self.table[i].append(item)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution \\#2: using the class Hashtable"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def repeat_hash1(st, l):\n",
    "    m=len(st)-l+1\n",
    "    htable = Hashtable(m)\n",
    "    for i in range(len(st)-l+1):\n",
    "        if htable.find(st[i:i+l])==False:\n",
    "            htable.insert(st[i:i+l])\n",
    "        else:\n",
    "            return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The expected (average) complexity is: $O(\\ell(n-\\ell))$\n",
    "\n",
    "Creating the table takes $O(n-\\ell)$ time, and there are $O(n-\\ell)$ iterations, each taking expected $O(\\ell)$ time.\n",
    "\n",
    "\n",
    "\n",
    "The worst case complexity is: $O(\\ell(n-\\ell)^2)$\n",
    "\n",
    "Creating the table takes $O(n-\\ell)$ time, and the time for executing the loop is\n",
    "$\\ell\\cdot\\sum_{i=0}^{n-\\ell}{i}= O(\\ell(n-\\ell)^2)$\n",
    "\n",
    "Which native Python data structure is most suitable for this problem?\n",
    "\n",
    "#### Solution #3: using Python's set implementation\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def repeat_hash2(st, l):\n",
    "    htable = set() #Python sets use hash functions for fast lookup\n",
    "    for i in range(len(st)-l+1):\n",
    "        if st[i:i+l] not in htable:\n",
    "            htable.add(st[i:i+l])\n",
    "        else: return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Competition between the 3 solutions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "repeat_naive 0.42494059999989986 found? False\n",
      "repeat_hash1 0.0042048000000249885 found? False\n",
      "repeat_hash2 0.001372700000047189 found? False\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "str_len=1000\n",
    "st=gen_str(str_len)\n",
    "l=10\n",
    "for f in [repeat_naive,repeat_hash1,repeat_hash2]:\n",
    "    t0=time.perf_counter()\n",
    "    res=f(st, l)\n",
    "    t1=time.perf_counter()\n",
    "    print(f.__name__, t1-t0, \"found?\",res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "repeat_naive 1.633473399999957 found? False\n",
      "repeat_hash1 0.009137300000020332 found? False\n",
      "repeat_hash2 0.0028928000001542387 found? False\n"
     ]
    }
   ],
   "source": [
    "str_len=2000\n",
    "st=gen_str(str_len)\n",
    "l=10\n",
    "for f in [repeat_naive,repeat_hash1,repeat_hash2]:\n",
    "    t0=time.perf_counter()\n",
    "    res=f(st, l)\n",
    "    t1=time.perf_counter()\n",
    "    print(f.__name__, t1-t0, \"found?\",res)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For a random string of size $n=1000$ and for $l=10$ the running time of repeat_hash2 is the smallest, while the one for repeat_naive is the largest.\n",
    "\n",
    "When increasing $n$ to 2000, the running time of repeat_naive increases by ~4, while the running time of repeat_hash1, repeat_hash2 increases by ~2.\n",
    "\n",
    "#### Time spent on creating the table\n",
    "When $st$ is \"a\"$*1000$, repeat_hash1 is the slowest, since it spends time on creating an empty table of size 991."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "repeat_naive 6.799999937356915e-06 found? True\n",
      "repeat_hash1 0.00018980000004376052 found? True\n",
      "repeat_hash2 5.799999826194835e-06 found? True\n"
     ]
    }
   ],
   "source": [
    "st=\"a\"*1000\n",
    "l=10\n",
    "for f in [repeat_naive,repeat_hash1,repeat_hash2]:\n",
    "    t0=time.perf_counter()\n",
    "    res=f(st, l)\n",
    "    t1=time.perf_counter()\n",
    "    print(f.__name__, t1-t0, \"found?\",res)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The effect of table size\n",
    "\n",
    "The second solution, with control over the table size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def repeat_hash1_var_size(st, l, m=0):\n",
    "    if m==0: #default hash table size is ~number of substrings to be inserted\n",
    "        m=len(st)-l+1\n",
    "    htable = Hashtable(m)\n",
    "    for i in range(len(st)-l+1):\n",
    "        if htable.find(st[i:i+l])==False:\n",
    "            htable.insert(st[i:i+l])\n",
    "        else:\n",
    "            return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Comparing tables sizes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "str_len= 1000 repeating substring len= 10\n",
      "0.044579099999964455 found? False table size= 1\n",
      "0.00932720000014342 found? False table size= 10\n",
      "0.004570000000057917 found? False table size= 100\n",
      "0.0057033999999021034 found? False table size= 1000\n",
      "0.004408700000112731 found? False table size= 1500\n",
      "0.006572400000095513 found? False table size= 10000\n",
      "0.04230780000011691 found? False table size= 100000\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "str_len=1000\n",
    "st=gen_str(str_len)\n",
    "l=10\n",
    "print(\"str_len=\",str_len, \"repeating substring len=\",l)\n",
    "for m in [1, 10, 100, 1000, 1500, 10000, 100000]:\n",
    "    t0=time.perf_counter()\n",
    "    res=repeat_hash1_var_size(st, l, m)\n",
    "    t1=time.perf_counter()\n",
    "    print(t1-t0, \"found?\",res, \"table size=\",m)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Summary\n",
    "Make sure you read the following <a href=\"http://tau-cs1001-py.wdfiles.com/local--files/recitation-logs-2016b/m_10_repeating_substring_additional_material.pdf\">summary</a> that includes a detailed explanation on the experiments."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}