Data Structure code complete.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Data Structure\n",
    "\n",
    "* [Array](#Array)\n",
    "* [Linked List](#Linked-List)\n",
    "* [Stack](#Stack)\n",
    "* [Queue（单链队列）](#Queue（单链队列）)\n",
    "* [Queue（循环队列）](#Queue（循环队列）)\n",
    "* [Deque](#Deque)\n",
    "* [Binary Tree](#Binary-Tree)\n",
    "* [Binary Search Tree](#Binary-Search-Tree)\n",
    "* [Balanced Search Tree](#Balanced-Search-Tree)\n",
    "* [Heap](#Heap)\n",
    "* [Union-Find](#Union-Find)\n",
    "* [Hash Table](#Hash-Table)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Array\n",
    "\n",
    "[返回目录](#Data-Structure)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Array:\n",
    "    # 使用Python列表实现\n",
    "    def __init__(self, x):\n",
    "        self.data = list(x)\n",
    "    # 数组元素的个数\n",
    "    def size(self):\n",
    "        return len(self.data)\n",
    "    # 判断数组是否为空\n",
    "    def is_empty(self):\n",
    "        return True if not self.data else False\n",
    "        # other ways: 1. self.data == [] ; 2. len(self.data) == 0\n",
    "    # 获取数组对应索引的元素，若越界则报错\n",
    "    def at(self,index):\n",
    "        if index >= len(self.data):\n",
    "            raise IndexError(\"Array index out of range.\")\n",
    "        return self.data[index]\n",
    "    # 在数组末尾插入元素\n",
    "    def push(self,item):\n",
    "        self.data.append(item)\n",
    "    # 在指定索引中插入元素，并把后面的元素依次后移\n",
    "    def insert(self, index, item):\n",
    "        self.data.insert(index, item)\n",
    "    # 删除在数组末尾的元素并返回其值\n",
    "    def pop(self):\n",
    "        return self.data.pop()\n",
    "    # 删除指定索引的元素，并把后面的元素依次前移\n",
    "    def delete(self,index):\n",
    "        self.data.pop(index)\n",
    "    # 删除指定值的元素，并返回其索引（即使有多个元素）\n",
    "    def remove(self, item):\n",
    "        index_list = []\n",
    "        item_count = self.data.count(item)\n",
    "        for i in range(item_count):\n",
    "            index_list.append(self.data.index(item))\n",
    "            self.data.remove(item)\n",
    "        return index_list\n",
    "    # 寻找指定值的元素并返回其中第一个出现的元素其索引，若未找到则返回 -1\n",
    "    def find(self, item):\n",
    "        if item in self.data:\n",
    "            return self.data.index(item)\n",
    "        else:\n",
    "            return -1\n",
    "    # 翻转数组\n",
    "    def reverse(self):\n",
    "        temp = []\n",
    "        size = len(self.data)\n",
    "        for i in range(size):\n",
    "            temp.append(self.data[size-1-i])\n",
    "        self.data = temp\n",
    "    # 升序排序数组\n",
    "    def sort(self):\n",
    "        return self.data.sort()    # self.data.sort(reverse = True) 为降序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 普通测试用例"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "array1:  [1, 2, 3, 3, 4, 3]\n",
      "size of array1:  6\n",
      "is array1 empty?  False\n",
      "the 3rd element of array1:  3\n",
      "sorted array1:  [1, 2, 3, 3, 3, 4]\n",
      "insert 9 to 3rd position:  [1, 2, 3, 9, 3, 3, 4]\n",
      "pop:  [1, 2, 3, 9, 3, 3]\n",
      "delete index 4:  [1, 2, 3, 9, 3]\n",
      "remove all 3:  [1, 2, 9]\n",
      "find the index of 9:  2\n",
      "reverse array:  [9, 2, 1]\n"
     ]
    }
   ],
   "source": [
    "array1 = Array([1,2,3,3])\n",
    "array1.push(4)\n",
    "array1.push(3)\n",
    "print(\"array1: \",array1.data)\n",
    "print(\"size of array1: \", array1.size())\n",
    "print(\"is array1 empty? \", array1.is_empty())\n",
    "print(\"the 3rd element of array1: \", array1.at(2))\n",
    "array1.sort()\n",
    "print(\"sorted array1: \",array1.data)\n",
    "array1.insert(3,9)\n",
    "print(\"insert 9 to 3rd position: \", array1.data)\n",
    "array1.pop()\n",
    "print(\"pop: \",array1.data)\n",
    "array1.delete(4)\n",
    "print(\"delete index 4: \",array1.data)\n",
    "array1.remove(3)\n",
    "print(\"remove all 3: \", array1.data)\n",
    "print(\"find the index of 9: \",array1.find(9))\n",
    "array1.reverse()\n",
    "print(\"reverse array: \",array1.data)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linked List \n",
    "\n",
    "[返回目录](#Data-Structure)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class listNode:    # 链表中的结点类\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "class LinkedList:    # 链表类\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "    # 打印链表\n",
    "    def get_list(self):\n",
    "        res = []\n",
    "        head = self.head\n",
    "        while head:\n",
    "            res.append(head.val)\n",
    "            head = head.next\n",
    "        return res\n",
    "    # 链表长度\n",
    "    def size(self):\n",
    "        size = 0\n",
    "        head = self.head\n",
    "        while head:\n",
    "            size += 1\n",
    "            head = head.next\n",
    "        return size\n",
    "    # 判断链表是否为空\n",
    "    def empty(self):\n",
    "        return False if self.head else True\n",
    "    # 返回索引处的值\n",
    "    def value_at(self, index):\n",
    "        if not self.head:\n",
    "            raise IndexError(\"Index out of range.\")\n",
    "        head = self.head\n",
    "        while index > 0:\n",
    "            if not head:\n",
    "                raise IndexError(\"Index out of range.\")\n",
    "            head = head.next\n",
    "            index -= 1\n",
    "        return head.val\n",
    "    # 添加元素到链表的首部\n",
    "    def add(self, value):\n",
    "        new_node = listNode(value)\n",
    "        new_node.next = self.head\n",
    "        self.head = new_node\n",
    "    # 删除首部元素并返回其值\n",
    "    def pop_front(self):\n",
    "        if not self.head:\n",
    "            raise IndexError(\"Pop from empty list\")\n",
    "        value = self.head.val\n",
    "        self.head = self.head.next\n",
    "        return value\n",
    "    # 添加元素到链表的尾部\n",
    "    def append(self, value):\n",
    "        new_node = listNode(value)\n",
    "        if not self.head:\n",
    "            self.head = new_node\n",
    "            return\n",
    "        head = self.head\n",
    "        while head.next:\n",
    "            head = head.next\n",
    "        head.next = new_node\n",
    "    # 删除尾部元素并返回其值\n",
    "    def pop_back(self):\n",
    "        if not self.head:\n",
    "            raise IndexError(\"Pop from empty list\")\n",
    "        if not self.head.next:\n",
    "            value = self.head.val\n",
    "            self.head = None\n",
    "            return value\n",
    "        head = self.head\n",
    "        while head.next.next:\n",
    "              head = head.next\n",
    "        value = head.next.val\n",
    "        head.next = None\n",
    "        return value\n",
    "    # 返回首部元素的值\n",
    "    def front(self):\n",
    "        if not self.head:\n",
    "            raise ValueError(\"Linked list is empty\")\n",
    "        return self.head.val\n",
    "    # 返回尾部元素的值\n",
    "    def back(self):\n",
    "        if not self.head:\n",
    "            raise ValueError(\"Linked list is empty\")\n",
    "        head = self.head\n",
    "        while head.next:\n",
    "            head = head.next\n",
    "        return head.val\n",
    "    # 插入值到指定的索引\n",
    "    def insert(self, index, value):\n",
    "        if not self.head:\n",
    "            raise IndexError(\"Index out of range\")\n",
    "        head = self.head\n",
    "        new_node = listNode(value)\n",
    "        if index == 0:\n",
    "            new_node.next = head\n",
    "            self.head = new_node\n",
    "            return\n",
    "        while index - 1 > 0:\n",
    "            head = head.next\n",
    "            if not head:\n",
    "                raise IndexError(\"Index out of range\")\n",
    "            index -= 1\n",
    "        temp = head.next\n",
    "        head.next = new_node\n",
    "        new_node.next = temp\n",
    "    # 删除指定索引的节点\n",
    "    def erase(self, index):\n",
    "        if not self.head:\n",
    "            raise IndexError(\"Index out of range\")\n",
    "        head = self.head\n",
    "        if index == 0:\n",
    "            self.head = head.next\n",
    "        while index - 1 > 0:\n",
    "            index -= 1\n",
    "            head = head.next\n",
    "            if not head:\n",
    "                raise IndexError(\"Index out of range\")\n",
    "        temp = head.next\n",
    "        head.next = temp.next\n",
    "    # 翻转链表\n",
    "    def reverse(self):\n",
    "        prev = None\n",
    "        head = self.head\n",
    "        while head:\n",
    "            temp = head.next\n",
    "            head.next = prev\n",
    "            prev = head\n",
    "            head = temp\n",
    "        self.head = prev\n",
    "    # 删除链表中指定值的第一个元素\n",
    "    def remove(self,value):\n",
    "        if not self.head:\n",
    "            return\n",
    "        head = self.head\n",
    "        if head.val == value:\n",
    "            self.head = head.next\n",
    "            return\n",
    "        while head.next:\n",
    "            if head.next.val == value:\n",
    "                temp = head.next.next\n",
    "                head.next = temp\n",
    "                return\n",
    "            head = head.next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 普通测试用例"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Linked list l1:  [1, 2, 3, 4, 4, 5]\n",
      "size of l1:  6\n",
      "is l1 empty?  False\n",
      "value at index 3:  4\n",
      "add node -1:  [-1, 1, 2, 3, 4, 4, 5]\n",
      "pop the front node:  [1, 2, 3, 4, 4, 5]\n",
      "pop the end node:  [1, 2, 3, 4, 4]\n",
      "get the front node value:  1\n",
      "get the end node value:  4\n",
      "insert 9 at index 4:  [1, 2, 3, 4, 9, 4]\n",
      "erase index 1:  [1, 3, 4, 9, 4]\n",
      "remove value 4:  [1, 3, 9, 4]\n",
      "revers l1:  [4, 9, 3, 1]\n"
     ]
    }
   ],
   "source": [
    "l1 = LinkedList()\n",
    "a = [1,2,3,4,4,5]\n",
    "for i in a:\n",
    "    l1.append(i)\n",
    "print(\"Linked list l1: \", l1.get_list())\n",
    "print(\"size of l1: \", l1.size())\n",
    "print(\"is l1 empty? \", l1.empty())\n",
    "print(\"value at index 3: \", l1.value_at(3))\n",
    "l1.add(-1)\n",
    "print(\"add node -1: \", l1.get_list())\n",
    "l1.pop_front()\n",
    "print(\"pop the front node: \", l1.get_list())\n",
    "l1.pop_back()\n",
    "print(\"pop the end node: \", l1.get_list())\n",
    "print(\"get the front node value: \", l1.front())\n",
    "print(\"get the end node value: \", l1.back())\n",
    "l1.insert(4,9)\n",
    "print(\"insert 9 at index 4: \",l1.get_list())\n",
    "l1.erase(1)\n",
    "print(\"erase index 1: \",l1.get_list())\n",
    "l1.remove(4)\n",
    "print(\"remove value 4: \",l1.get_list())\n",
    "l1.reverse()\n",
    "print(\"revers l1: \",l1.get_list())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stack\n",
    "\n",
    "[返回目录](#Data-Structure)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Stack:\n",
    "    # 使用Python的列表实现\n",
    "    def __init__(self):\n",
    "        self.data = []\n",
    "    # 压栈\n",
    "    def push(self, item):\n",
    "        self.data.append(item)\n",
    "    # 出栈\n",
    "    def pop(self):\n",
    "        if self.data:\n",
    "            return self.data.pop()\n",
    "        else:\n",
    "            raise PopError(\"Pop from empty stack.\")\n",
    "    # 取栈顶的元素\n",
    "    def peek(self):\n",
    "        if self.data:\n",
    "            return self.data[-1]\n",
    "        else:\n",
    "            raise IndexError(\"Stack is empty.\")\n",
    "    # 返回栈的大小\n",
    "    def size(self):\n",
    "        return len(self.data)\n",
    "    # 判断栈是否为空\n",
    "    def is_empty(self):\n",
    "        return self.data == []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 普通测试用例"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "s1:  [1, 2, 3, 4, 5]\n",
      "s1 peek:  5\n",
      "s1 pop and peek:  4\n",
      "s1 size:  4\n",
      "is s1 empty?  False\n"
     ]
    }
   ],
   "source": [
    "s1 = Stack()\n",
    "a = [1,2,3,4,5]\n",
    "for i in a:\n",
    "    s1.push(i)\n",
    "print(\"s1: \", a)\n",
    "print(\"s1 peek: \",s1.peek())\n",
    "s1.pop()\n",
    "print(\"s1 pop and peek: \",s1.peek())\n",
    "print(\"s1 size: \", s1.size())\n",
    "print(\"is s1 empty? \", s1.is_empty())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Queue（单链队列）\n",
    "\n",
    "[返回目录](#Data-Structure)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Queue:\n",
    "    # 使用Python的列表实现\n",
    "    def __init__(self):\n",
    "        self.data = []\n",
    "    # 元素入队（在队尾添加元素）\n",
    "    def enqueue(self, item):\n",
    "        self.data.append(item)\n",
    "    # 出队\n",
    "    def dequeue(self):\n",
    "        if self.data:\n",
    "            return self.data.pop(0)\n",
    "        else:\n",
    "            raise DequeueError(\"Queue is empty.\")\n",
    "    # 返回队列长度\n",
    "    def size(self):\n",
    "        return len(self.data)\n",
    "    # 判空\n",
    "    def is_empty(self):\n",
    "        return self.data == []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 普通测试用例"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "queue q1:  [1, 2, 3, 4, 5]\n",
      "dequeue:  1\n",
      "size of q1:  4\n",
      "is q1 empty?  False\n"
     ]
    }
   ],
   "source": [
    "q1 = Queue()\n",
    "a = [1,2,3,4,5]\n",
    "for i in a:\n",
    "    q1.enqueue(i)\n",
    "print(\"queue q1: \", a)\n",
    "print(\"dequeue: \", q1.dequeue())\n",
    "print(\"size of q1: \", q1.size())\n",
    "print(\"is q1 empty? \", q1.is_empty())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Queue（循环队列）\n",
    "\n",
    "[返回目录](#Data-Structure)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "class CircularQueue:\n",
    "    def __init__(self, max_size = 6):\n",
    "        self.data = [None]*(max_size+1)\n",
    "        self.front = 0\n",
    "        self.rear = 0\n",
    "    # 获得队列可容纳的最大长度\n",
    "    def get_max_size(self):\n",
    "        return len(self.data) - 1\n",
    "    # 调整队列的最大长度（扩容或缩减）\n",
    "    def resize(self, max_size):\n",
    "        new_queue = [None]*(max_size+1)\n",
    "        size = self.size()\n",
    "        for i in range(size):\n",
    "            new_queue[i] = self.data[(self.front+i)%self.get_max_size()]\n",
    "        self.data = new_queue\n",
    "        self.front = 0\n",
    "        self.rear = size\n",
    "    # 将新元素添加到队尾，若队列已满则报错\n",
    "    def enqueue_strict(self, item):\n",
    "        if (self.rear+1) % len(self.data) == self.front:\n",
    "            raise SizeError(\"Queue is full. Unable to enqueue.\")\n",
    "        self.data[self.rear] = item\n",
    "        self.rear = (self.rear+1) % len(self.data)\n",
    "    # 将队首的元素出队，若队列为空则报错\n",
    "    def dequeue_strict(self):\n",
    "        if self.front == self.rear:\n",
    "            raise SizeError(\"Queue is empty. Unable to dequeue.\")\n",
    "        item = self.data[self.front]\n",
    "        self.data[self.front] = None\n",
    "        self.front = (self.front + 1) % len(self.data)\n",
    "        return item\n",
    "    # 将新元素添加到队尾，若队列已满，则先扩容为原来可容纳大小的2倍，再入队\n",
    "    def enqueue(self, item):\n",
    "        if (self.rear+1) % len(self.data) == self.front:\n",
    "            self.resize(self.get_max_size() * 2)\n",
    "        self.data[self.rear] = item\n",
    "        self.rear = (self.rear+1) % len(self.data)\n",
    "    # 将队首的元素出队，若队列为空则报错。若队列当前长度为可容纳总长度的1/4，且列表总空间大于等于2时，将队列最大长度减小为原来的1/2以减小空间开销\n",
    "    def dequeue(self):\n",
    "        if self.front == self.rear:\n",
    "            raise SizeError(\"Queue is empty. Unable to dequeue.\")\n",
    "        item = self.data[self.front]\n",
    "        self.data[self.front] = None\n",
    "        self.front = (self.front + 1) % len(self.data)\n",
    "        if self.size() == self.get_max_size()//4 and len(self.data) >= 2:\n",
    "            self.resize(self.get_max_size() // 2)\n",
    "        return item\n",
    "    # 获得队列的当前长度\n",
    "    def size(self):\n",
    "        return (self.rear - self.front + len(self.data)) % len(self.data)\n",
    "    # 判断队列是否为空\n",
    "    def is_empty(self):\n",
    "        return self.front == self.rear"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 普通测试用例"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "queue q1:  [1, 2, 3, 4, 5, 6, None]\n",
      "q1 max_size:  6\n",
      "after enqueue, max size:  12\n",
      "q1:  [1, 2, 3, 4, 5, 6, 7, None, None, None, None, None, None]\n",
      "q1 size:  7\n",
      "is q1 empty?  False\n",
      "dequeue until q1 size = 3\n",
      "dequeue:  1\n",
      "dequeue:  2\n",
      "dequeue:  3\n",
      "dequeue:  4\n",
      "now q1 size =  3\n",
      "q1:  [5, 6, 7, None, None, None, None]\n",
      "q1 max size:  6\n"
     ]
    }
   ],
   "source": [
    "q1 = CircularQueue()\n",
    "a = [1,2,3,4,5,6]\n",
    "for i in a:\n",
    "    q1.enqueue(i)\n",
    "print(\"queue q1: \", q1.data)\n",
    "print(\"q1 max_size: \", q1.get_max_size())\n",
    "q1.enqueue(7)\n",
    "print(\"after enqueue, max size: \", q1.get_max_size())\n",
    "print(\"q1: \", q1.data)\n",
    "print(\"q1 size: \", q1.size())\n",
    "print(\"is q1 empty? \", q1.is_empty())\n",
    "print(\"dequeue until q1 size = 3\")\n",
    "for i in range(4):\n",
    "    print(\"dequeue: \", q1.dequeue())\n",
    "print(\"now q1 size = \", q1.size())\n",
    "print(\"q1: \", q1.data)\n",
    "print(\"q1 max size: \", q1.get_max_size())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Deque\n",
    "\n",
    "[返回目录](#Data-Structure)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Deque:\n",
    "    def __init__(self):\n",
    "        self.data = []\n",
    "    def is_empty(self):\n",
    "        return self.data == []\n",
    "    def add_front(self, item):\n",
    "        self.data.append(item)\n",
    "    def add_rear(self, item):\n",
    "        self.data.insert(0, item)\n",
    "    def remove_front(self):\n",
    "        return self.data.pop()\n",
    "    def remove_rear(self):\n",
    "        return self.data.pop(0)\n",
    "    def size(self):\n",
    "        return len(self.data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "is d1 empty?  True\n",
      "d1 size:  4\n",
      "is d1 empty?  False\n",
      "d1:  ['bird', 'cat', 4, 'dog']\n",
      "remove rear:  bird\n",
      "remove front:  dog\n",
      "d1:  ['cat', 4]\n"
     ]
    }
   ],
   "source": [
    "d1 = Deque()\n",
    "print(\"is d1 empty? \", d1.is_empty())\n",
    "d1.add_front(4)\n",
    "d1.add_front('dog')\n",
    "d1.add_rear('cat')\n",
    "d1.add_rear('bird')\n",
    "print('d1 size: ', d1.size())\n",
    "print('is d1 empty? ', d1.is_empty())\n",
    "print('d1: ', d1.data)\n",
    "print('remove rear: ', d1.remove_rear())\n",
    "print('remove front: ', d1.remove_front())\n",
    "print('d1: ', d1.data)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary Tree\n",
    "\n",
    "* [二叉树的遍历（递归实现）](#二叉树的遍历（递归实现）)\n",
    "* [二叉树的遍历（非递归实现）](#二叉树的遍历（非递归实现）)\n",
    "\n",
    "[返回目录](#Data-Structure)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class treeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 二叉树的遍历（递归实现）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 前序遍历\n",
    "def preorder(root):\n",
    "    if root is None:\n",
    "        return []\n",
    "    return [root.val] + preorder(root.left) + preorder(root.right)\n",
    "\n",
    "# 中序遍历\n",
    "def inorder(root):\n",
    "    if root is None:\n",
    "        return []\n",
    "    return inorder(root.left) + [root.val] + inorder(root.right)\n",
    "\n",
    "# 后序遍历\n",
    "def postorder(root):\n",
    "    if not root:\n",
    "        return []\n",
    "    return postorder(root.left) + postorder(root.right) + [root.val]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 测试用例"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "PreOrder:  [1, 2, 4, 5, 3, 6]\n",
      "InOrder:  [4, 2, 5, 1, 3, 6]\n",
      "PostOrder:  [4, 5, 2, 6, 3, 1]\n"
     ]
    }
   ],
   "source": [
    "a1 = treeNode(1)\n",
    "a2 = treeNode(2)\n",
    "a3 = treeNode(3)\n",
    "a4 = treeNode(4)\n",
    "a5 = treeNode(5)\n",
    "a6 = treeNode(6)\n",
    "'''\n",
    "            1\n",
    "          /   \\\n",
    "         /     \\\n",
    "        2       3\n",
    "       / \\       \\\n",
    "      4   5       6 \n",
    "'''\n",
    "a1.left = a2\n",
    "a1.right = a3\n",
    "a2.left = a4\n",
    "a2.right = a5\n",
    "a3.right = a6\n",
    "\n",
    "# 验证前序遍历\n",
    "print(\"PreOrder: \", preorder(a1))  # [1,2,4,5,3,6]\n",
    "# 验证中序遍历\n",
    "print(\"InOrder: \", inorder(a1))  # [4,2,5,1,3,6]\n",
    "# 验证后序遍历\n",
    "print(\"PostOrder: \", postorder(a1))  # [4,5,2,6,3,1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 二叉树的遍历（非递归实现）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 前序遍历\n",
    "def preorder_wh(root):\n",
    "    if root is None:\n",
    "        return []\n",
    "    res = []\n",
    "    nodestack = []\n",
    "    while nodestack or root:\n",
    "        if root:\n",
    "            res.append(root.val)\n",
    "            nodestack.append(root)\n",
    "            root = root.left\n",
    "        else:\n",
    "            root = nodestack.pop()\n",
    "            root = root.right\n",
    "    return res\n",
    "\n",
    "# 中序遍历\n",
    "def inorder_wh(root):\n",
    "    if root is None:\n",
    "        return []\n",
    "    res = []\n",
    "    nodestack = []\n",
    "    while nodestack or root:\n",
    "        if root:\n",
    "            nodestack.append(root)\n",
    "            root = root.left\n",
    "        else:\n",
    "            root = nodestack.pop()\n",
    "            res.append(root.val)\n",
    "            root = root.right\n",
    "    return res\n",
    "\n",
    "# 后序遍历1：修改前序遍历，倒序输出“根-右-左”\n",
    "def postorder_wh1(root):\n",
    "    if root is None:\n",
    "        return []\n",
    "    res = []\n",
    "    nodestack = []\n",
    "    while nodestack or root:\n",
    "        if root:\n",
    "            res.append(root.val)\n",
    "            nodestack.append(root)\n",
    "            root = root.right\n",
    "        else:\n",
    "            root = nodestack.pop()\n",
    "            root = root.left\n",
    "    # res1 用来存放 res 的倒序输出，或者直接用 res[::-1] 倒序输出\n",
    "    res1 = []\n",
    "    for i in range(len(res)):\n",
    "        res1.append(res.pop())\n",
    "    return res1\n",
    "\n",
    "# 后序遍历2：使用两个栈实现\n",
    "def postorder_wh2(root):\n",
    "    if root is None:\n",
    "        return []\n",
    "    res = []\n",
    "    nodestack = [root]\n",
    "    while nodestack:\n",
    "        root = nodestack.pop()\n",
    "        res.append(root)\n",
    "        if root.left:\n",
    "            nodestack.append(root.left)\n",
    "        if root.right:\n",
    "            nodestack.append(root.right)\n",
    "    # 此时res中存放了倒序的结点，使用res1将其倒序输出并取结点的值\n",
    "    res1 = []\n",
    "    for i in range(len(res)):\n",
    "        res1.append(res.pop().val)\n",
    "    return res1\n",
    "\n",
    "# 层次遍历\n",
    "def level_order(root):\n",
    "    if not root:\n",
    "        return []\n",
    "    res = []\n",
    "    nodequeue = [root]\n",
    "    while nodequeue:\n",
    "        root = nodequeue.pop(0)\n",
    "        res.append(root.val)\n",
    "        if root.left:\n",
    "            nodequeue.append(root.left)\n",
    "        if root.right:\n",
    "            nodequeue.append(root.right)\n",
    "    return res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 测试用例"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "PreOrder:  [1, 2, 4, 5, 3, 6]\n",
      "InOrder:  [4, 2, 5, 1, 3, 6]\n",
      "PostOrder, method 1 :  [4, 5, 2, 6, 3, 1]\n",
      "PostOrder, method 2 :  [4, 5, 2, 6, 3, 1]\n",
      "LevelOrder:  [1, 2, 3, 4, 5, 6]\n"
     ]
    }
   ],
   "source": [
    "a1 = treeNode(1)\n",
    "a2 = treeNode(2)\n",
    "a3 = treeNode(3)\n",
    "a4 = treeNode(4)\n",
    "a5 = treeNode(5)\n",
    "a6 = treeNode(6)\n",
    "'''\n",
    "            1\n",
    "          /   \\\n",
    "         /     \\\n",
    "        2       3\n",
    "       / \\       \\\n",
    "      4   5       6 \n",
    "'''\n",
    "a1.left = a2\n",
    "a1.right = a3\n",
    "a2.left = a4\n",
    "a2.right = a5\n",
    "a3.right = a6\n",
    "\n",
    "# 验证前序遍历\n",
    "print(\"PreOrder: \", preorder_wh(a1))  # [1,2,4,5,3,6]\n",
    "# 验证中序遍历\n",
    "print(\"InOrder: \", inorder_wh(a1))  # [4,2,5,1,3,6]\n",
    "# 验证后序遍历：方法1\n",
    "print(\"PostOrder, method 1 : \", postorder_wh1(a1))  # [4,5,2,6,3,1]\n",
    "# 验证后序遍历：方法2\n",
    "print(\"PostOrder, method 2 : \", postorder_wh2(a1))\n",
    "# 验证层次遍历\n",
    "print(\"LevelOrder: \", level_order(a1))  # [1,2,3,4,5,6]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary Search Tree\n",
    "\n",
    "[返回目录](#Data-Structure)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class treeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "# 查找某个元素\n",
    "def find_item(item, root):\n",
    "    if not root:\n",
    "        return None\n",
    "    while root:\n",
    "        if root.val == item:\n",
    "            return root\n",
    "        elif root.val > item:\n",
    "            root = root.left\n",
    "        else:\n",
    "            root = root.right\n",
    "    return None\n",
    "# 返回BST中的最小元素\n",
    "def find_min(root):\n",
    "    if not root:\n",
    "        return None\n",
    "    while root.left:\n",
    "        root = root.left\n",
    "    return root\n",
    "# 返回BST中的最大元素\n",
    "def find_max(root):\n",
    "    if not root:\n",
    "        return None\n",
    "    while root.right:\n",
    "        root = root.right\n",
    "    return root\n",
    "# 在二叉搜索树中插入一个新的元素，若元素已存在则忽略\n",
    "def add_node(value, root):\n",
    "    if not root:\n",
    "        return treeNode(value)\n",
    "    if value > root.val:\n",
    "        root.right = add_node(value, root.right)  # 递归插入右子树\n",
    "    elif value < root.val:\n",
    "        root.left = add_node(value, root.left)  # 递归插入左子树\n",
    "    else:\n",
    "        pass  # 如果value已经存在，则什么也不做\n",
    "    return root\n",
    "# 从二叉搜索树中删除一个结点\n",
    "def delete_node(value, root):\n",
    "    if not root:\n",
    "        return None  # 说明要删除的元素未找到\n",
    "    if value < root.val:\n",
    "        root.left = delete_node(value, root.left)  # 左子树递归删除\n",
    "    elif value > root.val:\n",
    "        root.right = delete_node(value, root.right)  # 右子树递归删除\n",
    "    else:  # 说明已经找到要删除的结点了\n",
    "        if not root.left:  # 只有右子树或者没有子结点\n",
    "            return root.right\n",
    "        elif not root.right:  # 只有左子树\n",
    "            return root.left\n",
    "        else:  # 有左右两个结点\n",
    "            temp = find_min(root.right)  # 在右子树中找到最小的元素\n",
    "            root.val = temp.val\n",
    "            root.right = delete_node(temp.val, root.right)\n",
    "    return root"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 测试用例"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "test add_node. After add, InOrder:  [1, 2, 3, 4, 5, 6, 7]\n",
      "find value 6. Left:  5 right:  7\n",
      "find min:  1\n",
      "find max:  7\n",
      "delete value 6, InOrder:  [1, 2, 3, 4, 5, 7]\n"
     ]
    }
   ],
   "source": [
    "a1 = treeNode(4)\n",
    "'''\n",
    "            4\n",
    "          /   \\\n",
    "         /     \\\n",
    "        2       6\n",
    "       / \\     / \\\n",
    "      1   3   5   7 \n",
    "'''\n",
    "for i in [2,1,3,6,5,7,3]:\n",
    "    add_node(i, a1)\n",
    "print(\"test add_node. After add, InOrder: \", inorder_wh(a1))\n",
    "print(\"find value 6. Left: \", find_item(6, a1).left.val, \"right: \", find_item(6, a1).right.val)\n",
    "print(\"find min: \", find_min(a1).val)\n",
    "print(\"find max: \", find_max(a1).val)\n",
    "delete_node(6, a1)\n",
    "print(\"delete value 6, InOrder: \",inorder_wh(a1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Balanced Search Tree\n",
    "\n",
    "实现红黑树\n",
    "\n",
    "[返回目录](#Data-Structure)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "BLACK = False\n",
    "RED = True\n",
    "\n",
    "class rb_node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.color = BLACK\n",
    "        \n",
    "'''\n",
    "这里实现的红黑树：\n",
    "红色结点均为左结点\n",
    "'''\n",
    "class RedBlackBST:\n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "    def rotate_left(self, node):\n",
    "        if not node.right:\n",
    "            return False\n",
    "        temp = node.right\n",
    "        node.right = temp.left\n",
    "        temp.left = node\n",
    "        return temp\n",
    "    def rotate_right(self, node):\n",
    "        if not node.left:\n",
    "            return False\n",
    "        temp = node.left\n",
    "        node.left = temp.right\n",
    "        temp.right = node\n",
    "        return temp\n",
    "    def re_color(self, node):\n",
    "        # 重新着色. 着色前：结点是黑色，两个子结点都是红色；着色后：结点是红色，两个子结点都是黑色\n",
    "        self.color = RED\n",
    "        self.left.color = BLACK\n",
    "        self.right.color = BLACK\n",
    "    def is_red(self, node):\n",
    "        if not node:\n",
    "            return False\n",
    "        return node.color == RED\n",
    "    def insert(self, val):\n",
    "        def _insert(node, val):\n",
    "            new_node = rb_node(val)\n",
    "            if not node:\n",
    "                new_node.color = RED\n",
    "                return new_node\n",
    "            if val > node.val:\n",
    "                node.right = _insert(node.right, val)\n",
    "            elif val < node.val:\n",
    "                node.left = _insert(node.left, val)\n",
    "            else:\n",
    "                pass\n",
    "            # 分三种case修复结点（见笔记）；顺序：CASE2-CASE3-CASE1\n",
    "            if is_red()\n",
    "        _insert(self.root, val)\n",
    "        self.root.color = BLACK"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Heap\n",
    "\n",
    "[返回目录](#Data-Structure)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MaxHeap:\n",
    "    def __init__(self):\n",
    "        self.data = [None]\n",
    "    # 判断堆是否为空\n",
    "    def is_empty(self):\n",
    "        return len(self.data) == 1\n",
    "    # 获得堆当前的大小\n",
    "    def get_size(self):\n",
    "        return len(self.data) - 1\n",
    "    # 返回堆顶元素（最大值），但不删除\n",
    "    def peek_max(self):\n",
    "        if self.is_empty():\n",
    "            return None\n",
    "        else:\n",
    "            return self.data[1]\n",
    "    # 向堆中插入元素\n",
    "    def insert(self, value):\n",
    "        self.data.append(value)\n",
    "        index = self.get_size()\n",
    "        # 如果比父结点大并且不是根结点则向上调整\n",
    "        while index > 1 and self.data[index] > self.data[index//2]:\n",
    "            self.data[index], self.data[index//2] = self.data[index//2], self.data[index]\n",
    "            index = index // 2\n",
    "    # 用于删除和创建堆的函数。从当前结点开始向下调整，保证结点往下是一个堆\n",
    "    def sift_down(self, index):\n",
    "        while 2*index <= self.get_size():\n",
    "            # 左子结点的索引\n",
    "            child = 2 * index\n",
    "            # 如果右子结点存在且比左子结点大，则应与右子结点交换\n",
    "            if 2*index + 1 <= self.get_size() and self.data[2*index+1] > self.data[2*index]:\n",
    "                child += 1  # 右子结点的索引\n",
    "            # 如果当前结点的值小于子结点中的较大者，则应继续向下交换，否则结束\n",
    "            if self.data[index] < self.data[child]:\n",
    "                self.data[index], self.data[child] = self.data[child], self.data[index]\n",
    "                index = child\n",
    "            else:\n",
    "                break\n",
    "    # 删除堆顶元素（最大值）\n",
    "    def remove(self):\n",
    "        if self.is_empty():\n",
    "            raise RemoveError(\"Unable to remove from an empty heap.\")\n",
    "        # 用堆的最后一个元素替代堆顶元素，然后删除最后一个元素\n",
    "        self.data[1], self.data[self.get_size()] = self.data[self.get_size()], self.data[1]\n",
    "        self.data.pop()\n",
    "        # 从堆顶向下调整\n",
    "        self.sift_down(1)\n",
    "    # 从一个序列创建堆\n",
    "    def build_heap(self, array):\n",
    "        self.data = [None] + array\n",
    "        index = self.get_size() // 2\n",
    "        # 从倒数第二层开始，从右到左，逐层向上调整。每次调整只需sift_down\n",
    "        while index > 0:\n",
    "            self.sift_down(index)\n",
    "            index -= 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 测试用例"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "build heap through list:  [None, 60, 33, 48, 21, 5, 1, 16]\n",
      "insert value 100:  [None, 100, 60, 48, 33, 5, 1, 16, 21]\n",
      "value of top of h1:  100\n",
      "remove top of heap:  [None, 60, 33, 48, 21, 5, 1, 16]\n",
      "size of h1:  7\n",
      "is h1 empty?  False\n"
     ]
    }
   ],
   "source": [
    "a = [1,5,16,21,33,48,60]\n",
    "h1 = MaxHeap()\n",
    "h1.build_heap(a)\n",
    "print(\"build heap through list: \", h1.data)\n",
    "h1.insert(100)\n",
    "print(\"insert value 100: \", h1.data)\n",
    "print(\"value of top of h1: \", h1.peek_max())\n",
    "h1.remove()\n",
    "print(\"remove top of heap: \", h1.data)\n",
    "print(\"size of h1: \",h1.get_size())\n",
    "print(\"is h1 empty? \", h1.is_empty())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Union-Find\n",
    "\n",
    "[返回目录](#Data-Structure)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 实现平衡树形结构的并查集\n",
    "class UnionFind:\n",
    "    # 初始化并查集中的元素，默认每个元素的值就是数组下标，每个元素的集合只有自身\n",
    "    def __init__(self, N):\n",
    "        self.data = list(range(N))  # 存储元素的值\n",
    "        self.count = N    # 存储集合的个数\n",
    "        self.parent = list(range(N))  # 存储该元素的父结点的数组下标\n",
    "        self.size = [1] * N  # 存储以该元素为根的树的大小（树中的元素个数）\n",
    "    def find(self, value):    # 返回根结点的下标\n",
    "        index = self.data.index(value)\n",
    "        while self.parent[index] != index:\n",
    "            index = self.parent[index]\n",
    "        return index\n",
    "    def union(self, value1, value2):\n",
    "        root1 = self.find(value1)\n",
    "        root2 = self.find(value2)\n",
    "        if root1 == root2:\n",
    "            return\n",
    "        if self.size[root1] > self.size[root2]:\n",
    "            self.parent[root2] = root1\n",
    "            self.size[root1] += self.size[root2]\n",
    "        else:\n",
    "            self.parent[root1] = root2\n",
    "            self.size[root2] + self.size[root1]\n",
    "        self.count -= 1\n",
    "    def connected(self, value1, value2):\n",
    "        return self.find(value1) == self.find(value2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 测试用例"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "find 5:  5\n",
      "find 4:  4\n",
      "find 2:  4\n",
      "find 3:  4\n",
      "connected: 1,8:  True\n",
      "connected: 3,7 False\n"
     ]
    }
   ],
   "source": [
    "uf1 = UnionFind(10)\n",
    "print(\"find 5: \", uf1.find(5))\n",
    "# {0} {1,5,8} {2,3,4,6} {7,9}\n",
    "uf1.union(1, 5)\n",
    "uf1.union(5, 8)\n",
    "uf1.union(2, 6)\n",
    "uf1.union(3, 6)\n",
    "uf1.union(2, 4)\n",
    "uf1.union(7, 9)\n",
    "print(\"find 4: \", uf1.find(4))\n",
    "print(\"find 2: \", uf1.find(2))\n",
    "print(\"find 3: \", uf1.find(3))\n",
    "print(\"connected: 1,8: \", uf1.connected(1,8))\n",
    "print(\"connected: 3,7\", uf1.connected(3,7))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Hash Table\n",
    "\n",
    "[返回目录](#Data-Structure)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class listNode:\n",
    "    def __init__(self, key, value):\n",
    "        self.key = key\n",
    "        self.value = value\n",
    "        self.next = None\n",
    "\n",
    "class HashTable:\n",
    "    def __init__(self, N):\n",
    "        self.size = N\n",
    "        self.table = [None] * N\n",
    "    def hash_code(self, key):\n",
    "        # (((a*key + b) mod p) mod N)\n",
    "        return ((13 * key  + 31) % 16908799) % self.size\n",
    "    def insert(self, key, value):\n",
    "        index = self.hash_code(key)\n",
    "        head = self.table[index]\n",
    "        if not head:  # 如果哈希表对应位置还是空的\n",
    "            self.table[index] = listNode(key, value)\n",
    "        else:\n",
    "            while head.next:\n",
    "                head = head.next\n",
    "            head.next = listNode(key, value)\n",
    "    def find(self, key):\n",
    "        index = self.hash_code(key)\n",
    "        head = self.table[index]\n",
    "        if not head:\n",
    "            return None\n",
    "        else:\n",
    "            while head:\n",
    "                if head.key == key:\n",
    "                    return head.value\n",
    "                head = head.next\n",
    "            return None\n",
    "    def remove(self, key):\n",
    "        index = self.hash_code(key)\n",
    "        head = self.table[index]\n",
    "        if not head:\n",
    "            return None\n",
    "        else:\n",
    "            prev = None\n",
    "            while head:\n",
    "                if head.key == key:\n",
    "                    next_node = head.next\n",
    "                    if prev:\n",
    "                        prev.next = next_node\n",
    "                        return head.value\n",
    "                    else:\n",
    "                        self.table[index] = head.next\n",
    "                        return head.value\n",
    "                else:\n",
    "                    prev = head\n",
    "                    head = head.next\n",
    "            return None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 测试用例"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "find 322:  jack\n",
      "find 543:  michael\n",
      "find 167:  jhon\n",
      "find 132:  henry\n",
      "find 113:  steve\n",
      "================\n",
      "find 333:  None\n",
      "================\n",
      "remove 322\n",
      "find 322:  None\n"
     ]
    }
   ],
   "source": [
    "h1 = HashTable(20)\n",
    "a = [\n",
    "    [322, 'jack'],\n",
    "    [543, 'michael'],\n",
    "    [167, 'jhon'],\n",
    "    [132, 'henry'],\n",
    "    [113, 'steve'],\n",
    "    [256, 'ray'],\n",
    "    [289, 'christopher']\n",
    "]\n",
    "for x in a:\n",
    "    h1.insert(x[0], x[1])\n",
    "print(\"find 322: \", h1.find(322))\n",
    "print(\"find 543: \", h1.find(543))\n",
    "print(\"find 167: \", h1.find(167))\n",
    "print(\"find 132: \", h1.find(132))\n",
    "print(\"find 113: \", h1.find(113))\n",
    "print(\"================\")\n",
    "print(\"find 333: \", h1.find(333))\n",
    "print(\"================\")\n",
    "print(\"remove 322\")\n",
    "h1.remove(322)\n",
    "print(\"find 322: \", h1.find(322))"
   ]
  },
  {
   "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.6.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}