Lab-03-BST.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Binary Search Tree\n",
    "\n",
    "In this assignment, we will implement the binary search tree data structure and its related operations. First of all, we need a class for holding a node in the tree. Each node would have a key and the corresponding value. All BST operations should be based on comparing keys. Each node would also have a link to its left and right neighbors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, key, value, left=None, right=None):\n",
    "        self.key = key\n",
    "        self.value = value\n",
    "        self.left = left\n",
    "        self.right = right"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can implement the BST methods."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insert(root, key, value):\n",
    "    \"\"\"Insert (key, value) at the appropriate place of the binary search \n",
    "    tree rooted at node `root'. If `root' is None, it means that \n",
    "    the tree empty - you need to create the root node.\n",
    "    Return the root node.\"\"\"\n",
    "    \n",
    "    # Your code after this line\n",
    "    \n",
    "    return root\n",
    "\n",
    "def search(root, key):\n",
    "    \"\"\"Search the binary search tree with root node `root' for a node with\n",
    "    key value `key'. If the key is present in the tree, \n",
    "    return the list of (key, value) tuples in the path from the root node to \n",
    "    the found node: [(root-key, root-value), ... , (key, value)]\n",
    "    If the key is not present, return None\"\"\"\n",
    "    \n",
    "    # Your code after this line\n",
    "    \n",
    "\n",
    "def inorder(root):\n",
    "    \"\"\"Return a list of tuples (key, value) in the in-order traversal of bst \n",
    "    rooted at `root'.\"\"\"\n",
    "    \n",
    "    # Your code after this line\n",
    "    \n",
    "\n",
    "def bstmin(root):\n",
    "    \"\"\"Return the (key, value) pair corresponding to the least `key' in the bst.\"\"\"\n",
    "    \n",
    "    # Your code after this line.\n",
    "    \n",
    "def bstmax(root):\n",
    "    \"\"\"Return the (key, value) pair corresponding to the largest `key' in the bst.\"\"\"\n",
    "    \n",
    "    # Your code after this line.\n",
    "    \n",
    "def build_bst(alist):\n",
    "    \"\"\"Use the insert function to build a binary tree from a list of \n",
    "    (key, value) tuples.\"\"\"\n",
    "    root = None\n",
    "    for k, v in alist:\n",
    "        root = insert(root, k, v)\n",
    "    return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test cell. Do not modify!\n",
    "\n",
    "root1 = build_bst([(6, 10), (7, 2), (5, 13), (8, 8), (2, 5), (5, 14)])\n",
    "root2 = build_bst([(2, 5), (5, 14), (7, 2), (8, 8), (6, 10), (5, 13)])\n",
    "\n",
    "assert search(root1, 6) == [(6, 10)]\n",
    "assert search(root2, 2) == [(2, 5)]\n",
    "\n",
    "assert search(root1, 8) == [(6, 10), (7, 2), (8, 8)]\n",
    "assert search(root1, 2) == [(6, 10), (5, 13), (2, 5)]\n",
    "assert search(root2, 8) == [(2, 5), (5, 14), (7, 2), (8, 8)]\n",
    "assert search(root2, 6) == [(2, 5), (5, 14), (7, 2), (6, 10)]\n",
    "\n",
    "assert bstmin(root1) == (2, 5)\n",
    "assert bstmin(root2) == (2, 5)\n",
    "assert bstmax(root1) == (8, 8)\n",
    "assert bstmax(root2) == (8, 8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sorting using BST\n",
    "\n",
    "We can use BST for sorting by inserting the elements we need to sort into a BST and then doing a in-order traversal of the resulting tree."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bst_sort(alist):\n",
    "    \"\"\"Use Binary Search Tree for sorting.\n",
    "    Accepts a list of tuples of (key, value) as input.\n",
    "    Returns the list of tuples sorted according to the keys\"\"\"\n",
    "    \n",
    "    # Your code after this line.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Helper functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random as rnd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Do NOT modify this cell!\n",
    "\n",
    "# Helper functions\n",
    "\n",
    "def toss_coin(p=0.5):\n",
    "    r = rnd.random()\n",
    "    if r <= p:\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "\n",
    "def get_random_list(max_length=1000, min_length=0, key_start=0):\n",
    "    n = rnd.randint(min_length, max_length)\n",
    "    \n",
    "    values = list( range(n) )\n",
    "    rnd.shuffle( values )\n",
    "    \n",
    "    rls = []\n",
    "    \n",
    "    i = 0\n",
    "    while True:\n",
    "        # Toss a fair coin and decide whether to include this key or not.\n",
    "        if toss_coin():\n",
    "            rls.append( (key_start, values[i]) )\n",
    "            i += 1\n",
    "            \n",
    "            if i >= n:\n",
    "                break\n",
    "        \n",
    "        # Again toss a biased coin (p=0.9) to decide whether to increment the key.\n",
    "        if toss_coin(0.8):\n",
    "            key_start += 1\n",
    "            \n",
    "    rls2 = rls[:]\n",
    "    rnd.shuffle(rls2)\n",
    "    return rls2, rls\n",
    "    \n",
    "    \n",
    "def test_sort(sort_fn = None):\n",
    "    a = []\n",
    "    sort_fn(a)\n",
    "    assert a==[]\n",
    "\n",
    "    for i in range(10):\n",
    "        a, asorted = get_random_list(max_length=20, min_length=5, key_start=-10)\n",
    "        sort_fn(a)\n",
    "        assert [x[0] for x in a] == [x[0] for x in asorted]\n",
    "    \n",
    "\n",
    "    for i in range(5):\n",
    "        a, asorted = get_random_list(max_length=1000, min_length=100, key_start=-100)\n",
    "        sort_fn(a)\n",
    "        assert [x[0] for x in a] == [x[0] for x in asorted]\n",
    "        \n",
    "    print(\"Everything works!\")\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Do NOT modify this cell!\n",
    "\n",
    "# Test suit\n",
    "\n",
    "test_sort(sort_fn = bst_sort)"
   ]
  }
 ],
 "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
}