chapter_12.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 12 -- Binary Search Trees"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class BinaryNode(object):\n",
    "    \n",
    "    def __init__(self, key, parent, left=None, right=None):\n",
    "        self.key = key\n",
    "        self.parent = parent\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        \n",
    "    def __repr__(self):\n",
    "        return str(self.key)\n",
    "    \n",
    "class Tree(object):\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "        \n",
    "    def search(self, key):\n",
    "        return search(self.root, key)\n",
    "        \n",
    "    def insert(self, key):\n",
    "        node = BinaryNode(key, None)\n",
    "        pointer = self.root\n",
    "        parent = None\n",
    "        while pointer:\n",
    "            parent = pointer\n",
    "            if pointer.key > node.key:\n",
    "                pointer = pointer.left\n",
    "            else:\n",
    "                pointer = pointer.right\n",
    "        node.parent = parent\n",
    "        if parent == None:\n",
    "            self.root = node\n",
    "        elif parent.key > node.key:\n",
    "            parent.left = node\n",
    "        else:\n",
    "            parent.right = node\n",
    "            \n",
    "    def delete(self, node):\n",
    "        if not node.left:\n",
    "            self.transplant(node, node.right)\n",
    "        elif not node.right:\n",
    "            self.transplant(node, node.left)\n",
    "        else:\n",
    "            head = successor(node)\n",
    "            if head.parent != node:\n",
    "                self.transplant(head, head.right)\n",
    "                head.right = node.right\n",
    "                head.right.parent = head\n",
    "            self.transplant(node, head)\n",
    "            head.left = node.left\n",
    "            head.left.parent = head\n",
    "            \n",
    "    def transplant(self, old, new):\n",
    "        if not old.parent:\n",
    "            self.root = new\n",
    "        elif old == old.parent.left:\n",
    "            old.parent.left = new\n",
    "        else:\n",
    "            old.parent.right = new\n",
    "        if new:\n",
    "            new.parent = old.parent\n",
    "            \n",
    "\n",
    "def inorder_walk(node):\n",
    "    result = []\n",
    "    if node:\n",
    "        result.extend(inorder_walk(node.left))\n",
    "        result.append(node.key)\n",
    "        result.extend(inorder_walk(node.right))\n",
    "    return result\n",
    "\n",
    "def preorder_walk(node):\n",
    "    result = []\n",
    "    if node:\n",
    "        result.append(node.key)\n",
    "        result.extend(preorder_walk(node.left))\n",
    "        result.extend(preorder_walk(node.right))\n",
    "    return result\n",
    "\n",
    "def postorder_walk(node):\n",
    "    result = []\n",
    "    if node:\n",
    "        result.extend(postorder_walk(node.left))\n",
    "        result.extend(postorder_walk(node.right))\n",
    "        result.append(node.key)\n",
    "    return result\n",
    "\n",
    "def search(node, key):\n",
    "    while (node) and (node.key != key):\n",
    "        if node.key > key:\n",
    "            node = node.left\n",
    "        else:\n",
    "            node = node.right\n",
    "    return node\n",
    "    \n",
    "def minimum(node):\n",
    "    while node.left:\n",
    "        node = node.left\n",
    "    return node\n",
    "\n",
    "def maximum(node):\n",
    "    while node.right:\n",
    "        node = node.right\n",
    "    return node\n",
    "\n",
    "def successor(node):\n",
    "    if node.right:\n",
    "        return minimum(node.right)\n",
    "    else:\n",
    "        sucessor = node.parent\n",
    "        while (successor) and (node == successor.right):\n",
    "            node = successor\n",
    "            successor = successor.parent\n",
    "        return successor\n",
    "    \n",
    "def predecessor(node):\n",
    "    if node.left:\n",
    "        return maximum(node.left)\n",
    "    else:\n",
    "        predecessor = node.parent\n",
    "        while (successor) and (node == predecessor.left):\n",
    "            node = predecessor\n",
    "            predecessor = predecessor.parent\n",
    "        return predecessor\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = Tree()\n",
    "for key in [5, 6, 4, 7, 3, 8, 2, 0, 9, 1]:\n",
    "    tree.insert(key)\n",
    "inorder_walk(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 4, 3, 2, 0, 1, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "preorder_walk(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 0, 2, 3, 4, 9, 8, 7, 6, 5]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "postorder_walk(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maximum(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "minimum(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "successor(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "predecessor(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "tree.search(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "tree.delete(tree.search(5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[6, 4, 3, 2, 0, 1, 7, 8, 9]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "preorder_walk(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}