cviko_7/BVS.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BinarySearchNode:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        \n",
    "    def __str__(self):\n",
    "        strings = []\n",
    "        \n",
    "        # left subtree\n",
    "        if self.left is not None:\n",
    "            strings.append(str(self.left))\n",
    "        \n",
    "        # parent\n",
    "        strings.append(str(self.val))\n",
    "        \n",
    "        # right subtree\n",
    "        if self.right is not None:\n",
    "            strings.append(str(self.right))\n",
    "            \n",
    "        # join the string representations\n",
    "        return \", \".join(strings)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BinarySearchTree:\n",
    "    def __init__(self, root=None):\n",
    "        self.root = root\n",
    "        \n",
    "    def add_node(self, node):\n",
    "        # this function works both for BinarySearchNode and values\n",
    "        if not isinstance(node, BinarySearchNode):\n",
    "            node = BinarySearchNode(node)\n",
    "        \n",
    "        if self.root is None:\n",
    "            self.root = node\n",
    "            return\n",
    "        \n",
    "        curr = self.root\n",
    "        while True:\n",
    "            # we need to save this so that we know where to add the node\n",
    "            next_left = curr.val > node.val\n",
    "            \n",
    "            # this is the same as:\n",
    "            # if next_left:\n",
    "            #    next = curr.left\n",
    "            # else:\n",
    "            #    next = curr.right\n",
    "            next_node = curr.left if next_left else curr.right\n",
    "            \n",
    "            if next_node is None:\n",
    "                if next_left:\n",
    "                    curr.left = node\n",
    "                else:\n",
    "                    curr.right = node\n",
    "                return\n",
    "            \n",
    "            curr = next_node\n",
    "            \n",
    "    def find_node(self, value):\n",
    "        # TODO IMPLEMENT ME\n",
    "        \n",
    "        # implement method for finding a value in a binary search tree\n",
    "        # - if the value is present, return the node with the value\n",
    "        # - else return None\n",
    "        \n",
    "        # BONUS - modify add_node method to utilize your find_node\n",
    "        \n",
    "        return None\n",
    "    \n",
    "    def successor(self, value):\n",
    "        # TODO IMPLEMENT ME\n",
    "        \n",
    "        # implement method for finding the successor of the node with value\n",
    "        # you can utilize find_node\n",
    "    \n",
    "    def delete_node(self, value):\n",
    "        # TODO IMPLEMENT ME\n",
    "        \n",
    "        # implement node deletion\n",
    "        # HINT: use the successor\n",
    "        # HINT2: read wiki entry https://en.wikipedia.org/wiki/Binary_search_tree\n",
    "            \n",
    "    def __str__(self):\n",
    "        return str(self.root) if self.root is not None else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1, 3, 5, 10\n"
     ]
    }
   ],
   "source": [
    "bvs = BinarySearchTree()\n",
    "bvs.add_node(5)\n",
    "bvs.add_node(1)\n",
    "bvs.add_node(BinarySearchNode(3))\n",
    "bvs.add_node(10)\n",
    "print(bvs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 0, 8, 7, 7, 4, 3, 17, 2, 18]\n",
      "0, 2, 3, 3, 4, 7, 7, 8, 17, 18\n"
     ]
    }
   ],
   "source": [
    "# random numbers generator\n",
    "import random\n",
    "\n",
    "# this means I get the same value every time\n",
    "random.seed(42)\n",
    "\n",
    "limit = 20\n",
    "n_vals = 10\n",
    "some_numbers = [random.randint(0, limit - 1) for _ in range(n_vals)]\n",
    "print(some_numbers)\n",
    "\n",
    "bvs_sort = BinarySearchTree()\n",
    "\n",
    "for val in some_numbers:\n",
    "    bvs_sort.add_node(val)\n",
    "\n",
    "print(bvs_sort)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Alexander', 'Alphabet', 'Binary search tree', 'Coffee', 'Kernel', 'Kitten']\n",
      "Alexander, Alphabet, Binary search tree, Coffee, Kernel, Kitten\n"
     ]
    }
   ],
   "source": [
    "# lexicographic sort\n",
    "print(sorted([\"Alphabet\", \"Kitten\",\"Alexander\", \"Kernel\", \"Coffee\", \"Binary search tree\"]))\n",
    "\n",
    "bvs = BinarySearchTree()\n",
    "bvs.add_node(\"Alphabet\")\n",
    "bvs.add_node(\"Kitten\")\n",
    "bvs.add_node(\"Alexander\")\n",
    "bvs.add_node(\"Kernel\")\n",
    "bvs.add_node(\"Coffee\")\n",
    "bvs.add_node(\"Binary search tree\")\n",
    "print(bvs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": ".env",
   "language": "python",
   "name": ".env"
  },
  "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.8.10"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}