algorithm_ch4_binarySearchTree.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Node 정의\n",
    "\n",
    "이진 검색트리의 Node는 다음과 같은 멤버 변수를 갖는다\n",
    "* parent: 노드의 parent node의 레퍼런스, parent가 None이면, root node로 간주한다.\n",
    "* left  : 노드의 왼쪽 child node의 레퍼런스\n",
    "* right : 노드의 오른쪽 child node의 레퍼런스\n",
    "* key   : 검색 키 값\n",
    "\n",
    "또한, 레드블랙트리를 지원하기 위하여 다음과 같은 멤버 변수를 가질 수 있다.\n",
    "* color : 블랙=1, 레드=0\n",
    "* nullNode : 레드블랙트리의 leaf node의 child node는 NULL 이 아니라 특별히 정의된 공백 노드의 레퍼런스이다. nullNode의 값이 1이면, 공백 노드를 의미한다. 공백 노드는 블랙 노드이며, 두 child는 모두 None이다.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, key, nullNode=0):\n",
    "        self.parent = None\n",
    "        self.key = key\n",
    "        self.left = None    #None or empty leaf node for red black tree\n",
    "        self.right = None   \n",
    "        \n",
    "        #these items are for a red black tree\n",
    "        self.color = 0      #black(1), red(0)\n",
    "        self.nullNode = nullNode #if it is 1, it means a Null leaf node of a red black tree\n",
    "    \n",
    "    def addChild(self, leftOrRight, childNode):\n",
    "        \n",
    "        if leftOrRight == 0: #left child\n",
    "            self.left = childNode \n",
    "            childNode.parent = self\n",
    "            \n",
    "        elif leftOrRight == 1: #right child            \n",
    "            self.right = childNode \n",
    "            childNode.parent = self\n",
    "\n",
    "        else :\n",
    "            return 1\n",
    "        return 0\n",
    "    \n",
    "    \n",
    "    def readKey(self):\n",
    "        return self.key\n",
    "    \n",
    "    def writeKey(self, key):\n",
    "        self.key = key\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## BST의 노드 검색\n",
    "\n",
    "주어진 node를 root로 하는 이진 검색트리에서 key값을 갖는 노드를 검색하여 리턴한다.\n",
    "* result = 0 이면, key 값을 갖는 노드를 찾음\n",
    "* result = 1 이면, key 값을 갖는 노드를 찾을 수 없음"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binarySearchTreeFindNode(node: Node, key) :\n",
    "    \n",
    "    if node == None or key == None:\n",
    "        return 1, None\n",
    "    \n",
    "    if node.key == key:\n",
    "        result = 0    \n",
    "    elif node.key < key :\n",
    "        result, node = binarySearchTreeFindNode(node.right, key)\n",
    "    else :\n",
    "        result, node = binarySearchTreeFindNode(node.left, key)\n",
    "            \n",
    "    return result, node"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " ## BST에서 새로운 노드 추가\n",
    " \n",
    "root와 key 값이 주어지면, 주어진 key 값을 갖는 새로운 노드를 생성하여 root를 참조하여 트리에 새로운 노드를 삽입한다.\n",
    "treeType은 레드블랙트리를 지원하기 위한 파라메타로, treeType=1이면, 레드블랙트리에 노드를 삽입하기 위해 함수가 호출되었음을 의미한다.\n",
    "\n",
    "root가 None이면, 트리를 새로 생성하는 것으로 간주하고 root를 생성한 후 종료한다.\n",
    "\n",
    "root가 None이 아니면, key 값을 참조하여 적절한 leaf를 찾아 노드를 삽입한다.\n",
    "\n",
    "함수 호출 후, result = 0 이 리턴되면 정상종료된 것을 의미하며, 0 보다 큰 값이 리턴되면 오류가 발생한 것으로 간주한다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def _binarySearchTreeInsertNode(parent: Node, key, treeType) -> (int, Node):    \n",
    "     \n",
    "    if parent == None or parent.nullNode == 1:  # if nullNode==1, it is a empty leaf node for red black tree\n",
    "        return 1, None\n",
    "    \n",
    "    # to check whether input type of 'parent' is Node\n",
    "    # if isinstance(parent,Node) == False:\n",
    "    #    return 2, None    \n",
    "    \n",
    "    node=None\n",
    "    \n",
    "    if key < parent.key:\n",
    "        result, node =  _binarySearchTreeInsertNode(parent.left, key, treeType)\n",
    "        if result == 1:\n",
    "            node = Node(key)\n",
    "            parent.addChild(0, node) #add a left child to a parent node\n",
    "            \n",
    "    else:\n",
    "        result, node =  _binarySearchTreeInsertNode(parent.right, key, treeType)\n",
    "        if result == 1:\n",
    "            node = Node(key)\n",
    "            parent.addChild(1, node) #add a right child to a parent node\n",
    "    \n",
    "    #if a tree is a red black tree, a leaf node is an empty leaf node, not a node which does not any child node\n",
    "    if treeType == 1:\n",
    "        emptyNode_left = Node(0,1)  #key is 0 and nullNode is 1\n",
    "        emptyNode_left.parent=node\n",
    "        emptyNode_left.color=1\n",
    "        emptyNode_right = Node(0,1)\n",
    "        emptyNode_right.parent=node\n",
    "        emptyNode_right.color=1\n",
    "            \n",
    "        node.left = emptyNode_left\n",
    "        node.right = emptyNode_right        \n",
    "            \n",
    "    return 0, node\n",
    "\n",
    "\n",
    "def binarySearchTreeInsertNode(root: Node, key, treeType=0) -> (int, Node):  \n",
    "    \n",
    "    if root == None: #generate a root\n",
    "        node = Node(key, 0)  \n",
    "        if treeType == 1:\n",
    "            emptyNode_left = Node(0,1) #key is 0 and nullNode is 1\n",
    "            emptyNode_left.parent=node\n",
    "            emptyNode_left.color=1\n",
    "            emptyNode_right = Node(0,1)\n",
    "            emptyNode_right.parent=node\n",
    "            emptyNode_right.color=1\n",
    "            \n",
    "            node.color = 1  #a root is a black node\n",
    "            node.left = emptyNode_left\n",
    "            node.right = emptyNode_right \n",
    "            \n",
    "        return 0, node\n",
    "    else:\n",
    "        result, node = _binarySearchTreeInsertNode(root, key, treeType)\n",
    "        return result, node \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## BST에서 노드 삭제\n",
    "\n",
    "주어진 키 값을 이용하여 노드를 탐색한 후, 탐색된 노드를 삭제한다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def _deleteNode(node):\n",
    "    if node.left == None and node.right == None:\n",
    "        return None\n",
    "    \n",
    "    elif node.left != None and node.right == None:\n",
    "        return node.left\n",
    "    \n",
    "    elif node.left == None and node.right != None:\n",
    "        return node.right\n",
    "    \n",
    "    else:\n",
    "        target = node.right \n",
    "        while target.left != None:\n",
    "            parent = target\n",
    "            target = target.left\n",
    "        \n",
    "        #delete target\n",
    "        node.key = target.key\n",
    "        \n",
    "        if target == node.right:\n",
    "            node.right = target.right\n",
    "        else:\n",
    "            parent.right = target.right\n",
    "        return node \n",
    "\n",
    "# it finds a node with removeNode.key and then remove the node from tree with the root    \n",
    "def binarySearchTreeDeleteNode(root:Node, key):\n",
    "    \n",
    "    result, removeNode = binarySearchTreeFindNode(root, key)\n",
    "    \n",
    "    if result == 0:\n",
    "        if removeNode.key == root.key:\n",
    "            root = _deleteNode(removeNode)\n",
    "            \n",
    "        elif removeNode.parent.left != None and removeNode.parent.left.key == removeNode.key :\n",
    "            removeNode.parent.left = _deleteNode(removeNode)\n",
    "        \n",
    "        else:\n",
    "            removeNode.parent.right = _deleteNode(removeNode)\n",
    "    \n",
    "    return result, removeNode, root"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## BST Test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "result, root=binarySearchTreeInsertNode(None,2)\n",
    "result, node=binarySearchTreeInsertNode(root,4)\n",
    "result, node=binarySearchTreeInsertNode(root,5)\n",
    "result, node=binarySearchTreeInsertNode(root,1)\n",
    "print(root)\n",
    "node = binarySearchTreeFindNode(root, 5)\n",
    "print(node)\n",
    "result, remove, root = binarySearchTreeDeleteNode(root, 2)\n",
    "print(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## red black tree for BTS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "##################################################\n",
    "# redBlackTree \n",
    "##################################################\n",
    "\n",
    "# node를 중심으로 쪽으로 회전한다.\n",
    "# 함수가 None이 아닌 객체 return 하면, 루트노드가 변경된 것이므로 해당 함수를 호출한\n",
    "# 해당 함수를 호출한 함수가 이를 적절히 반영해서 처리해야 한다.\n",
    "# temp = redBlackTreeInsertNodeLeftTurn(node)\n",
    "# if temp != None: root = temp\n",
    "\n",
    "def redBlackTreeInsertNodeLeftTurn(node: Node):\n",
    "    #node를 중심으로 왼쪽으로 회전\n",
    "    \n",
    "    if node.parent != None:  #if node is not a root node\n",
    "        if node.parent.right == node:\n",
    "            node.parent.right = node.right\n",
    "        else:\n",
    "            node.parent.left = node.right\n",
    "    \n",
    "    node.right.parent = node.parent\n",
    "    \n",
    "    temp = node.right.left\n",
    "    node.right.left = node\n",
    "    node.parent = node.right\n",
    "    \n",
    "    temp.parent = node\n",
    "    node.right = temp  \n",
    "    \n",
    "    root = None\n",
    "    if node.parent.parent == None:  #if node.parent becomes a root\n",
    "        root=node.parent\n",
    "        \n",
    "    return root\n",
    "\n",
    "\n",
    "# node를 중심으로 오른쪽으로 회전한다.\n",
    "# 함수가 None이 아닌 객체 return 하면, 루트노드가 변경된 것이므로 해당 함수를 호출한\n",
    "# 해당 함수를 호출한 함수가 이를 적절히 반영해서 처리해야 한다.\n",
    "# temp = redBlackTreeInsertNodeRightTurn(node)\n",
    "# if temp != None: root = temp\n",
    "\n",
    "def redBlackTreeInsertNodeRightTurn(node: Node):\n",
    "    \n",
    "    if node.parent != None:   #if node is not a root node,\n",
    "        if node.parent.right == node:\n",
    "            node.parent.right = node.left\n",
    "        else:\n",
    "            node.parent.left = node.left\n",
    "    \n",
    "    #node가 root 노드라 해도 아래 절차는 문제 되지 않는다.        \n",
    "    node.left.parent = node.parent    \n",
    "    \n",
    "    temp = node.left.right\n",
    "    node.left.right = node\n",
    "    node.parent = node.left\n",
    "    \n",
    "    temp.parent = node\n",
    "    node.left = temp\n",
    "    \n",
    "    root = None\n",
    "    if node.parent.parent == None:  #if node.parent becomes a root\n",
    "        root=node.parent\n",
    "        \n",
    "    return root\n",
    "\n",
    "\n",
    "# redBlackTree에 노드 삽입을 위한 함수 SET\n",
    "#     (1) redBlackTreeInsertNodeCheckColor\n",
    "#     (2) redBlackTreeGenerateEmptyLeafNode\n",
    "#     (3) redBlackTreeInsertNode\n",
    "def redBlackTreeInsertNodeCheckColor(node:Node, root:Node):\n",
    "    \n",
    "    if node.parent == None or node == root: #the node is a root\n",
    "        return 0, root\n",
    "    \n",
    "    if node.parent.parent == None: #if the depth of node is 2 (root is of depth 1)\n",
    "        node.color = 0 # red \n",
    "        return 0, root\n",
    "    \n",
    "    if node.parent.color == 1: # the parent node of a new node is black\n",
    "        return 0, root    \n",
    "    else:        \n",
    "        if node.parent.parent.left == node.parent:\n",
    "            sibling = node.parent.parent.right\n",
    "        else:\n",
    "            sibling = node.parent.parent.left   \n",
    "\n",
    "        if sibling.color == 0 : # sibling is red  case 1\n",
    "            node.parent.color = 1               #black\n",
    "            sibling.color = 1                   #black\n",
    "            node.parent.parent.color = 0        #red\n",
    "            if node.parent.parent.parent == None:\n",
    "                node.parent.parent.color = 1    #black\n",
    "            else:\n",
    "                if node.parent.parent.parent.color == 0: #red\n",
    "                    result, root = redBlackTreeInsertNodeCheckColor(node.parent.parent, root)\n",
    "        else:                   # sibling is black\n",
    "            # 교과서의 경우보다 더 세분화 해서 경우를 나눠야 한다.\n",
    "            # p2의 오른쪽/왼쪽 child인지 부터 나눠서 구현해야 한다.\n",
    "            if node.parent.parent.right == node.parent:\n",
    "                if node.parent.left == node:           #case 2-1\n",
    "                    temp=redBlackTreeInsertNodeRightTurn(node.parent)                 \n",
    "                    node = node.right  #case 2-2 상황에서의 node로 설정\n",
    "                     \n",
    "                #case 2-2\n",
    "                temp = redBlackTreeInsertNodeLeftTurn(node.parent.parent)\n",
    "                node.parent.color, node.parent.left.color = node.parent.left.color, node.parent.color\n",
    "            \n",
    "                \n",
    "            else: #node.parent.parent.left == node.parent 인 경\n",
    "                if node.parent.right == node:           #case 2-1\n",
    "                    temp=redBlackTreeInsertNodeLeftTurn(node.parent)                 \n",
    "                    node = node.left  #case 2-2 상황에서의 node로 설정\n",
    "                     \n",
    "                #case 2-2\n",
    "                temp = redBlackTreeInsertNodeRightTurn(node.parent.parent)\n",
    "                node.parent.color, node.parent.right.color = node.parent.right.color, node.parent.color\n",
    "                \n",
    "            if temp != None:\n",
    "                root = temp    \n",
    "    return 1, root\n",
    "\n",
    "   \n",
    "def redBlackTreeInsertNode(root: Node, key):\n",
    "    \n",
    "    if __name__==\"__main__\": print(\"insert node with key %d\"%key)\n",
    "    \n",
    "    if root == None:\n",
    "        result, root = binarySearchTreeInsertNode(root, key, 1)\n",
    "        return 0, None, root\n",
    "    \n",
    "    result, node = binarySearchTreeInsertNode(root, key, 1)\n",
    "    \n",
    "    if result > 0 :\n",
    "        return result, None\n",
    "    \n",
    "    if node.parent != None : # the node is not a root node\n",
    "\n",
    "        node.color = 0 #red   \n",
    "        result, root = redBlackTreeInsertNodeCheckColor(node, root)\n",
    "    \n",
    "    return 0, node, root\n",
    "\n",
    "\n",
    "\n",
    "# 주의: 노드 삭제는 child가 하나 이하인 경우만을 고려한다.\n",
    "# 함수의 입력변수 node_x는 노드가 삭제되고, 새로 parent에 연결된 노드를 의미한다.\n",
    "# 특히, 이 함수는 node_x를 기준으로 블랙의 수가 1개 부족한 경우를 처리하기 위해 호출한다.\n",
    "def redBlackTreeDeleteNodeCheckColor(node_x:Node, root:Node):\n",
    "    \n",
    "    if node_x == None or root == None:\n",
    "        return 1, None\n",
    "    \n",
    "    if node_x.parent == None: # 삭제된 노드를 대신하여 새로 연결된 노드가 루트가  경우\n",
    "        node_x.color = 1\n",
    "        return 0, node_x\n",
    "    \n",
    "    temp = None\n",
    "    result = 0\n",
    "    \n",
    "    parent = node_x.parent\n",
    "    #get sibling of deleted node\n",
    "    if parent.right == node_x:\n",
    "        sibling = parent.left\n",
    "    else:\n",
    "        sibling = parent.right\n",
    "    \n",
    "    #case1-1: p, s, l, r = 0, 1, 1, 1        \n",
    "    if parent.color == 0 and sibling.left.color == 1 and sibling.right.color == 1:\n",
    "        #p is red  and s is black\n",
    "        parent.color = 1\n",
    "        sibling.color = 0\n",
    "        \n",
    "    #case *-2: (주의) sibling 이 parent의 왼쪽 또는 오른쪽 노드인지를 구분하여 처리해야 한다.\n",
    "    elif parent.right == sibling and sibling.right.color == 0:\n",
    "        # parent를 중심으로 왼쪽으로 회전 \n",
    "        temp = redBlackTreeInsertNodeLeftTurn(parent)\n",
    "        parent.color, sibling.color = sibling.color, parent.color\n",
    "        sibling.right.color = 1\n",
    "    elif parent.left == sibling and sibling.left.color == 0:\n",
    "        # parent를 중심으로 오른쪽으로 회전\n",
    "        temp = redBlackTreeInsertNodeRightTurn(parent) \n",
    "        parent.color, sibling.color = sibling.color, parent.color\n",
    "        sibling.left.color = 1 \n",
    "            \n",
    "    \n",
    "    #case *-3: (주의) sibling 이 parent의 왼쪽 또는 오른쪽 노드인지를 구분하여 처리해야 한다.\n",
    "    # sibling 과 parent 사이에 노드가 회전하면서 끼어든다. 그러므로 회전으로 루트가 변경되지는 않는다.   \n",
    "    elif parent.right== sibling and sibling.left.color == 0 and sibling.right.color == 1:\n",
    "        temp = redBlackTreeInsertNodeRightTurn(sibling)\n",
    "        sibling.parent.color, sibling.color = sibling.color, sibling.parent.color\n",
    "        # case *-2\n",
    "        redBlackTreeDeleteNodeCheckColor(node_x, root)\n",
    "    elif parent.left== sibling and sibling.left.color == 1 and sibling.right.color == 0:\n",
    "        temp = redBlackTreeInsertNodeLeftTurn(sibling)\n",
    "        sibling.parent.color, sibling.color = sibling.color, sibling.parent.color\n",
    "        # case *-2\n",
    "        redBlackTreeDeleteNodeCheckColor(node_x, root)\n",
    "        \n",
    "    \n",
    "    #case 2-1\n",
    "    elif sibling.color == 1 and sibling.left.color == 1 and sibling.right.color == 1:\n",
    "        sibling.color = 0  #red\n",
    "        result, temp = redBlackTreeDeleteNodeCheckColor(parent)\n",
    "        \n",
    "    #case 2-4: (주의) sibling 이 parent의 왼쪽 또는 오른쪽 노드인지를 구분하여 처리해야 한다.    \n",
    "    elif parent.color == 1 and sibling.color == 0 and sibling.left.color == 1 and sibling.right.color == 1:\n",
    "        if parent.right == sibling:\n",
    "            redBlackTreeInsertNodeLeftTurn(parent)\n",
    "        else:\n",
    "            redBlackTreeInsertNodeRightTurn(parent)\n",
    "        parent.color, sibling.color = sibling.color, node.parent.color\n",
    "        #case 1으로 변환 \n",
    "        result, temp = redBlackTreeDeleteNodeCheckColor(node_x)\n",
    "        \n",
    "    \n",
    "    if temp != None:\n",
    "        root = temp\n",
    "        \n",
    "    return result, root    \n",
    "\n",
    "# if this function returns (result > 0, None), it means there is error\n",
    "# if this functions returns (0, None), it means a root is deleted         \n",
    "def redBlackTreeDeleteNode(root:Node, key):\n",
    "    \n",
    "    result, node = binarySearchTreeFindNode(root, key)\n",
    "    \n",
    "    if result > 0 :\n",
    "        return result, None\n",
    "    \n",
    "    # 삭제 노드가 2개의 child 노드를 갖는 경우 :\n",
    "    # 삭제 노드의 키 값을 오른쪽 서브 트리의 최소 노드의 키 값으로 치환한 후,\n",
    "    # 오른쪽 서브 트리의 최소 노드를 삭제하는 것으로 문제를 변경하여 처리한다.\n",
    "    if node.right.nullNode != 1 and node.left.nullNode != 1:\n",
    "        target = node.right \n",
    "        while target.left != None:\n",
    "            target = target.left\n",
    "        \n",
    "        #delete target\n",
    "        key = target.key\n",
    "        \n",
    "        redBlackTreeDeleteNode(root, key)\n",
    "        \n",
    "        node.key = target.key\n",
    "        \n",
    "        return 0, root\n",
    "    \n",
    "    # 삭제 노드가 1개 또는 0개의 child 노드를 갖는 경우 :\n",
    "    # 삭제 노드가 레드인 경우, child노드와 parent를 연결시키고 종료한다.\n",
    "    # 이 경우, 삭제 노드가 1개 또는 0개의 child 노드를 갖는 두 경우가  동일하게 처리된다.\n",
    "    else:\n",
    "            \n",
    "        if node.color == 0: \n",
    "            #노드의 색이 레드인 경우 이므로, 해당 노드는 root일 수 없다.\n",
    "            #그러므로, 이 경우  root의 삭제를 고려하지 않아도 된다.       \n",
    "            if node.right.nullNode == 1:\n",
    "                node.parent = node.left\n",
    "            else:\n",
    "                node.parent = node.right\n",
    "            return 0, root\n",
    "                \n",
    "        else: # 노드의 색이 블랙인 경우\n",
    "            # node의 두 child 중 하나는 empty leaf node이다.\n",
    "            # node의 두 child 중 empty leaf node가 아닌 child를 찾는다.\n",
    "            # 단, node의 두 child가 모두 empty leaf node인 경우도 함께 처리된다.\n",
    "            if node.right.nullNonde != 1:  #if right child is not empty leaf node,\n",
    "                child = node.right\n",
    "            else:\n",
    "                child = node.left\n",
    "                \n",
    "            child.parent = node.parent\n",
    "            \n",
    "            # 삭제할 node가 루트인 경우\n",
    "            if node.parent == None:\n",
    "                if node.right.nullNode == 1 and node.left.nullNode == 1 :\n",
    "                    return 0, node\n",
    "                if node.right.nullNode != 1:\n",
    "                    node.right.color = 1\n",
    "                    return 0, node.right    #새로운 root\n",
    "                else:\n",
    "                    node.left.color = 1\n",
    "                    return 0, node.left     #새로운 root\n",
    "            \n",
    "            # 삭제할 node가 루트가 아닌 경\n",
    "            # delete a node and link its child to its parent\n",
    "            if node.parent.right == node:\n",
    "                node.parent.right = child\n",
    "            else:\n",
    "                node.parent.left = child\n",
    "                \n",
    "            # node가 삭제되어 블랙 노드의 수가 1개 부족하게 된다.\n",
    "            \n",
    "            #it is needed to check the color of nodes  \n",
    "            if child.color==0: \n",
    "                child.color = 1  # 블랙 노드의 수가 1 증가하게 된다 -> 문제 해결       \n",
    "            else: \n",
    "                #블랙 노드의 수가 1 부족한 문제를 해결해야 한다.\n",
    "                redBlackTreeDeleteNodeCheckColor(child, root) "
   ]
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}