5.Trees.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": "true"
   },
   "source": [
    "# Table of Contents\n",
    " <p><div class=\"lev1\"><a href=\"#List-of-Lists-Representation-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>List of Lists Representation</a></div><div class=\"lev1\"><a href=\"#Nodes-and-References-2\"><span class=\"toc-item-num\">2&nbsp;&nbsp;</span>Nodes and References</a></div><div class=\"lev1\"><a href=\"#Parse-Tree-3\"><span class=\"toc-item-num\">3&nbsp;&nbsp;</span>Parse Tree</a></div><div class=\"lev1\"><a href=\"#Tree-Traversals-4\"><span class=\"toc-item-num\">4&nbsp;&nbsp;</span>Tree Traversals</a></div><div class=\"lev1\"><a href=\"#Priority-Queues-with-Binary-Heaps-5\"><span class=\"toc-item-num\">5&nbsp;&nbsp;</span>Priority Queues with Binary Heaps</a></div><div class=\"lev2\"><a href=\"#Binary-Heap-Implementation-5.1\"><span class=\"toc-item-num\">5.1&nbsp;&nbsp;</span>Binary Heap Implementation</a></div><div class=\"lev3\"><a href=\"#The-Structure-Property-5.1.1\"><span class=\"toc-item-num\">5.1.1&nbsp;&nbsp;</span>The Structure Property</a></div><div class=\"lev3\"><a href=\"#Heap-Operations-5.1.2\"><span class=\"toc-item-num\">5.1.2&nbsp;&nbsp;</span>Heap Operations</a></div><div class=\"lev1\"><a href=\"#Binary-Search-Trees-6\"><span class=\"toc-item-num\">6&nbsp;&nbsp;</span>Binary Search Trees</a></div><div class=\"lev2\"><a href=\"#Search-Tree-Implementation-6.1\"><span class=\"toc-item-num\">6.1&nbsp;&nbsp;</span>Search Tree Implementation</a></div><div class=\"lev1\"><a href=\"#Balanced-Binary-Search-Tree-7\"><span class=\"toc-item-num\">7&nbsp;&nbsp;</span>Balanced Binary Search Tree</a></div><div class=\"lev2\"><a href=\"#AVL-Tree-Performance-7.1\"><span class=\"toc-item-num\">7.1&nbsp;&nbsp;</span>AVL Tree Performance</a></div><div class=\"lev2\"><a href=\"#AVL-Tree-Implementation-7.2\"><span class=\"toc-item-num\">7.2&nbsp;&nbsp;</span>AVL Tree Implementation</a></div><div class=\"lev1\"><a href=\"#Summary-of-Map-ADT-Implementations-8\"><span class=\"toc-item-num\">8&nbsp;&nbsp;</span>Summary of Map ADT Implementations</a></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# List of Lists Representation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are several ways to represent a tree."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "code_folding": [],
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "myTree = ['a', #root\n",
    "         ['b',#left subtree\n",
    "          ['d',[],[]],\n",
    "          ['e',[],[]],],\n",
    "         ['c', #right subtree\n",
    "          ['f',[],[]],\n",
    "          [] ] \n",
    "         ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'a'"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myTree[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['b', ['d', [], []], ['e', [], []]]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myTree[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def BinaryTree(r):\n",
    "    return [r, [], []]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def insertLeft(root, newBranch):\n",
    "    \"\"\"If the list already has something in the second position,\n",
    "    we need to keep track of it and push it down the tree \n",
    "    as the left child of the list we are adding.\"\"\"\n",
    "    t = root.pop(1)\n",
    "    if len(t) > 1:\n",
    "        root.insert(1, [newBranch,t,[]])\n",
    "    else:\n",
    "        root.insert(1,[newBranch,[],[]])\n",
    "    return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def insertRight(root,newBranch):\n",
    "    t = root.pop(2)\n",
    "    if len(t)>1:\n",
    "        root.insert(2,[newBranch,[],t])\n",
    "    else:\n",
    "        root.insert(2,[newBranch,[],[]])\n",
    "    return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def getRootVal(root):\n",
    "    return root[0]\n",
    "\n",
    "def setRootVal(root,newVal):\n",
    "    root[0] = newVal\n",
    "    \n",
    "def getLeftChild(root):\n",
    "    return root[1]\n",
    "\n",
    "def getRightChild(root):\n",
    "    return root[2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Nodes and References"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "another method to represent a tree.\n",
    "\n",
    "Since this representation more closely follows the object-oriented programming paradigm, we will continue to use this representation for the remainder of the chapter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "code_folding": [
     0
    ],
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#implement a BinaryTree class\n",
    "class BinaryTree:\n",
    "    def __init__(self,rootObj):\n",
    "        self.key = rootObj\n",
    "        self.leftChild = None\n",
    "        self.rightChild = None\n",
    "        \n",
    "    def insertLeft(self,newNode):\n",
    "        if self.leftChild == None:\n",
    "            self.leftChild = BinaryTree(newNode)\n",
    "        else:\n",
    "            t = BinaryTree(newNode)\n",
    "            t.leftChild = self.leftChild\n",
    "            self.leftChild = t\n",
    "    \n",
    "    def insertRight(self,newNode):\n",
    "        if self.rightChild == None:\n",
    "            self.rightChild = BinaryTree(newNode)\n",
    "        else:\n",
    "            t = BinaryTree(newNode)\n",
    "            t.rightChild = self.rightChild\n",
    "            self.rightChild = t\n",
    "\n",
    "    def getRightChild(self):\n",
    "        return self.rightChild\n",
    "    \n",
    "    def getLeftChild(self):\n",
    "        return self.leftChild\n",
    "    \n",
    "    def setRootVal(self,obj):\n",
    "        self.key = obj\n",
    "    \n",
    "    def getRootVal(self):\n",
    "        return self.key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "r = BinaryTree('a')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'a'"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r.getRootVal()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "r.getLeftChild()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "r.insertLeft('b')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.BinaryTree at 0x103fb1550>"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r.getLeftChild()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'b'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r.getLeftChild().getRootVal()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "r.insertRight('c')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "r.getRightChild().setRootVal('hello')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'hello'"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r.getRightChild().getRootVal()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "code_folding": [
     0
    ],
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def buildTree():\n",
    "    t = BinaryTree('a')\n",
    "    \n",
    "    #Construct Left Subtree\n",
    "    t.insertLeft('b')\n",
    "    t.getLeftChild().insertRight('d')\n",
    "    \n",
    "    #Construct right one\n",
    "    t.insertRight('c')\n",
    "    t.getRightChild().insertLeft('e')\n",
    "    t.getRightChild().insertRight('f')\n",
    "    \n",
    "    return t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Parse Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Represent a mathematical expression such as $((7+3)*(5-2))$ as a parse tree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img  src=\"meParse.png\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How can we keep track of the parent? A simple solution to keeping track of parents as we traverse the tree is to use a stack. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "code_folding": [
     0
    ],
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Implementing s Stack\n",
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "    \n",
    "    def isEmpty(self):\n",
    "        return self.items == []\n",
    "    \n",
    "    def push(self, item):\n",
    "        self.items.append(item)\n",
    "        \n",
    "    def pop(self):\n",
    "        return self.items.pop()\n",
    "    \n",
    "    def peek(self):\n",
    "        return self.items[len(self.items)-1]\n",
    "        #when you'd like to extract the last item of the list, do not forget len(*)-1.\n",
    "    \n",
    "    def size(self):\n",
    "        return len(self.items)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "code_folding": [
     0
    ],
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#implement a BinaryTree class\n",
    "class BinaryTree:\n",
    "    def __init__(self,rootObj):\n",
    "        self.key = rootObj\n",
    "        self.leftChild = None\n",
    "        self.rightChild = None\n",
    "        \n",
    "    def insertLeft(self,newNode):\n",
    "        if self.leftChild == None:\n",
    "            self.leftChild = BinaryTree(newNode)\n",
    "        else:\n",
    "            t = BinaryTree(newNode)\n",
    "            t.leftChild = self.leftChild\n",
    "            self.leftChild = t\n",
    "    \n",
    "    def insertRight(self,newNode):\n",
    "        if self.rightChild == None:\n",
    "            self.rightChild = BinaryTree(newNode)\n",
    "        else:\n",
    "            t = BinaryTree(newNode)\n",
    "            t.rightChild = self.rightChild\n",
    "            self.rightChild = t\n",
    "\n",
    "    def getRightChild(self):\n",
    "        return self.rightChild\n",
    "    \n",
    "    def getLeftChild(self):\n",
    "        return self.leftChild\n",
    "    \n",
    "    def setRootVal(self,obj):\n",
    "        self.key = obj\n",
    "    \n",
    "    def getRootVal(self):\n",
    "        return self.key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "code_folding": [
     0
    ],
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def buildParseTree(fpexp):\n",
    "    #fpexp: fully parenthesized expression\n",
    "    \n",
    "    fplist = fpexp.split()\n",
    "    pStack = Stack()\n",
    "    eTree = BinaryTree('')\n",
    "    pStack.push(eTree)\n",
    "    currentTree = eTree\n",
    "    \n",
    "    for i in fplist:\n",
    "        if i == '(':\n",
    "            currentTree.insertLeft('')\n",
    "            pStack.push(currentTree)\n",
    "            currentTree = currentTree.getLeftChild()\n",
    "        elif i not in ['+', '-', '*', '/', ')']:\n",
    "            currentTree.setRootVal(int(i))\n",
    "            parent = pStack.pop()\n",
    "            currentTree = parent\n",
    "        elif i in ['+','-','*','/']:\n",
    "            currentTree.setRootVal(i)\n",
    "            currentTree.insertRight('')\n",
    "            pStack.push(currentTree)\n",
    "            currentTree = currentTree.getRightChild()\n",
    "        elif i == ')':\n",
    "            currentTree = pStack.pop()\n",
    "        else:\n",
    "            raise ValueError\n",
    "    return eTree\n",
    "            "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$((10+5)*3)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "pt = buildParseTree(\"( ( 10 + 5 ) * 3 )\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As a first example, we will write a function to evaluate the parse tree, returning the numerical result.\n",
    "\n",
    "We can write an algorithm that evaluates a parse tree by recursively evaluating each subtree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img  src=\"meParse (1).png\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img  src=\"meSimple.png\"/>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "code_folding": [
     1
    ],
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import operator\n",
    "def evaluate(parseTree):\n",
    "    opers = {'+':operator.add, '-':operator.sub, '*':operator.mul, '/':operator.truediv}\n",
    "    \n",
    "    leftC = parseTree.getLeftChild()\n",
    "    rightC = parseTree.getRightChild()\n",
    "    \n",
    "    if leftC and rightC:\n",
    "        fn = opers[parseTree.getRootVal()]\n",
    "        return fn(evaluate(leftC),evaluate(rightC))\n",
    "    else: #both children are None\n",
    "        return parseTree.getRootVal()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "45"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "evaluate(pt)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tree Traversals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "There are three commonly used patterns to visit all the nodes in a tree. The difference between these patterns is the order in which each node is visited.\n",
    "\n",
    "1.preorder\n",
    "\n",
    "In a preorder traversal, we visit the root node first, then recursively do a preorder traversal of the left subtree, followed by a recursive preorder traversal of the right subtree.\n",
    "\n",
    "2.inorder\n",
    "\n",
    "In an inorder traversal, we recursively do an inorder traversal on the left subtree, visit the root node, and finally do a recursive inorder traversal of the right subtree.\n",
    "\n",
    "3.postorder\n",
    "\n",
    "In a postorder traversal, we recursively do a postorder traversal of the left subtree and the right subtree followed by a visit to the root node."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img  src=\"booktree.png\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose that you wanted to read this book from front to back. The preorder traversal gives you exactly that ordering."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#preorder as an external function\n",
    "def preorder(tree):\n",
    "    print(tree.getRootVal())\n",
    "    preorder(tree.getLeftChild())\n",
    "    preorder(tree.getRightChild())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def postorder(tree):\n",
    "    postorder(tree.getLeftChild())\n",
    "    postorder(tree.getRightChild())\n",
    "    print(tree.getRootVal())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def inorder(tree):\n",
    "    if tree != None:\n",
    "        inorder(tree.getLeftChild())\n",
    "        print(tree.getRootVal())\n",
    "        inorder(tree.getRightChild())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "+\n",
      "5\n",
      "*\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "inorder(pt)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Priority Queues with Binary Heaps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A priority queue acts like a queue in that you dequeue an item by removing it from the front. However, in a priority queue the logical order of items inside a queue is determined by their priority.\n",
    "\n",
    "The priority queue is a useful data structure for some of the graph algorithms.\n",
    "\n",
    "Inserting into a list is $O(n)$ and sorting a list is $O(nlogn)$. It should be better.\n",
    "\n",
    "The classic way to implement a priority queue is using a data structure called a binary heap. A binary heap will allow us both enqueue and dequeue items in $O(logn)$.\n",
    "\n",
    "The binary heap is interesting to study because when we diagram the heap it looks a lot like a tree, but when we implement it we use only a single list as an internal representation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary Heap Implementation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Structure Property"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In order to guarantee the logarithmic performance, the tree should be balanced.\n",
    "\n",
    "-> complete binary tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another interesting property of a complete tree is that we can represent it using a single list. We do not need to use nodes and references or even lists of lists."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img  src=\"heapOrder.png\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Heap Operations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class BinHeap:\n",
    "    def __init__(self):\n",
    "        self.heapList = [0]\n",
    "        self.currentSize = 0\n",
    "    \n",
    "    def percUp(self,i):\n",
    "    # If the newly added item is less than its parent,\n",
    "    # then we can swap the item with its parent.\n",
    "        while i//2 > 0:\n",
    "            if self.heapList[i] < self.heapList[i//2]:\n",
    "                tmp = self.heapList[i//2]\n",
    "                self.heapList[i//2] = self.heapList[i]\n",
    "                self.heapList[i] = tmp\n",
    "            i = i//2\n",
    "    \n",
    "    def insert(self,k):\n",
    "        self.heapList.append(k)\n",
    "        self.currentSize = self.currentSize + 1\n",
    "        self.percUp(self.currentSize)\n",
    "    \n",
    "    def minChild(self,i):\n",
    "        if i*2 + 1 > self.currentSize:\n",
    "            return i*2\n",
    "        else:\n",
    "            if self.heapList[i*2] < self.heapList[i*2+1]:\n",
    "                return i*2\n",
    "            else:\n",
    "                return i*2 + 1\n",
    "    \n",
    "    def percDown(self,i):\n",
    "        while (i*2) <= self.currentSize:\n",
    "            mc = self.minChild(i)\n",
    "            if self.heapList[i] > self.heapList[mc]:\n",
    "                tmp = self.heapList[i]\n",
    "                self.heapList[i] = self.heapList[mc]\n",
    "                self.heapList[mc] = tmp\n",
    "            i = mc\n",
    "    \n",
    "    def delMin(self):\n",
    "    #The hard part of delMin is restoring full compliance\n",
    "    #with the heap structure and heap order properties\n",
    "    #after the root has been removed.\n",
    "        retval = self.heapList[1]\n",
    "        self.heapList[1] = self.heapList[self.currentSize]\n",
    "        self.currentSize = self.CurrentSize - 1\n",
    "        self.heapList.pop()\n",
    "        self.percDown(1)\n",
    "        return retval\n",
    "    \n",
    "    def buildHeap(self,alist):\n",
    "        #O(n)\n",
    "        i = len(alist)//2\n",
    "        self.currentSize = len(alist)\n",
    "        self.heapList = [0] + alist[:]\n",
    "        while (i>0):\n",
    "            self.percDown(i)\n",
    "            i = i - 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img  src=\"buildheap.png\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Binary Search Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "http://interactivepython.org/runestone/static/pythonds/SortSearch/Hashing.html#implementing-the-map-abstract-data-type\n",
    "\n",
    "\n",
    "Recall that a dictionary is an associative data type where you can store key–data pairs. The key is used to look up the associated data value. We often refer to this idea as a map.\n",
    "\n",
    "Binary search trees is another way to map from a key to a value. In this case we are not interested in the exact placement of items in the tree, but we are interested in using the binary tree structure to provide for efficient searching."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img  src=\"simpleBST.png\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Search Tree Implementation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A binary search tree relies on the property that keys that are less than the parent are found in the left subtree, and keys that are greater than the parent are found in the right subtree. We will call this the bst property."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Because we must be able create and work with a binary search tree that is empty, our implementation will use two classes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "code_folding": [
     0
    ],
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class BinarySearchTree:\n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "        self.size = 0\n",
    "    \n",
    "    def length(self):\n",
    "        return self.size\n",
    "    \n",
    "    def __len__(self):\n",
    "        return self.size\n",
    "    \n",
    "    def __iter__(self):\n",
    "        return self.root.__iter__()\n",
    "    \n",
    "    def put(self,key,val):\n",
    "        if self.root:\n",
    "            self._put(key,val,self.root)\n",
    "        else:\n",
    "            self.root = TreeNode(key,val)\n",
    "        self.size = self.size + 1\n",
    "    \n",
    "    def _put(self,key,val,currentNode):\n",
    "        #helper function\n",
    "        if key < currentNode.key:\n",
    "            if currentNode.hasLeftChild():\n",
    "                self._put(key,val,currentNode.leftChild)\n",
    "            else:\n",
    "                currentNode.leftChild = TreeNode(key,val,parent=currentNode)\n",
    "        #Modefied by me in order to handle with the duplicate key \n",
    "        elif key == currentNode.key:\n",
    "            currentNode.payload = val\n",
    "        else:\n",
    "            if currentNode.hasRightChild():\n",
    "                self._put(key,val,currentNode.rightChild)\n",
    "            else:\n",
    "                currentNode.rightChild = TreeNode(key,val,parent=currentNode)\n",
    "    \n",
    "    def __setitem__(self,k,v):\n",
    "        #allows us to write the statement like \"myZipTree['Plymouth'] = 55446\"\n",
    "        self.put(k,v)\n",
    "    \n",
    "    def get(self,key):\n",
    "        if self.root:\n",
    "            res = self._get(key,self.root)\n",
    "            if res:\n",
    "                return res.payload\n",
    "            else:\n",
    "                return None\n",
    "        return None\n",
    "    \n",
    "    def _get(self,key,currentNode):\n",
    "        if not currentNode:\n",
    "            return None\n",
    "        elif currentNode.key == key:\n",
    "            return currentNode\n",
    "        elif key < currentNode.key:\n",
    "            return self._get(key,currentNode.leftChild)\n",
    "        else:\n",
    "            return self._get(key,currentNode.rightChild)\n",
    "    \n",
    "    def __getitem__(self,key):\n",
    "        return self.get(key)\n",
    "    \n",
    "    def __contains__(self,key):\n",
    "        #overload in operator\n",
    "        if self._get(key,self.root):\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "    \n",
    "    def delete(self,key):\n",
    "        #the most challenging method in the binary search tree\n",
    "        if self.size > 1:\n",
    "            nodeToRemove = self._get(key,self.root)\n",
    "            if nodeToRemove:\n",
    "                self.remove(nodeToRemove)\n",
    "                self.size = self.size - 1\n",
    "            else:\n",
    "                raise KeyError('Error, key not in tree')\n",
    "        elif self.size == 1 and self.root.key == key:\n",
    "            self.root = None\n",
    "            self.size = self.size -1\n",
    "        else:\n",
    "            raise KeyError('Error, key not in tree')\n",
    "    \n",
    "    def __delitem__(self,key):\n",
    "        self.delete(key)\n",
    "    \n",
    "    def remove(self,currentNode):\n",
    "        if currentNode.isLeaf():\n",
    "            if currentNode == currenNode.parent.leftChild:\n",
    "                currentNode.parent.leftChild = None\n",
    "            else:\n",
    "                currentNode.parent.rightChild = None\n",
    "                \n",
    "        elif currenNode.hasBothChildren():\n",
    "            #the most difficult case to handle\n",
    "            succ = currentNode.findSuccessor()\n",
    "            succ.spliceOut()\n",
    "            currentNode.key = succ.key\n",
    "            currentNode.payload = succ.payload\n",
    "        \n",
    "        else:\n",
    "            if currentNode.hasLeftChild():\n",
    "                if currentNode.isLeftChild():\n",
    "                    currentNode.leftChild.parent = currentNode.parent\n",
    "                    currentNode.parent.leftChild = currentNode.leftChild\n",
    "                elif currentNode.isRightChild():\n",
    "                    currentNode.leftChild.parent = currentNode.parent\n",
    "                    currentNode.parent.rightChild = currentNode.leftChild\n",
    "                else:\n",
    "                    currentNode.replaceNodeData(currentNode.leftChild.key,\n",
    "                            currentNode.leftChild.payload,\n",
    "                             currentNode.leftChild.leftChild,\n",
    "                             currentNode.leftChild.rightChild)\n",
    "            else:\n",
    "                if currentNode.isLeftChild():\n",
    "                    currentNode.rightChild.parent = currentNode.parent\n",
    "                    currentNode.parent.leftChild = currentNode.rightChild\n",
    "                elif currentNode.isRightChild():\n",
    "                    currentNode.rightChild.parent = currentNode.parent\n",
    "                    currentNode.parent.rightChild = currentNode.rightChild\n",
    "                else:\n",
    "                    currentNode.replaceNodeData(currentNode.rightChild.key,\n",
    "                             currentNode.rightChild.payload,\n",
    "                             currentNode.rightChild.leftChild,\n",
    "                             currentNode.rightChild.rightChild)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "code_folding": [
     0
    ],
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class TreeNode:\n",
    "    def __init__(self,key,val,left=None,right=None,\n",
    "                                       parent=None):\n",
    "        self.key = key\n",
    "        self.payload = val\n",
    "        self.leftChild = left\n",
    "        self.rightChild = right\n",
    "        self.parent = parent\n",
    "\n",
    "    def hasLeftChild(self):\n",
    "        return self.leftChild\n",
    "\n",
    "    def hasRightChild(self):\n",
    "        return self.rightChild\n",
    "\n",
    "    def isLeftChild(self):\n",
    "        return self.parent and self.parent.leftChild == self\n",
    "\n",
    "    def isRightChild(self):\n",
    "        return self.parent and self.parent.rightChild == self\n",
    "\n",
    "    def isRoot(self):\n",
    "        return not self.parent\n",
    "\n",
    "    def isLeaf(self):\n",
    "        return not (self.rightChild or self.leftChild)\n",
    "\n",
    "    def hasAnyChildren(self):\n",
    "        return self.rightChild or self.leftChild\n",
    "\n",
    "    def hasBothChildren(self):\n",
    "        return self.rightChild and self.leftChild\n",
    "\n",
    "    def replaceNodeData(self,key,value,lc,rc):\n",
    "        self.key = key\n",
    "        self.payload = value\n",
    "        self.leftChild = lc\n",
    "        self.rightChild = rc\n",
    "        if self.hasLeftChild():\n",
    "            self.leftChild.parent = self\n",
    "        if self.hasRightChild():\n",
    "            self.rightChild.parent = self\n",
    "    def findSuccessor(self):\n",
    "        succ = None\n",
    "        if self.rightChild():\n",
    "            #the node has a right child\n",
    "            succ = self.rightChild.findMin()\n",
    "            #the successor is to be the smallest in the right subtree\n",
    "        else:\n",
    "            #the node doesn't have a right child\n",
    "            #In deleting the node, this case never happans(?)\n",
    "            if self.parent:\n",
    "                if self.isLeftChild():\n",
    "                    succ = self.parent\n",
    "                else:\n",
    "                    self.parent.rightChild = None\n",
    "                    succ = self.parent.findSuccessor()\n",
    "                    self.parent.rightChild = self\n",
    "        return succ\n",
    "    \n",
    "    def findMin(self):\n",
    "        current = self\n",
    "        while current.hasLeftChild():\n",
    "            current = current.leftChild\n",
    "        return current\n",
    "    \n",
    "    def spliceOut(self):\n",
    "        if self.isLeaf():\n",
    "            if self.isLeftChild():\n",
    "                   self.parent.leftChild = None\n",
    "            else:\n",
    "                   self.parent.rightChild = None\n",
    "        elif self.hasAnyChildren():\n",
    "            if self.hasLeftChild():\n",
    "                if self.isLeftChild():\n",
    "                    #Is it correct? What if there is also a right child?\n",
    "                        self.parent.leftChild = self.leftChild\n",
    "                else:\n",
    "                        self.parent.rightChild = self.leftChild\n",
    "                self.leftChild.parent = self.parent\n",
    "            else:\n",
    "                if self.isLeftChild():\n",
    "                        self.parent.leftChild = self.rightChild\n",
    "                else:\n",
    "                        self.parent.rightChild = self.rightChild\n",
    "                self.rightChild.parent = self.parent\n",
    "    \n",
    "    def __iter__(self):\n",
    "        #???\n",
    "        if self:\n",
    "            if self.hasLeftChild():\n",
    "                for elem in self.leftChild:\n",
    "                    yield elem\n",
    "            yield self.key\n",
    "            if self.hasRightChild():\n",
    "                for elem in self.rightChild:\n",
    "                    yield elem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img  src=\"bstdel3.png\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Writing an iterator requires a bit more work, since an iterator should return only one node each time the iterator is called.\n",
    "\n",
    "Python provides us with a very powerful function to use when creating an iterator. The function is called yield."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "mytree = BinarySearchTree()\n",
    "mytree[3] = \"red\"\n",
    "mytree[4] = \"blue\"\n",
    "mytree[6] = \"yellow\"\n",
    "mytree[2] = \"at\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'yellow'"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mytree[6]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Balanced Binary Search Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "a special kind of binary search tree that automatically makes sure that the tree remains balanced at all times\n",
    "\n",
    "This tree is called an AVL tree and is named for its inventors: G.M. Adelson-Velskii and E.M. Landis\n",
    "\n",
    "$$balanceFactor=height(leftSubTree)−height(rightSubTree)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img  src=\"unbalanced.png\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## AVL Tree Performance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "by ensuring that a tree always has a balance factor of -1, 0, or 1 we can get better Big-O performance of key operations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img  src=\"worstAVL.png\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$N_h$: the number of nodes whose height is h\n",
    "$$N_h = 1 + N_{h-1} + N_{h-2}$$\n",
    "\n",
    "By thinking of the similarity to Fibonacci sequence, we can show that searching AVL tree is limited to $O(\\log N)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## AVL Tree Implementation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "augment the procudure to insert a new key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def _put(self,key,val,currentNode):\n",
    "    if key < currentNode.key:\n",
    "        if currentNode.hasLeftChild():\n",
    "            self._put(key,val,currentNode.leftChild)\n",
    "        else:\n",
    "            currentNode.leftChild = TreeNode(key,val,parent=currentNode)\n",
    "            self.updateBalance(currentNode.leftChild)\n",
    "    else:\n",
    "        if currentNode.hasRightChild():\n",
    "            self._put(key,val,currentNode.rightChild)\n",
    "        else:\n",
    "            currentNode.rightChild = TreeNode(key,val,parent=currentNode)\n",
    "            self.updateBalance(currentNode.rightChild)\n",
    "\n",
    "def updateBalance(self,node):\n",
    "    if node.balanceFactor > 1 or node.balanceFactor < -1:\n",
    "        self.rebalance(node)\n",
    "        return\n",
    "    if node.parent != None:\n",
    "        if node.isLeftChild():\n",
    "            node.parent.balanceFactor += 1\n",
    "        elif node.isRightChild():\n",
    "            node.parent.balanceFactor -= 1\n",
    "\n",
    "        if node.parent.balanceFactor != 0:\n",
    "            self.updateBalance(node.parent)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Efficient rebalancing is the key to making the AVL Tree work well without sacrificing performance. In order to bring an AVL Tree back into balance we will perform one or more rotations on the tree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Summary of Map ADT Implementations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img  src=\"Screen Shot 2016-04-07 at 2.01.13 PM.png\"/>"
   ]
  }
 ],
 "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.4.3"
  },
  "toc": {
   "toc_cell": true,
   "toc_number_sections": true,
   "toc_threshold": 6,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}