Modulabs presentation about binary search tree 20180618

binary_search_tree.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Binary Search Tree\n",
    "\n",
    "### refrence\n",
    "- [2018_Spring_IE260] 데이터 구조 및 분석 KAIST 문일철 교수\n",
    "- cf.[visualization of BST - usfca](https://www.cs.usfca.edu/~galles/visualization/BST.html)\n",
    "\n",
    "## Keyword\n",
    "- ADT\n",
    "- Tree\n",
    "  - Insert\n",
    "  - Delete\n",
    "  - Traverse\n",
    "- BinarySearch\n",
    "  - Heap - OS - Memory - Process\n",
    "  - Decesion Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Detour - Data Structure?\n",
    "- program 실행\n",
    "  - 메인 Memory에 데이터 로드(load) - exe - input\n",
    "- 변수는 그릇\n",
    "- 그릇의 모양 - 자료구조\n",
    "- 적절한 그릇type을 찾는 일 \n",
    "  -  동화 '두루미와 여우' \n",
    "  - 현실문제 - 검색 서비스 \n",
    "- **자료구조에 대한 이해**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Detour - ADT\n",
    "### ADT? \n",
    "- An abstract data type (ADT) is an abstraction of a data structure\n",
    "\n",
    "### An ADT specifies:\n",
    "- Data stored\n",
    "- Operations on the data\n",
    "- Error conditions associated with operations\n",
    "- [Algorithm complexities](http://bigocheatsheet.com)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Example\n",
    "- Example: ADT modeling a simple stock trading system\n",
    "- The data stored are buy/sell orders\n",
    "- The operations supported are\n",
    "  - order buy(stock, shares, price)\n",
    "  - order sell(stock, shares, price)\n",
    "- void cancel(order)\n",
    "- Error conditions:\n",
    "  - Buy/sell a nonexistent stock\n",
    "  - Cancel a nonexistent order"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Tree\n",
    "\n",
    "### Tree?\n",
    "- 네, 우리가 아는 그 나무 구조\n",
    "\n",
    "#### Operations\n",
    "- Ordinary data structure operations just as linked  lists\n",
    "- Insert\n",
    "- Delete\n",
    "- Search\n",
    "- Traverse (Special searching approaches for trees and networks)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Why tree?\n",
    "- 현실세계에서 쓰이는 구조와 닯음(조직도, 혈통)\n",
    "- Divide and Conquer!\n",
    "  - 이쪽에는 어떤 특정 속성을 가지는 데이터만 가지고 있음. 양 쪽이 섞이지 않음\n",
    "  - remind\n",
    "    - Divide and Conquer = smallsize 로 줄여나감\n",
    "    - 배열 모든 원소들의 합 구하기\n",
    "\n",
    "### When?\n",
    "- Binary Search\n",
    "- Heap\n",
    "- DescisonTree\n",
    "  - [Tree 실습코드](http://kooc.kaist.ac.kr/datastructure-2018s/lecture/25014/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Terminologies of tree structure\n",
    "- 기본 용어 : root, edge, node \n",
    "- 관계에 따라\n",
    "  - Parents - Child\n",
    "  - siblings\n",
    "  - Descendants of A(올라가다보면 만남)\n",
    "  - Ancestors of E = A,B\n",
    "- 위치에 따라\n",
    " - Leaves[Terminal Nodes]\n",
    " - Internal Nodes\n",
    "\n",
    "- **중요** Path to E Root에서 특정 노드(E)까지 최단거리\n",
    "  - Depth and level of B = 1 (Root에서 B까지 Path의 길이)\n",
    "- Height of Tree = 2 = Leaf까지의 path\n",
    "- Degree of B = 4 = B 가 가지는 childe의 수\n",
    "- tree size = node 의 갯수 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "- 모양에 따라\n",
    "  - Full tree \n",
    "    - 꽉 찬 삼각형! \n",
    "    - Leaf 꽉 차있음\n",
    "  - complete tree \n",
    "    - 바로 직전 depth까지는 Full tree \n",
    "   - Filled from left 왼쪽에서 오른쪽으로 채워나가는 과정이면 complete tree "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "###  Characteristics of Tree (수식으로)\n",
    "- edge갯수는 node 의 갯수만큼? -> reference 되는 node 갯수만큼 -> Root는 reference 안되는 node => num of nodes -1\n",
    "- Depth of root = 0 \n",
    "- Height of root = height of tree\n",
    "- Maximum num of nodes at level i with degree d = d^i \n",
    "- Maximum num of leaves with height h and degree d = d^h\n",
    "- Maximum size of a tree with height h and degree d = 1 + d + d^2+...+d^h = (d^h+1 - 1)/d-1\n",
    "- Height of a complete tree with size s and degree d\n",
    "h = r log d s(d-1)+1 ㄱ - 1\n",
    "```\n",
    "s = (d^(h+1) -1) / (d-1)\n",
    "s(d-1) = d^(h+1)\n",
    "s(d-1) + 1 = d^(h+1)\n",
    "log d (s(d-1)+1) = h + 1\n",
    "h = r log d s(d-1)+1 ㄱ - 1 #올림\n",
    "```\n",
    "s = 16 , d= 4 then h = 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Binary Search Tree and Implementation\n",
    "**How to perform a faster search? 빠른 검색!**\n",
    "- 이진탐색 - 소주병뚜껑 숫자 맞추기 게임\n",
    "- Implementation of tree node : 05:13\n",
    "- Root 에 대한 reference만 저장해 놓음\n",
    "- tree는 root에 대한 access만 가짐"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Implementation of Binary Search Tree (python3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Insert operation\n",
    "#### checkPoint\n",
    "- Divide and Conquer - recursion - reduce problem(scale)\n",
    "- 우리가 지켜야할 규칙 : parent 보다 작은 값은 왼쪽 node로 큰 값은 오른쪽 node로 insert 한다\n",
    "- 중복값 보관하지 않아요\n",
    "- recursion\n",
    "\n",
    "#### Action \n",
    "- Insert 3,2,0,5,7,4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def insert(self, value, node = ''):\n",
    "    if root = '':\n",
    "        node = self.root\n",
    "    if self.root == '':\n",
    "        self.root = TreeNode(value, '') #3\n",
    "        return\n",
    "    if value == node.getValue():\n",
    "        if node.getRHS() == '':\n",
    "            node.setRHS(TreeNode(value,node))\n",
    "        else:\n",
    "            self.insert(value,node.getRHS())\n",
    "    if value < node.getValue():\n",
    "        if node.getRHS() == '':\n",
    "            node.setLHS(TreeNode(value,node))\n",
    "        else:\n",
    "            self.insert(value, node.getLHS())\n",
    "    return"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Search Operation\n",
    "#### checkPoint\n",
    "- 다른 쪽은 찾을 필요없어요\n",
    "- compare to LinkedList search\n",
    "- Tree height , Maximum depth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def search(self,value,node = ''):\n",
    "    if node == '':\n",
    "        node = self.root\n",
    "    if value == node.getValue():\n",
    "        return True\n",
    "    if value > node.getValue():\n",
    "        if node.getRHS() == '':\n",
    "            return False\n",
    "        else:\n",
    "            return self.search(value,node.getRHS())\n",
    "    if value < node.getValue():\n",
    "        if node.getLHS() == '':\n",
    "            return False\n",
    "        else:\n",
    "            return self.search(value,node.getLHS())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Delete Operation\n",
    "#### check point\n",
    "- 쉽지 않아요. delete하면 tree 구조에 생기는 여파\n",
    "- No children , one child, two children"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Action\n",
    "- Insert 3,2,0,5,7,4\n",
    "- case by case, step by step\n",
    "- No children -> one child -> two children(3)\n",
    "\n",
    "##### No children -> one child -> two children\n",
    "- garbage reference, None\n",
    "\n",
    "##### one child\n",
    "- referencing only child\n",
    "- GC\n",
    "\n",
    "##### two children\n",
    "- Two Result\n",
    "- sol. Insert[move] other node (Keep the Rules)\n",
    "- LHS Maximum, RHS Minimum (think Replace '5')\n",
    "  - Minimum? Go to LeftSide!\n",
    "  - Maximum? Go to RightSide!\n",
    "- First of All, Just Copy the node (LHS max or RHS min)\n",
    "- delete copied node\n",
    "  - copied node has zero or One Child"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def delete(self, value, node = ''):\n",
    "    if node == '':\n",
    "        node = self.root\n",
    "    if node.getValue() < value:\n",
    "        return self.delete(value, node.getRHS())\n",
    "    if node.getValue() > value:\n",
    "        return self.delete(value, node.getLHS())\n",
    "    if node.getValue() == value:\n",
    "        #  two children\n",
    "        if node.getLHS() != '' and node.getRHS() != '':\n",
    "            nodeMin = self.findMin(node.getRHS())\n",
    "            node.setValue(nodeMin.getValue()) #copy\n",
    "            self.delete(nodeMin.getValue(), node.getRHS())\n",
    "            return\n",
    "        parent = node.getParent()\n",
    "        # one child\n",
    "        if node.getLHS() != '':\n",
    "            if node == self.root:\n",
    "                self.root = node.getLHS()\n",
    "            elif parent.getLHS() == node:\n",
    "                parent.setLHS(node.getLHS())\n",
    "                node.getLHS().setParent(parent)\n",
    "            else:\n",
    "                parent.setRHS(node.getLHS())\n",
    "                node.getLHS().setParent(parent)\n",
    "            return\n",
    "        if node.getRHS() != '':\n",
    "            if node == self.root:\n",
    "                self.root = node.getRHS()\n",
    "            elif parent.getLHS() == node:\n",
    "                parent.setLHS(node.getRHS())\n",
    "                node.getRHS().setParent(parent)\n",
    "            else:\n",
    "                parent.setRHS(node.getRHS())\n",
    "                node.getRHS().setParent(parent)\n",
    "            return\n",
    "        #no child\n",
    "        if node == self.root:\n",
    "            self.root = ''\n",
    "        elif parent.getLHS() == node:\n",
    "            parent.setLHS('')\n",
    "        else:\n",
    "            parent.setRHS('')\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def findMax(self, node = ''):\n",
    "    if node == '':\n",
    "        node = self.root\n",
    "    if node.getRHS() == '':\n",
    "        return node\n",
    "    return self.findMax(node.getRHS())\n",
    "\n",
    "def findMin(self,node = ''):\n",
    "    if node == '':\n",
    "        node = self.root\n",
    "    if node.getLHS() == '':\n",
    "        return node\n",
    "    return self.findMin(node.getLHS())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Traversing\n",
    "- Tree, Graph\n",
    "- Think print dataStructure\n",
    "  - Linked List\n",
    "  - BST\n",
    "- Hence there are multiple traversing approches\n",
    "\n",
    "### More\n",
    "- why Traversing? \n",
    "- Why use diffrent type of Traversing?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Depth First Traverse\n",
    "- 3 ways (LHS, RHS, current)\n",
    "- 'Pre-order', 'In-order', 'Post-order'\n",
    "- Action : 3,2,0,1,5,4,7,6,9,8\n",
    "- recurssion - stack frame\n",
    "\n",
    "#### Pre-order traverse\n",
    "- current : Pre order\n",
    "- Order: Current, LHS, RHS in Recursion\n",
    "  - (3, 2, 0, 1, 5, 4, 7, 6, 9, 8)\n",
    "\n",
    "#### In-order traverse\n",
    "- current : In\n",
    "- Order: LHS, Current, RHS in Recursion\n",
    "  - (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)\n",
    "\n",
    "#### Post-order traverse\n",
    "- current : post\n",
    "- Order: LHS, RHS, Current in Recursion\n",
    "  - (1, 0, 2, 4, 6, 8, 9, 7, 5, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def traverseInOrder(self, node = ''):\n",
    "    if node == '':\n",
    "        node = self.root\n",
    "    ret = []\n",
    "    if node.getLHS() != '':\n",
    "        ret = ret + self.traverseInOrder(node.getLHS())\n",
    "    ret.append(node.getValue())\n",
    "    if node.getRHS() != '':\n",
    "        ret = ret + self.traverseInOrder(node.getRHS())\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def traversePreOrder(self, node = ''):\n",
    "    if node == '':\n",
    "        node = self.root\n",
    "    ret = []\n",
    "    ret.append(node.getValue())\n",
    "    if node.getLHS() != '':\n",
    "        ret = ret + self.traversePreOrder(node.getLHS())\n",
    "    if node.getRHS() != '':\n",
    "        ret = ret + self.traversePreOrder(node.getRHS())\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def traversePostOrder(self, node = ''):\n",
    "    if node == '':\n",
    "        node = self.root\n",
    "    ret = []\n",
    "    if node.getLHS() != '':\n",
    "        ret = ret + self.traversePostOrder(node.getLHS())\n",
    "    if node.getRHS() != '':\n",
    "        ret = ret + self.traversePostOrder(node.getRHS())\n",
    "    ret.append(node.getValue())\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Breadth First Traverse\n",
    "- Queue-based **level-order** traverse\n",
    "- Action : 3,2,5,0,4,7,1,6,9,8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def traverseLevelOrder(self):\n",
    "    ret = []\n",
    "    Q = Queue()\n",
    "    Q.enqueue(self.root)\n",
    "    while Q.isEmpty() == False:\n",
    "        node = Q.dequeue()\n",
    "        if node == '':\n",
    "            continue\n",
    "        ret.append(node.getValue())\n",
    "        if node.getLHS() != '':\n",
    "            Q.enqueue(node.getLHS())\n",
    "        if node.getRHS() != '':\n",
    "            Q.enqueue(node.getRHS())\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Performance of Binary Search tree\n",
    "- [Algorithm complexities](http://bigocheatsheet.com)\n",
    "- Skewed Binary Tree vs complete Binary Tree\n",
    "- Height!"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "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.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}