Data_Sructures.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyPUq+j0ok/RobHIdAWtsbFs",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/egbadon-victor/Data_Structures_and_Algorithms/blob/main/Data_Sructures.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**STACK DATA STRUCTURE**\n",
        "\n",
        "*   LIFO (Last In First Out) Property\n",
        "\n",
        "METHODS AVAILABLE\n",
        "*   PUSH function: Inserts an element at the top of the stack\n",
        "\n",
        "*   POP function: Removes an item from the top of the stack\n",
        "*   isEmpty : Checks whether the stack is empty\n",
        "\n",
        "*   isFull: Checks whether the stack is full\n",
        "*   peek: get the value at the top of the stack without replacing it\n",
        "\n",
        "IMPLEMENTATION ANALYSIS\n",
        "\n",
        "*   Push function: O(1) (Doesn't depend on the size of the stack)\n",
        "*   Pop function: O(1) (Doesn't depend on the lenght of the array since it removes just the last element)\n",
        "*   isEmpty / isFull: O(1) (The len() function does not iterate over the elements of the list to calculate. It retrieves the already precalculated value from the \\_\\_len__ property of the object.)\n",
        "*   Peek: O(1) Retrieves a single element despite the size of the stack\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n"
      ],
      "metadata": {
        "id": "mqCImLpkNA0W"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#Implementation\n",
        "class Stack:\n",
        "  def __init__(self,size):\n",
        "    self.stack = []\n",
        "    self.size = size\n",
        "    self.top = -1\n",
        "\n",
        "  def isEmpty(self):\n",
        "    if len(self.stack) == 0:\n",
        "      return True\n",
        "    return False\n",
        "\n",
        "  def isFull(self):\n",
        "    if len(self.stack) == self.size:\n",
        "      return True\n",
        "    return False\n",
        "\n",
        "  def push(self, item):\n",
        "    if self.isFull():\n",
        "      print(\"Stack Full\")\n",
        "      return\n",
        "    else:\n",
        "      self.top += 1\n",
        "      self.stack.append(item)\n",
        "      return self.stack\n",
        "\n",
        "  def pop(self):\n",
        "    if self.isEmpty():\n",
        "      print(\"Stack Empty\")\n",
        "      return\n",
        "    else:\n",
        "      removed_item = self.stack.pop(self.top)\n",
        "      self.top -= 1\n",
        "      return removed_item\n",
        "\n",
        "  def print(self):\n",
        "    print(self.stack)\n",
        "    return\n",
        "\n",
        "#Test cases\n",
        "s =  Stack(5)\n",
        "\n",
        "s.push(2)\n",
        "s.push(3)\n",
        "s.push(4)\n",
        "s.push(5)\n",
        "s.push(6)\n",
        "s.push(7)\n",
        "s.print()\n",
        "s.pop()\n",
        "s.pop()\n",
        "s.pop()\n",
        "s.pop()\n",
        "s.pop()\n",
        "s.pop()\n",
        "s.print()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "krwQ5B5rSXYF",
        "outputId": "1d9c919d-a4ba-48cd-965c-e494bceef324"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Stack Full\n",
            "[2, 3, 4, 5, 6]\n",
            "Stack Empty\n",
            "[]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**BASIC QUEUE DATA STRUCTURE**\n",
        "\n",
        "*   FIFO(First In First Out) property\n",
        "\n",
        "METHODS AVAILABLE\n",
        "\n",
        "*   Enqueue (Add an element to the end of the queue)\n",
        "*   Dequeue (Remove and element from the front of the queue)\n",
        "*   isEmpty (Checks whether the queue is empty)\n",
        "*   isFull (Checks whether the queue is full)\n",
        "*   Peek (Get the element at the front of the queue without removing it)\n",
        "\n",
        "IMPLEMENTATION ANALYSIS\n",
        "\n",
        "\n",
        "*   Enqueue - O(1). We are relying on the native append method of python lists which adds elements to the end of a list.\n",
        "*  Dequeue - O(n). Equivalent to removing an element from the front of a list. Therefore all the elements in the list will be shifted for evert dequeue.\n",
        "*   isEmpty O(1). *explanation given in stack implementation*\n",
        "*   peek: *explanation given in stack implementation*\n",
        "\n",
        "SIDE NOTES\n",
        "\n",
        "As observed, this is not the most efficient way to implement a queue in python.\n",
        "\n",
        "BETTER APPROACH\n",
        "\n",
        "Using Deque (Doubly Ended Queue) in python makes it such that insertion and deletion at both ends of the queue is O(1) time. You would probably prefer this method over any native implementation of a queue.\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n"
      ],
      "metadata": {
        "id": "lOtuWdiRqmjc"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#IMPLEMENTATION\n",
        "class Queue:\n",
        "  def __init__(self):\n",
        "    self.queue = []\n",
        "\n",
        "  def isEmpty(self):\n",
        "    return len(self.queue) == 0\n",
        "\n",
        "#Because of this basic implementation fo the queue,\n",
        "#there is no need for the isFull() method since we are relying on the inbuilt python lists.\n",
        "\n",
        "  def peek(self):\n",
        "    return self.queue[len(self.queue -1)]\n",
        "\n",
        "  def enqueue(self, item):\n",
        "    self.queue.append(item);\n",
        "    return self.queue\n",
        "\n",
        "  def dequeue(self):\n",
        "    if self.isEmpty():\n",
        "      print(\"Queue is already empty\")\n",
        "      return\n",
        "    return self.queue.pop(0)\n",
        "\n",
        "  def print(self):\n",
        "    print(self.queue)\n",
        "\n",
        "#test cases\n",
        "# q = Queue()\n",
        "# q.enqueue(2)\n",
        "# q.enqueue(3)\n",
        "# q.enqueue(4)\n",
        "# q.enqueue(5)\n",
        "# q.enqueue(6)\n",
        "# q.print()\n",
        "# q.dequeue()\n",
        "# q.print()\n",
        "# q.dequeue()\n",
        "# q.print()\n",
        "\n",
        "#MORE EFFICIENT IMPLEMENTATION\n",
        "from collections import deque\n",
        "\n",
        "q2 = deque([1,2,3])\n",
        "print(q2)\n",
        "q2.append(4)\n",
        "print(q2)\n",
        "q2.pop()\n",
        "print(q2)\n",
        "\n",
        "'''\n",
        "I'd stop here but you get the point.\n",
        "You can check deque in the geek for geeks site for a detailed documentation.\n",
        "'''"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ZtEzDmdAuf98",
        "outputId": "70a541ef-9a96-4b4d-ec21-fc85d732825f"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "deque([1, 2, 3])\n",
            "deque([1, 2, 3, 4])\n",
            "deque([1, 2, 3])\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**CIRCULAR QUEUE**\n",
        "\n",
        "Same mechanics as a normal queue with some improvements.\n",
        "A queue would need  to be reset anytime the front pointer is not at the beginning of the array(imagine this as the space reserved for the queue in memory). A circular queue avoids this by allowing the rear pointer to go to the start of the array."
      ],
      "metadata": {
        "id": "9kJ0GZ0tnjVh"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#IMPLEMENTATION\n",
        "\n",
        "class CircularQueue:\n",
        "  def __init__(self, size):\n",
        "    self.queue = [None] * size\n",
        "    self.size = size\n",
        "    self.head = self.tail = -1\n",
        "\n",
        "  def isEmpty(self):\n",
        "    if (self.head == self.tail == -1):\n",
        "      return True\n",
        "    else:\n",
        "      return False\n",
        "\n",
        "  def isFull(self):\n",
        "    if(self.head == 0 and self.tail == self.size -1):\n",
        "      return True\n",
        "    elif(self.head == self.tail + 1):\n",
        "      return True\n",
        "    else:\n",
        "      return False\n",
        "\n",
        "  def enqueue(self, item):\n",
        "    if(self.isFull()):\n",
        "      print(\"Queue is already full\")\n",
        "      return 0\n",
        "\n",
        "    if (self.isEmpty()):\n",
        "      self.head = self.tail = 0\n",
        "      self.queue[self.tail] = item\n",
        "      return 1\n",
        "\n",
        "    self.tail = (self.tail + 1) % self.size\n",
        "    self.queue[self.tail] = item\n",
        "    return 1\n",
        "\n",
        "  def dequeue(self):\n",
        "    if(self.isEmpty()):\n",
        "      print(\"Queue is already empty\")\n",
        "      return 0\n",
        "\n",
        "    temp = self.queue[self.head]\n",
        "    self.queue[self.head] = None\n",
        "    self.head = (self.head +1) % self.size\n",
        "    return temp\n",
        "\n",
        "  def printq(self):\n",
        "    i = self.head\n",
        "    temp =[]\n",
        "\n",
        "    if(self.isEmpty()):\n",
        "      print(temp)\n",
        "      return 0\n",
        "\n",
        "\n",
        "    while(self.queue[i] != None and len(temp) != self.size):\n",
        "      temp.append(self.queue[i])\n",
        "      i = (i + 1) % self.size\n",
        "    print(temp)\n",
        "    return 1\n",
        "\n",
        "\n",
        "\n",
        "obj = CircularQueue(5)\n",
        "obj.enqueue(1)\n",
        "obj.enqueue(2)\n",
        "obj.enqueue(3)\n",
        "obj.enqueue(4)\n",
        "obj.enqueue(5)\n",
        "obj.enqueue(5)\n",
        "print(\"Initial queue\")\n",
        "obj.printq()\n",
        "\n",
        "obj.dequeue()\n",
        "obj.dequeue()\n",
        "print(\"After removing an element from the queue\")\n",
        "obj.printq()\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "hG8VjEfZp16G",
        "outputId": "37cc94f4-4ed0-4687-c432-71d40537f866"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Queue is already full\n",
            "Initial queue\n",
            "[1, 2, 3, 4, 5]\n",
            "After removing an element from the queue\n",
            "[3, 4, 5]\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "1"
            ]
          },
          "metadata": {},
          "execution_count": 27
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**SIMPLE LINKED LIST**\n",
        "\n",
        "DESCRIPTION\n",
        "\n",
        "\n",
        "*   Each node in the linked list is connected in one dimension\n",
        "*   Each node contains it's value, as well as a pointer to the next node.\n",
        "*   Insertion is O(1). Same with deletion. Search is O(n)\n",
        "\n",
        "\n",
        "OPERATIONS\n",
        "*   Traversal - Going through all the elements of the linked List\n",
        "*   Search - Retrieve a specified element from the linked list\n",
        "*   Insertion - Insert an item into the linked list\n",
        "*   Deletion - Remove an item from the linked list\n",
        "*   Sort - Change the order of the liked list based on specified conditions"
      ],
      "metadata": {
        "id": "pafn6d3gu8XU"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#IMPLEMENTATION\n",
        "\n",
        "class Node:\n",
        "  def __init__(self,data):\n",
        "    self.data = data\n",
        "    self.next = None\n",
        "\n",
        "class LinkedList:\n",
        "  def __init__(self):\n",
        "    self.head = None\n",
        "\n",
        "  def insertAtBeginning(self, data):\n",
        "    data_node = Node(data)\n",
        "\n",
        "    if self.head == None :\n",
        "      self.head = data_node\n",
        "    else:\n",
        "      temp = self.head\n",
        "      self.head = data_node\n",
        "      data_node.next = temp\n",
        "\n",
        "  def insertAtEnd(self, data):\n",
        "    data_node = Node(data)\n",
        "\n",
        "    if self.head == None:\n",
        "      self.head = data_node\n",
        "      return 0\n",
        "\n",
        "    last_node = self.head\n",
        "\n",
        "    while(last_node.next):\n",
        "      last_node = last_node.next\n",
        "\n",
        "    last_node.next = data_node\n",
        "\n",
        "  def insertAfter(self,data,index):\n",
        "\n",
        "    i = 0\n",
        "    new_node = Node(data)\n",
        "    current_node = self.head\n",
        "\n",
        "    for i in range(index):\n",
        "      if current_node is None:\n",
        "        print(\"Given index not in the list\")\n",
        "        return\n",
        "      else:\n",
        "        current_node = current_node.next\n",
        "\n",
        "    temp = current_node.next\n",
        "    current_node.next = new_node\n",
        "    new_node.next = temp\n",
        "\n",
        "\n",
        "  def deleteNode(self, position):\n",
        "\n",
        "    if self.head is None:\n",
        "      print(\"Linked List is already empty\")\n",
        "      return\n",
        "\n",
        "    temp = self.head\n",
        "    if position == 0:\n",
        "      self.head = temp.next\n",
        "      temp = None\n",
        "      return\n",
        "\n",
        "    for i in range(position - 1):\n",
        "      temp = temp.next\n",
        "      if temp is None:\n",
        "        break\n",
        "\n",
        "    if temp is None:\n",
        "        return\n",
        "\n",
        "    if temp.next is None:\n",
        "        return\n",
        "\n",
        "    next = temp.next.next\n",
        "\n",
        "    temp.next = None\n",
        "\n",
        "    temp.next = next\n",
        "\n",
        "  def print(self):\n",
        "\n",
        "    output=[]\n",
        "    curr_node =  self.head\n",
        "\n",
        "    while curr_node:\n",
        "      output.append(curr_node.data)\n",
        "      curr_node = curr_node.next\n",
        "\n",
        "    print(output)\n",
        "\n",
        "\n",
        "\n",
        "l = LinkedList()\n",
        "\n",
        "l.insertAtEnd(1)\n",
        "l.insertAtEnd(2)\n",
        "l.insertAtEnd(3)\n",
        "l.print()\n",
        "# l.deleteNode(1)\n",
        "# l.print()\n",
        "l.insertAtBeginning(4)\n",
        "l.print()\n",
        "l.insertAfter(5,1)\n",
        "l.print()\n",
        "l.deleteNode(4)\n",
        "\n",
        "l.print()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "qLMW005bxrd7",
        "outputId": "9723e0ce-1af3-4463-9ab4-88f7ea10b4ce"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[1, 2, 3]\n",
            "[4, 1, 2, 3]\n",
            "[4, 1, 5, 2, 3]\n",
            "[4, 1, 5, 2]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**DOUBLY LINKED LIST**\n",
        "\n",
        "DESCRIPTION\n",
        "\n",
        "*   There is a previous pointer that points to the previous node in the Linked List\n",
        "*   Allows traversing of the Linked Lust in both forward and backward directions\n",
        "*   Shares the same methods and foundational implementation with the Singly Linked List."
      ],
      "metadata": {
        "id": "00d07WYJJjam"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#IMPLEMENTATION\n",
        "\n",
        "class Node:\n",
        "  def __init__(self,data):\n",
        "    self.data = data\n",
        "    self.next = self.prev = None\n",
        "\n",
        "\n",
        "class DoublyLinkedList:\n",
        "  def __init__(self):\n",
        "    self.head = None\n",
        "\n",
        "\n",
        "  def insertAtBeginning(self, data):\n",
        "    data_node = Node(data)\n",
        "\n",
        "    if self.head == None :\n",
        "      self.head = data_node\n",
        "      return\n",
        "\n",
        "\n",
        "    temp = self.head\n",
        "    self.head = None\n",
        "    self.head = data_node\n",
        "    self.head.next = temp\n",
        "    temp.prev = self.head\n",
        "\n",
        "\n",
        "  def insertAtEnd(self, data):\n",
        "    data_node = Node(data)\n",
        "\n",
        "    if self.head == None:\n",
        "      self.head = data_node\n",
        "      return 0\n",
        "\n",
        "    last_node = self.head\n",
        "\n",
        "    while(last_node.next):\n",
        "      last_node = last_node.next\n",
        "\n",
        "    last_node.next = data_node\n",
        "    data_node.prev = last_node\n",
        "\n",
        "\n",
        "  def insertAfter(self,data,index):\n",
        "\n",
        "    i = 0\n",
        "    new_node = Node(data)\n",
        "    current_node = self.head\n",
        "\n",
        "    for i in range(index):\n",
        "      if current_node is None:\n",
        "        print(\"Given index not in the list\")\n",
        "        return\n",
        "      else:\n",
        "        current_node = current_node.next\n",
        "\n",
        "    temp = current_node.next\n",
        "    current_node.next = new_node\n",
        "    new_node.prev = current_node\n",
        "    new_node.next = temp\n",
        "    temp.prev = new_node\n",
        "\n",
        "\n",
        "  def deleteNode(self, position):\n",
        "\n",
        "    if self.head is None:\n",
        "      print(\"Linked List is already empty\")\n",
        "      return\n",
        "\n",
        "    temp = self.head\n",
        "    if position == 0:\n",
        "      self.head = temp.next\n",
        "      self.head.prev = None\n",
        "      temp = None\n",
        "      return\n",
        "\n",
        "    for i in range(position - 1):\n",
        "      temp = temp.next\n",
        "      if temp is None:\n",
        "        break\n",
        "\n",
        "    if temp is None:\n",
        "        return\n",
        "\n",
        "    if temp.next is None:\n",
        "        return\n",
        "\n",
        "    next = temp.next.next\n",
        "\n",
        "    temp.next = None\n",
        "\n",
        "    temp.next = next\n",
        "    next.prev = temp\n",
        "\n",
        "  def print(self):\n",
        "\n",
        "    output=[]\n",
        "    curr_node =  self.head\n",
        "\n",
        "    while curr_node:\n",
        "      output.append(curr_node.data)\n",
        "      curr_node = curr_node.next\n",
        "\n",
        "    print(output)\n"
      ],
      "metadata": {
        "id": "gZyvZhJjKJWU"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "**HASH TABLE**\n",
        "\n",
        "*   This Data structure stores data in Key, value pairs.\n",
        "*   When inserted into the hash table, the key is hashed by a hasing function, and then used to store the value in the memory.\n",
        "*   At first, it does not make sense to hash the key, since the key itself is already unique. But hashing is important because hashing converts the key to an index in the array that is actually used to model this hash table. Hence, the need.\n",
        "\n",
        "\n",
        "There are various methods to resolve hash collisions. They are as follows\n",
        "\n",
        "\n",
        "1.   Chaining: If multiple keys hash to the same address, the multiple items are stored in a doubly linked list or a regular list at that same address.\n",
        "2.   Open Addressing: Here, multiple items are not stored in the same index. Instead, you would have to try another address for availability. There are ways in which you probe for a free address.\n",
        "\n",
        "  *   Linear probing: If a key hashed to an address that has been occupied, you increment to address index by 1 and try again until you have found a free address.\n",
        "  *   Quadratic probing: Similar to the Linear probing. But instead of increasing the index by 1, you increase it by value generated by a quadratic function of the form c1 + c2 i ^ 2\n",
        "  *   Double hashing:If a collision applies after applying a hash function, a second hash function is calculated to get another address.\n",
        "\n",
        "\n",
        "\n"
      ],
      "metadata": {
        "id": "3-ik3wB8WUkV"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "result = []\n",
        "for i in range(100):\n",
        "  lesser = 6 * i -1\n",
        "  greater = 6 * i + 1\n",
        "  result.append(lesser)\n",
        "  result.append( greater)\n",
        "print(result)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "elTC9b7hl1Rl",
        "outputId": "8511e869-4633-484e-94c2-325cd6086b9a"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[-1, 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97, 101, 103, 107, 109, 113, 115, 119, 121, 125, 127, 131, 133, 137, 139, 143, 145, 149, 151, 155, 157, 161, 163, 167, 169, 173, 175, 179, 181, 185, 187, 191, 193, 197, 199, 203, 205, 209, 211, 215, 217, 221, 223, 227, 229, 233, 235, 239, 241, 245, 247, 251, 253, 257, 259, 263, 265, 269, 271, 275, 277, 281, 283, 287, 289, 293, 295, 299, 301, 305, 307, 311, 313, 317, 319, 323, 325, 329, 331, 335, 337, 341, 343, 347, 349, 353, 355, 359, 361, 365, 367, 371, 373, 377, 379, 383, 385, 389, 391, 395, 397, 401, 403, 407, 409, 413, 415, 419, 421, 425, 427, 431, 433, 437, 439, 443, 445, 449, 451, 455, 457, 461, 463, 467, 469, 473, 475, 479, 481, 485, 487, 491, 493, 497, 499, 503, 505, 509, 511, 515, 517, 521, 523, 527, 529, 533, 535, 539, 541, 545, 547, 551, 553, 557, 559, 563, 565, 569, 571, 575, 577, 581, 583, 587, 589, 593, 595]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "#HASH TABLE WITH CHAINING\n",
        "\n",
        "class HashTableChaining:\n",
        "    def __init__(self, size=100):\n",
        "        self.size = size\n",
        "        self.table = [[] for _ in range(size)]\n",
        "\n",
        "    def _hash(self, key):\n",
        "        return hash(key) % self.size\n",
        "\n",
        "    def insert(self, key, value):\n",
        "        index = self._hash(key)\n",
        "        for kvp in self.table[index]:\n",
        "            if kvp[0] == key:\n",
        "                kvp[1] = value\n",
        "                return\n",
        "        self.table[index].append([key, value])\n",
        "\n",
        "    def retrieve(self, key):\n",
        "        index = self._hash(key)\n",
        "        for kvp in self.table[index]:\n",
        "            if kvp[0] == key:\n",
        "                return kvp[1]\n",
        "        return None\n",
        "\n",
        "print(\"Hash Table - Linear chaining\")\n",
        "hash_table = HashTableChaining()\n",
        "hash_table.insert('apple', 'fruit')\n",
        "hash_table.insert('carrot', 'vegetable')\n",
        "print(hash_table.retrieve('apple'))\n",
        "print(hash_table.retrieve('carrot'))\n",
        "\n",
        "\n",
        "#HASH TABLE WITH LINEAR PROBING\n",
        "class HashTableLinearProbing:\n",
        "    def __init__(self, size=100):\n",
        "        self.size = size\n",
        "        self.table = [None] * size\n",
        "\n",
        "    def _hash(self, key):\n",
        "        return hash(key) % self.size\n",
        "\n",
        "    def insert(self, key, value):\n",
        "        index = self._hash(key)\n",
        "        original_index = index\n",
        "        while self.table[index] is not None:\n",
        "            if self.table[index][0] == key:\n",
        "                self.table[index] = (key, value)\n",
        "                return\n",
        "            index = (index + 1) % self.size\n",
        "            if index == original_index:\n",
        "                raise Exception(\"Hash table is full\")\n",
        "        self.table[index] = (key, value)\n",
        "\n",
        "    def retrieve(self, key):\n",
        "        index = self._hash(key)\n",
        "        original_index = index\n",
        "        while self.table[index] is not None:\n",
        "            if self.table[index][0] == key:\n",
        "                return self.table[index][1]\n",
        "            index = (index + 1) % self.size\n",
        "            if index == original_index:\n",
        "                return None\n",
        "        return None\n",
        "\n",
        "\n",
        "print(\"Hash Table - Linear Probing\")\n",
        "hash_table = HashTableLinearProbing()\n",
        "hash_table.insert('apple', 'fruit')\n",
        "hash_table.insert('carrot', 'vegetable')\n",
        "print(hash_table.retrieve('apple'))\n",
        "print(hash_table.retrieve('carrot'))\n",
        "\n",
        "\n",
        "#HASH TABLE WITH QUADRATIC PROBING\n",
        "class HashTableQuadraticProbing:\n",
        "    def __init__(self, size=100, c1=1, c2=3):\n",
        "        self.size = size\n",
        "        self.table = [None] * size\n",
        "        self.c1 = c1\n",
        "        self.c2 = c2\n",
        "\n",
        "    def _hash(self, key):\n",
        "        return hash(key) % self.size\n",
        "\n",
        "    def quad_func(self, i, index):\n",
        "      return (index + self.c1 * i + self.c2 * i * i) % self.size\n",
        "\n",
        "    def insert(self, key, value):\n",
        "        index = self._hash(key)\n",
        "        i = 0\n",
        "        while self.table[self.quad_func(i, index)] is not None:\n",
        "            if self.table[self.quad_func(i, index)][0] == key:\n",
        "                self.table[self.quad_func(i, index)] = (key, value)\n",
        "                return\n",
        "            i += 1\n",
        "        self.table[self.quad_func(i, index)] = (key, value)\n",
        "\n",
        "    def retrieve(self, key):\n",
        "        index = self._hash(key)\n",
        "        i = 0\n",
        "        while self.table[self.quad_func(i, index)] is not None:\n",
        "            if self.table[self.quad_func(i, index)][0] == key:\n",
        "                return self.table[self.quad_func(i, index)][1]\n",
        "            i += 1\n",
        "        return None\n",
        "\n",
        "print(\"Hash Table - Quadratic Probing\")\n",
        "hash_table = HashTableQuadraticProbing()\n",
        "hash_table.insert('apple', 'fruit')\n",
        "hash_table.insert('carrot', 'vegetable')\n",
        "print(hash_table.retrieve('apple'))\n",
        "print(hash_table.retrieve('carrot'))\n",
        "\n",
        "#DOUBLE HASHING\n",
        "class HashTableDoubleHashing:\n",
        "    def __init__(self, size=100):\n",
        "        self.size = size\n",
        "        self.table = [None] * size\n",
        "\n",
        "    def _hash1(self, key):\n",
        "        return hash(key) % self.size\n",
        "\n",
        "    def _hash2(self, key):\n",
        "        return 1 + (hash(key) % (self.size - 1))\n",
        "\n",
        "    def insert(self, key, value):\n",
        "        index = self._hash1(key)\n",
        "        step = self._hash2(key)\n",
        "        original_index = index\n",
        "        i = 0\n",
        "        while self.table[index] is not None:\n",
        "            if self.table[index][0] == key:\n",
        "                self.table[index] = (key, value)\n",
        "                return\n",
        "            index = (original_index + i * step) % self.size\n",
        "            if index == original_index:\n",
        "                raise Exception(\"Hash table is full\")\n",
        "            i += 1\n",
        "        self.table[index] = (key, value)\n",
        "\n",
        "    def retrieve(self, key):\n",
        "        index = self._hash1(key)\n",
        "        step = self._hash2(key)\n",
        "        original_index = index\n",
        "        i = 0\n",
        "        while self.table[index] is not None:\n",
        "            if self.table[index][0] == key:\n",
        "                return self.table[index][1]\n",
        "            index = (original_index + i * step) % self.size\n",
        "            if index == original_index:\n",
        "                return None\n",
        "            i += 1\n",
        "        return None\n",
        "\n",
        "# Usage\n",
        "print(\"Hash Table - Double Hashing\")\n",
        "hash_table = HashTableDoubleHashing()\n",
        "hash_table.insert('apple', 'fruit')\n",
        "hash_table.insert('carrot', 'vegetable')\n",
        "print(hash_table.retrieve('apple'))  # Outputs: fruit\n",
        "print(hash_table.retrieve('carrot'))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "iY7R2YT-l4Lr",
        "outputId": "79b2b1f1-d5b1-4847-bd26-a960f6d478fe"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Hash Table - Linear chaining\n",
            "fruit\n",
            "vegetable\n",
            "Hash Table - Linear Probing\n",
            "fruit\n",
            "vegetable\n",
            "Hash Table - Quadratic Probing\n",
            "fruit\n",
            "vegetable\n",
            "Hash Table - Double Hashing\n",
            "fruit\n",
            "vegetable\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**HEAP DATA STRUCTURE**\n",
        "\n",
        "This is a complete binary tree in which the parent node is always greater than the child node (max heap property), or vice versa(min heap property).\n",
        "\n",
        "KEY INFO\n",
        "*   Left child of a node i = 2i + 1\n",
        "*   Right child of a node i = 2i + 2\n",
        "*   Largest/smallest element = root of max heap/min heap respectively\n",
        "\n",
        "METHODS\n",
        "*   Heapify: Create a heap from a binary trees\n",
        "*   Insert: Add an element to the heap\n",
        "*   Delete: Remove an element from the heap\n",
        "*   Peek: find the max or min element (for max heap and min heap respectively)"
      ],
      "metadata": {
        "id": "S35itSWoOIT-"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#HEAP IMPLEMENTATION\n",
        "\n",
        "class Heap:\n",
        "  def __init__(self):\n",
        "    self.heap=[]\n",
        "\n",
        "  def heapify(self, index):\n",
        "\n",
        "    largest = index\n",
        "    left = (2 * index) + 1\n",
        "    right = (2 * index) + 2\n",
        "\n",
        "    if left < len(self.heap) and self.heap[left] > self.heap[largest]:\n",
        "      largest = left\n",
        "\n",
        "    if right < len(self.heap) and self.heap[right] > self.heap[largest]:\n",
        "      largest = right\n",
        "\n",
        "    if largest is not index:\n",
        "      self.heap[largest], self.heap[index] = self.heap[index], self.heap[largest]\n",
        "      self.heapify(largest)\n",
        "\n",
        "  def insert(self, element):\n",
        "\n",
        "    self.heap.append(element)\n",
        "    last_non_leaf_node = len(self.heap)//2 - 1\n",
        "\n",
        "    for i in range (last_non_leaf_node, -1, -1):\n",
        "      self.heapify(i)\n",
        "\n",
        "  def delete(self, index):\n",
        "\n",
        "    left = 2 * index + 1\n",
        "    right = 2 * index + 2\n",
        "    size = len(self.heap)\n",
        "    last_non_leaf_node = len(self.heap)//2 - 1\n",
        "\n",
        "    if index >= size:\n",
        "      print(\"Element does not exist at this position\")\n",
        "      return\n",
        "\n",
        "    if left >= size:\n",
        "      self.heap.pop(index)\n",
        "      return\n",
        "\n",
        "    else:\n",
        "      self.heap[index], self.heap[ size - 1] = self.heap[size - 1], self.heap[index]\n",
        "      self.heap.pop()\n",
        "      for i in range (last_non_leaf_node, -1, -1):\n",
        "        self.heapify(i)\n",
        "\n",
        "  def print(self):\n",
        "    print(self.heap)\n",
        "\n",
        "\n",
        "heap = Heap()\n",
        "\n",
        "heap.insert(1)\n",
        "heap.insert(3)\n",
        "heap.insert(4)\n",
        "heap.insert(5)\n",
        "heap.insert(10)\n",
        "heap.insert(7)\n",
        "heap.print()\n",
        "heap.delete(0)\n",
        "heap.print()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "l1P2Q0U2ssJb",
        "outputId": "1db5d299-3443-455c-f0c4-7c26e97fce91"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[10, 5, 7, 1, 4, 3]\n",
            "[7, 5, 3, 1, 4]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**TREE DATA STRUCTURE**\n",
        "\n",
        "CHARACTERISTICS\n",
        "*   Non-linear data structure\n",
        "*   It consists of nodes connected by edges\n",
        "*   Edge: A link between any two nodes\n",
        "*   Root: Topmost node in a tree\n",
        "*   Depth of a node: Number of edges from the root node to that node\n",
        "*   Height of the tree: Number of edges from the deepest leaf of the tree to the root of the node.\n",
        "*   Height of a node: Number of edges from the node to the deepest leaf in the tree\n",
        "*   Degree of a node: This is the number of children that a node has.\n",
        "\n",
        "TREE TRAVERSAL\n",
        "\n",
        "This means visiting every node in the tree. There are tree main ways to do so.\n",
        "\n",
        "1.   Depth-first search(DFS): You traverse the branches of the tree, getting to the deepest node, before moving to another branch. You do so recursively until all branches are visited.\n",
        "\n",
        "*   Inorder: You visit the root node first, then the left, and then the right node\n",
        "*   Preorder: You visit the left node first, then the root and then the right node.\n",
        "*   Postorder: You visit the left node first, then the right, then the root node\n",
        "\n",
        "2.   Breadth-first search(BFS): You traverse all the nodes at the same level before going deeper in the tree. You do this until all nodes have been traversed."
      ],
      "metadata": {
        "id": "w7kVDBTwvfYo"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#IMPLEMENTATION OF TREE TRAVERSAL\n",
        "\n",
        "#Note that this implementation is for a binary tree traversal\n",
        "\n",
        "class Node:\n",
        "    def __init__(self, item):\n",
        "        self.left = None\n",
        "        self.right = None\n",
        "        self.val = item\n",
        "\n",
        "def in_order(root):\n",
        "\n",
        "  if root:\n",
        "    in_order(root.left)\n",
        "    print(str(root.val), end=\", \")\n",
        "    in_order(root.right)\n",
        "\n",
        "def pre_order(root):\n",
        "  if root:\n",
        "    print(str(root.val), end=\", \")\n",
        "    pre_order(root.left)\n",
        "    pre_order(root.right)\n",
        "\n",
        "def post_order(root):\n",
        "  if root:\n",
        "    post_order(root.left)\n",
        "    post_order(root.right)\n",
        "    print(str(root.val), end=\", \")\n",
        "\n",
        "\n",
        "root = Node(4)\n",
        "root.left = Node(2)\n",
        "root.right = Node(5)\n",
        "root.left.left = Node(1)\n",
        "root.left.right = Node(3)\n",
        "\n",
        "print(\"Inorder traversal \")\n",
        "in_order(root)\n",
        "\n",
        "print(\"\\nPreorder traversal \")\n",
        "pre_order(root)\n",
        "\n",
        "print(\"\\nPostorder traversal \")\n",
        "post_order(root)\n",
        "\n",
        "\n",
        "\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "P-wTeJbDvg2x",
        "outputId": "7cd1e217-bec9-4160-c315-c9848900fb50"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Inorder traversal \n",
            "1, 2, 3, 4, 5, \n",
            "Preorder traversal \n",
            "4, 2, 1, 3, 5, \n",
            "Postorder traversal \n",
            "1, 3, 2, 5, 4, "
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**BINARY TREE**\n",
        "\n",
        "CHARACTERISTICS\n",
        "*   This is a tree structure with a maximum of 2 children per node.\n",
        "\n",
        "TYPES OF BINARY TREE\n",
        "\n",
        "1.   Full Binary Tree: This is a special type of binary tree in which each internal node has either 2 or 0 children.\n",
        "2.   Perfect Binary Tree: This is a type of binary tree in which all internal node has 2 children and all the leaf nodes are on the same level.\n",
        "3.   Complete Binary tree: A complete binary tree is similar to a full binary tree with the following differences.\n",
        "   *   Every level must be completely filled\n",
        "   *   All leaf elements must lean towards the left\n",
        "   *   The last element may not necessarily have a right sibling\n",
        "4.   Degenerate/pathological Binary tree: This is a binary tree in which the internal nodes have only one child, either left or right.\n",
        "5.   Skewed Binary tree: A pathological binary tree with one dominating direction\n",
        "6.   Balanced Binary tree: Here, the difference in height of the left and right nodes in the tree must be either 0 or 1.\n",
        "\n",
        "\n",
        "FULL BINARY TREE\n",
        "\n",
        "Assuming,\n",
        "\n",
        "  i = number of internal nodes\n",
        "\n",
        "  n = total number of nodes\n",
        "\n",
        "  l = number of leaves\n",
        "\n",
        "  λ = number of levels\n",
        "\n",
        "1.   Number of leaves, l = i + 1 = (n + 1) / 2\n",
        "2.   Total number of nodes, n = 2i + 1 = 2l - 1\n",
        "3.   Number of internal nodes, i = (n - 1) / 2\n",
        "4.   Max number of leaves = 2 ^ (λ - 1)\n",
        "\n",
        "\n",
        "PERFECT BINARY TREE\n",
        "\n",
        "Here, all the leaf nodes are on the same level. I would like to think of it as if the tree were completely filled. (TBH this would be my defination of a full binary tree but oh well 😂)\n",
        "\n",
        "Using the name variable convention as in the full binary tree\n",
        "\n",
        "1.   Number of leaf nodes, l = 2 ^ h\n",
        "2.   Total number of nodes, n = (2 ^ h) - 1\n",
        "\n",
        "\n",
        "COMPLETE BINARY TREE\n",
        "\n",
        "A complete binary tree is a kind of binary tree in which all the levels are full except possibly the last one, which is filled in from the left. I would love to think of this as an orderly binary tree, where the elements are filled in level by level, from left to right. Therefore a complete binary tree is almost always skewed to the left, except its perfect.\n",
        "\n",
        "The most important relationships for checking this is:\n",
        "\n",
        "1.   index of Left child of a node, l = i * 2 + 1,\n",
        "2.   index of Right child of a node, l = i * 2 + 2,\n",
        "\n",
        "where i is the index of the parent element. Changing the subject of the formula gives the formular for getting the parent element when givent the left or right child.\n",
        "\n",
        "\n",
        "\n",
        "BALANCED BINARY TREE\n",
        "\n",
        "A balanced binary tree is one in which the difference between the right and left subtree of the node is not more than 1.\n",
        "\n",
        "Keynotes:\n",
        "\n",
        "1.   The height of a node is the height of max (height(left_node), height(right_node)) + 1\n",
        "\n",
        "\n",
        "BINARY SEARCH TREE\n",
        "\n",
        "This is a binary tree that is arranged in such a way that the left node must be lesser than the root node and the right node must be greater than the root node. This must apply for all nodes in the binary tree ( that is both the left and right nodes are also BSTs )\n",
        "\n",
        "OPERATIONS\n",
        "\n",
        "1.   Search: Retrieve a specified element from the BST\n",
        "2.   Insert: Add an element to the BST\n",
        "3.   Delete: Remove an element from the BST\n",
        "\n",
        "\n"
      ],
      "metadata": {
        "id": "uSYqXHT0NQcD"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#IMPLEMENTATION OF FULL BINARY TREE\n",
        "\n",
        "class Node:\n",
        "  def __init__(self, data):\n",
        "    self.left = None\n",
        "    self.right = None\n",
        "    self.data = data\n",
        "\n",
        "def isFullTree(root):\n",
        "\n",
        "  if root is None:\n",
        "    return True\n",
        "\n",
        "  if root.left is None and root.right is None:\n",
        "    return True\n",
        "\n",
        "  if root.left is not None and root.right is not None:\n",
        "    return (isFullTree(root.left) and isFullTree(root.right))\n",
        "\n",
        "  return False\n",
        "\n",
        "\n",
        "root = Node(1)\n",
        "root.right = Node(3)\n",
        "root.left = Node(2)\n",
        "\n",
        "root.left.left = Node(4)\n",
        "root.left.right = Node(5)\n",
        "root.left.right.left = Node(6)\n",
        "root.left.right.right = Node(7)\n",
        "\n",
        "print(isFullTree(root))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "fZKqafnHTbhd",
        "outputId": "8c47dd66-3e73-430b-b3a1-b9617c46a211"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "True\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# PERFECT BINARY TREE\n",
        "\n",
        "class Node:\n",
        "  def __init__(self, data):\n",
        "    self.left = None\n",
        "    self.right = None\n",
        "    self.data = data\n",
        "\n",
        "\n",
        "def calculateDepth(node):\n",
        "   d = 0\n",
        "   while node is not None:\n",
        "    d += 1\n",
        "    node = node.left\n",
        "   return d\n",
        "\n",
        "def isPerfectTree(root, depth, level=0):\n",
        "\n",
        "  if root is None:\n",
        "    return True\n",
        "\n",
        "  if root.left is None and root.right is None:\n",
        "    return depth == level + 1\n",
        "\n",
        "  if root.left is None or root.right is None:\n",
        "    return False\n",
        "\n",
        "  return (isPerfectTree(root.left, depth, level + 1) and isPerfectTree(root.right, depth, level + 1))\n",
        "\n",
        "\n",
        "root = Node(1)\n",
        "root.right = Node(3)\n",
        "root.left = Node(2)\n",
        "\n",
        "root.left.left = Node(4)\n",
        "root.left.right = Node(5)\n",
        "root.right.left = Node(6)\n",
        "root.right.right = Node(7)\n",
        "\n",
        "\n",
        "if (isPerfectTree(root, calculateDepth(root))):\n",
        "    print(\"The tree is a perfect binary tree\")\n",
        "else:\n",
        "    print(\"The tree is not a perfect binary tree\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ehGTHRFpUsyn",
        "outputId": "d485cbe2-6532-4a82-eefc-4ed37a8a1647"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The tree is a perfect binary tree\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# COMPLETE BINARY TREE\n",
        "\n",
        "class Node:\n",
        "  def __init__(self, data):\n",
        "    self.left = None\n",
        "    self.right = None\n",
        "    self.data = data\n",
        "\n",
        "def calculateNodesNumber(root):\n",
        "\n",
        "  if root is None:\n",
        "    return 0\n",
        "\n",
        "  return (1 + calculateNodesNumber(root.left) + calculateNodesNumber(root.right))\n",
        "\n",
        "\n",
        "def isCompleteTree(root, i, n):\n",
        "\n",
        "  if root is None:\n",
        "    return True\n",
        "\n",
        "  if i >= n:\n",
        "    return False\n",
        "\n",
        "  return (isCompleteTree(root.left, 2 * i + 1, n) and isCompleteTree(root.right, 2 * i + 2, n))\n",
        "\n",
        "\n",
        "\n",
        "root = Node(1)\n",
        "root.right = Node(3)\n",
        "root.left = Node(2)\n",
        "\n",
        "root.left.left = Node(4)\n",
        "root.left.right = Node(5)\n",
        "root.right.left = Node(6)\n",
        "root.right.right = Node(7)\n",
        "\n",
        "nodeCount = calculateNodesNumber(root)\n",
        "\n",
        "if isCompleteTree(root,0, nodeCount):\n",
        "    print(\"The tree is a complete binary tree\")\n",
        "else:\n",
        "    print(\"The tree is not a complete binary tree\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "aKbTahzLJPC_",
        "outputId": "576c0803-f79b-436c-9472-3b1001267b96"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The tree is not a complete binary tree\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "#BALANCED BINARY TREE\n",
        "\n",
        "class Node:\n",
        "    def __init__(self, data):\n",
        "        self.left = None\n",
        "        self.right = None\n",
        "        self.data = data\n",
        "\n",
        "def check_height_and_balance(node):\n",
        "    \"\"\"Check the height and balance of the binary tree in one traversal.\"\"\"\n",
        "    if node is None:\n",
        "        return 0, True\n",
        "\n",
        "    left_height, left_balanced = check_height_and_balance(node.left)\n",
        "    right_height, right_balanced = check_height_and_balance(node.right)\n",
        "\n",
        "    current_height = max(left_height, right_height) + 1\n",
        "    current_balanced = left_balanced and right_balanced and abs(left_height - right_height) <= 1\n",
        "\n",
        "    return current_height, current_balanced\n",
        "\n",
        "def is_balanced(node):\n",
        "    \"\"\"Check if the binary tree is balanced.\"\"\"\n",
        "    _, balanced = check_height_and_balance(node)\n",
        "    return balanced\n",
        "\n",
        "# Create a balanced binary tree\n",
        "root = Node(1)\n",
        "root.left = Node(2)\n",
        "root.right = Node(3)\n",
        "root.left.left = Node(4)\n",
        "root.left.right = Node(5)\n",
        "root.right.left = Node(6)\n",
        "root.right.right = Node(7)\n",
        "\n",
        "\n",
        "root.left.left.left = Node(8)\n",
        "root.left.left.left.left = Node(7)\n",
        "\n",
        "print(is_balanced(root))  # Output: True for the balanced tree; False for the unbalanced tree\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "N1gTKouEEZY_",
        "outputId": "f0cea8a0-c079-47ef-9aab-4ff7e82fabfb"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "False\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# BINARY SEARCH TREE\n",
        "\n",
        "class Node:\n",
        "  def __init__(self, key):\n",
        "    self.data = key\n",
        "    self.left = self.right = None\n",
        "\n",
        "\n",
        "class BST:\n",
        "  def __init__(self, key):\n",
        "    self.root = Node(key)\n",
        "\n",
        "  def inorder(self, node):\n",
        "    if node is not None:\n",
        "      self.inorder(node.left)\n",
        "      print(str(node.data) , end = \" -> \")\n",
        "      self.inorder(node.right)\n",
        "\n",
        "  def minNodeValue(self, node):\n",
        "    current = node\n",
        "    while current.left is not None:\n",
        "      current = current.left\n",
        "    return current\n",
        "\n",
        "  def search(self, key):\n",
        "\n",
        "    if not self.root:\n",
        "      return self.root\n",
        "\n",
        "    current = self.root\n",
        "\n",
        "    while current is not None:\n",
        "\n",
        "      if key == current.data:\n",
        "        return current.data\n",
        "      elif key < current.data:\n",
        "        current = current.left\n",
        "      elif key > current.data:\n",
        "        current = current.right\n",
        "\n",
        "\n",
        "    return current\n",
        "\n",
        "\n",
        "  def insert(self,key, node):\n",
        "\n",
        "      if node is None:\n",
        "        return Node(key)\n",
        "      elif key < node.data:\n",
        "        node.left = self.insert(key, node.left)\n",
        "      elif key > node.data:\n",
        "        node.right = self.insert(key, node.right)\n",
        "      return node\n",
        "\n",
        "  def delete(self, key, node):\n",
        "\n",
        "    if node is None:\n",
        "      return node\n",
        "\n",
        "    if key < node.data:\n",
        "      node.left = self.delete(key, node.left)\n",
        "    elif key > node.data:\n",
        "      node.right = self.delete(key, node.right)\n",
        "    else:\n",
        "\n",
        "      if node.left is None:\n",
        "        temp = node.right\n",
        "        node  = None\n",
        "        return temp\n",
        "\n",
        "      elif node.right is None:\n",
        "        temp = node.left\n",
        "        node  = None\n",
        "        return temp\n",
        "\n",
        "      #If the node has 2 children\n",
        "      temp = self.minNodeValue(node.right);\n",
        "      node.data = temp.data\n",
        "\n",
        "      node.right = self.delete(temp.data, root.right)\n",
        "\n",
        "    return node\n",
        "\n",
        "\n",
        "bst = BST(5)\n",
        "root = bst.root\n",
        "bst.insert(6, root)\n",
        "bst.insert(4, root)\n",
        "bst.insert(2, root)\n",
        "bst.insert(3, root)\n",
        "bst.insert(10, root)\n",
        "bst.insert(1, root)\n",
        "\n",
        "bst.inorder(root)\n",
        "\n",
        "bst.delete(2, root)\n",
        "print(\"\\ndelete 2\")\n",
        "bst.inorder(root)\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "blD3jvlPtaSF",
        "outputId": "771bbcb6-afae-40ab-de7e-498f7c83b6f8"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 10 -> \n",
            "delete 2\n",
            "1 -> 3 -> 6 -> 10 -> 4 -> 5 -> 6 -> 10 -> "
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**AVL TREE**\n",
        "\n",
        "*   This is a self-balancing tree. It is named after Georgy Adelson-Velsky and Landis\n",
        "*   It uses a balance factor to determine whether the tree is balanced or not. Balance factor = Height of left subtree - Height of right subtree\n",
        "\n",
        "\n",
        "OPERATIONS\n",
        "(For diagrams associated with each operation and for understanding, please visit https://www.programiz.com/dsa/avl-tree)\n",
        "*   Left Rotate:  Algorithm as follows\n",
        "  1.   If y has a left subtree, assign it to x's right subtree.\n",
        "  2.   If x has a parent, replace x's position with y in the parent's subtree\n",
        "  3.   Make y the parent of x (left  subtree)\n",
        "\n",
        "*   Right Rotate:  Algorithm as follows\n",
        "  1.   If y has a right subtree, assign it to x's left subtree.\n",
        "  2.   If x has a parent, replace x's position with y in the parent's subtree\n",
        "  3.   Make y the parent of x (right  subtree)\n",
        "\n",
        "*   Left-right rotation: assuming a tree where z is the parent of y that is the parent of x;\n",
        "  1.   perform a left rotation on y\n",
        "  2.   perform a right rotation on z\n",
        "\n",
        "*   Right-left rotation: assuming a tree where z is the parent of y that is the parent of x;\n",
        "  1.   perform a right rotation on y\n",
        "  2.   perform a left rotation on z\n",
        "\n",
        "\n",
        "*   Insert: Adding a node to the tree\n",
        "  1.   Locate the right position to insert the element, following the rules of a BST and insert the node. If the key already exists, exit the function\n",
        "  2.   Update the height of each node\n",
        "  3.   Update the balance factor of the nodes.\n",
        "  4.   If the nodes are unbalanced, rebalance them according the the following principle.\n",
        "\n",
        "  BALANCE PRINCIPLE\n",
        "\n",
        "      a.   if balanceFactor > 1, it means that the height of the left subtree is greater than the right subtree\n",
        "\n",
        "      > a. if the key of the newNode is lesser than the left child, perform a right rotate\n",
        "\n",
        "      > b.else do a left-right rotation\n",
        "\n",
        "      b.   if balanceFactor < -1, it means that the height of the right subtree is greater than the left subtree\n",
        "\n",
        "      > a. if the key of the newNode is greater than the right child, perform a left rotate\n",
        "\n",
        "      > b.else do a right-left rotation\n",
        "\n",
        "\n",
        "*   Delete: Nodes are always deleted as leaf nodes. Here is the algorithm\n",
        "\n",
        "  1.   Locate the correct position of the node to be deleted.\n",
        "  2.   Determine how to delete the node\n",
        "\n",
        "      a.  if the node is a leaf node, directly delete the node\n",
        "      b.  if the node has only one child, swap the node to be deleted and the child element. Call the delete_node function on the child.\n",
        "      c.  if the node has 2 children, swap the node to be deleted with the inorder successor ( the min node on the right subtree of the element) and call the delete_node function on that element\n",
        "  \n",
        "  3.   Update the height and rebalance the nodes according the balance principle.\n"
      ],
      "metadata": {
        "id": "j5s8tnn0C8dx"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# AVL tree implementation in Python\n",
        "\n",
        "\n",
        "import sys\n",
        "\n",
        "# Create a tree node\n",
        "class TreeNode(object):\n",
        "    def __init__(self, key):\n",
        "        self.key = key\n",
        "        self.left = None\n",
        "        self.right = None\n",
        "        self.height = 1\n",
        "\n",
        "\n",
        "class AVLTree(object):\n",
        "\n",
        "    # Function to insert a node\n",
        "    def insert_node(self, root, key):\n",
        "\n",
        "        # Find the correct location and insert the node\n",
        "        if not root:\n",
        "            return TreeNode(key)\n",
        "        elif key < root.key:\n",
        "            root.left = self.insert_node(root.left, key)\n",
        "        elif key > root.key:\n",
        "            root.right = self.insert_node(root.right, key)\n",
        "        else:\n",
        "            print(\"node already exists\")\n",
        "            return root\n",
        "\n",
        "        root.height = 1 + max(self.getHeight(root.left),\n",
        "                              self.getHeight(root.right))\n",
        "\n",
        "        # Update the balance factor and balance the tree\n",
        "        balanceFactor = self.getBalance(root)\n",
        "        if balanceFactor > 1:\n",
        "            if key < root.left.key:\n",
        "                return self.rightRotate(root)\n",
        "            else:\n",
        "                root.left = self.leftRotate(root.left)\n",
        "                return self.rightRotate(root)\n",
        "\n",
        "        if balanceFactor < -1:\n",
        "            if key > root.right.key:\n",
        "                return self.leftRotate(root)\n",
        "            else:\n",
        "                root.right = self.rightRotate(root.right)\n",
        "                return self.leftRotate(root)\n",
        "\n",
        "        return root\n",
        "\n",
        "    # Function to delete a node\n",
        "    def delete_node(self, root, key):\n",
        "\n",
        "        # Find the node to be deleted and remove it\n",
        "        if not root:\n",
        "            return root\n",
        "        elif key < root.key:\n",
        "            root.left = self.delete_node(root.left, key)\n",
        "        elif key > root.key:\n",
        "            root.right = self.delete_node(root.right, key)\n",
        "        else:\n",
        "            if root.left is None:\n",
        "                temp = root.right\n",
        "                root = None\n",
        "                return temp\n",
        "            elif root.right is None:\n",
        "                temp = root.left\n",
        "                root = None\n",
        "                return temp\n",
        "            temp = self.getMinValueNode(root.right)\n",
        "            root.key = temp.key\n",
        "            root.right = self.delete_node(root.right,\n",
        "                                          temp.key)\n",
        "        if root is None:\n",
        "            return root\n",
        "\n",
        "        # Update the balance factor of nodes\n",
        "        root.height = 1 + max(self.getHeight(root.left),\n",
        "                              self.getHeight(root.right))\n",
        "\n",
        "        balanceFactor = self.getBalance(root)\n",
        "\n",
        "        # Balance the tree\n",
        "        if balanceFactor > 1:\n",
        "            if self.getBalance(root.left) >= 0:\n",
        "                return self.rightRotate(root)\n",
        "            else:\n",
        "                root.left = self.leftRotate(root.left)\n",
        "                return self.rightRotate(root)\n",
        "        if balanceFactor < -1:\n",
        "            if self.getBalance(root.right) <= 0:\n",
        "                return self.leftRotate(root)\n",
        "            else:\n",
        "                root.right = self.rightRotate(root.right)\n",
        "                return self.leftRotate(root)\n",
        "        return root\n",
        "\n",
        "    # Function to perform left rotation\n",
        "    def leftRotate(self, z):\n",
        "        y = z.right\n",
        "        T2 = y.left\n",
        "        y.left = z\n",
        "        z.right = T2\n",
        "        z.height = 1 + max(self.getHeight(z.left),\n",
        "                           self.getHeight(z.right))\n",
        "        y.height = 1 + max(self.getHeight(y.left),\n",
        "                           self.getHeight(y.right))\n",
        "        return y\n",
        "\n",
        "    # Function to perform right rotation\n",
        "    def rightRotate(self, z):\n",
        "        y = z.left\n",
        "        T3 = y.right\n",
        "        y.right = z\n",
        "        z.left = T3\n",
        "        z.height = 1 + max(self.getHeight(z.left),\n",
        "                           self.getHeight(z.right))\n",
        "        y.height = 1 + max(self.getHeight(y.left),\n",
        "                           self.getHeight(y.right))\n",
        "        return y\n",
        "\n",
        "    # Get the height of the node\n",
        "    def getHeight(self, root):\n",
        "        if not root:\n",
        "            return 0\n",
        "        return root.height\n",
        "\n",
        "    # Get balance factore of the node\n",
        "    def getBalance(self, root):\n",
        "        if not root:\n",
        "            return 0\n",
        "        return self.getHeight(root.left) - self.getHeight(root.right)\n",
        "\n",
        "    def getMinValueNode(self, root):\n",
        "        if root is None or root.left is None:\n",
        "            return root\n",
        "        return self.getMinValueNode(root.left)\n",
        "\n",
        "    def preOrder(self, root):\n",
        "        if not root:\n",
        "            return\n",
        "        print(\"{0} \".format(root.key), end=\"\")\n",
        "        self.preOrder(root.left)\n",
        "        self.preOrder(root.right)\n",
        "\n",
        "    # Print the tree\n",
        "    def printHelper(self, currPtr, indent, last):\n",
        "        if currPtr != None:\n",
        "            sys.stdout.write(indent)\n",
        "            if last:\n",
        "                sys.stdout.write(\"R----\")\n",
        "                indent += \"     \"\n",
        "            else:\n",
        "                sys.stdout.write(\"L----\")\n",
        "                indent += \"|    \"\n",
        "            print(currPtr.key)\n",
        "            self.printHelper(currPtr.left, indent, False)\n",
        "            self.printHelper(currPtr.right, indent, True)\n",
        "\n",
        "\n",
        "myTree = AVLTree()\n",
        "root = None\n",
        "nums = [33, 13, 52, 9, 21, 61, 8, 11]\n",
        "for num in nums:\n",
        "    root = myTree.insert_node(root, num)\n",
        "myTree.printHelper(root, \"\", True)\n",
        "key = 13\n",
        "root = myTree.delete_node(root, key)\n",
        "print(\"After Deletion: \")\n",
        "myTree.printHelper(root, \"\", True)\n",
        "\n",
        "print(\"after insertion\")\n",
        "myTree.insert_node(root, 8)\n",
        "myTree.printHelper(root, \"\", True)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "d53nFzhTolfh",
        "outputId": "d946a300-ecd0-4bfb-cdd4-b920c573ab2f"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "R----33\n",
            "     L----13\n",
            "     |    L----9\n",
            "     |    |    L----8\n",
            "     |    |    R----11\n",
            "     |    R----21\n",
            "     R----52\n",
            "          R----61\n",
            "After Deletion: \n",
            "R----33\n",
            "     L----9\n",
            "     |    L----8\n",
            "     |    R----21\n",
            "     |         L----11\n",
            "     R----52\n",
            "          R----61\n",
            "after insertion\n",
            "node already exists\n",
            "R----33\n",
            "     L----9\n",
            "     |    L----8\n",
            "     |    R----21\n",
            "     |         L----11\n",
            "     R----52\n",
            "          R----61\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**GRAPH DATA STRUCTURE**\n",
        "\n",
        "A graph is a collection of nodes that are connected to other nodes. Each node is called a vertex and the connection between nodes are called edges.\n",
        "\n",
        "TERMINOLOGY\n",
        "*   Adjacency: Two nodes or vertexes are adjacent if an edge connects them both.\n",
        "*   Path: A series of edges that connect one vertex to another is called a path.\n",
        "*   Directed graph: This is a type of graph in which the edges have a direction of traversal. For example, if there are two adjacent nodes A and B, because you can move from A to B doesn't mean you can move from B to A. (One way roads in Nigeria for instance).\n",
        "*   Undirected graph: This is a type of graph in which the edges do not point in any direction.\n",
        "*   Connected graph: This is a graph in which there is always a path from a vertex to any other vertex\n",
        "\n",
        "REPRESENTATION\n",
        "\n",
        "*   Adjacency Matrix: It a 2D V by V matrix which uses 1s and 0s to represent the presence of edges between vertexes. 1 shows the existence of an edge between the two vertexes while 0 shows the edge doesn't exist. Space complexity = O(V ^ 2)\n",
        "*   Adjacency List: This represents a graph as a list of linked lists.\n",
        "\n",
        "OPERATIONS\n",
        "\n",
        "*   Traversal\n",
        "*   Search and Retrieval\n",
        "*   Insertion\n",
        "*   Path finding\n",
        "\n",
        "\n",
        "\n",
        "SPANNING TREE\n",
        "\n",
        "This is a subgraph of a connect undirected graph, which includes all the vertices of the original graph with the minimum possible number of edges. The total number of spanning trees with n vertices that can be created from a complete graph is = n ^ (n - 2)\n",
        "*   Minimum spanning tree: This is a spanning tree where the sum of the weights of each edge is a minimum as possible.\n",
        "\n",
        "CHARACTERISTICS\n",
        "*   Acyclic: The spanning tree contains no circles.\n",
        "*   Connectivity: It connects all the vertices together\n",
        "*   Edges: A spanning tree of graph with vertices V has exactly V - 1 edges.\n",
        "\n",
        "STRONGLY CONNECTED COMPONENTS\n",
        "\n",
        "A strongly connected component is a portion of a graph where all the vertexes can be accessed by each in both directions. The concerned components can be found using **Kosaraju's algorithm** or **Tarjan's algorithm**.\n",
        "\n",
        "KOSARAJU'S ALGORITHM\n",
        "1.   Perform a DFS on the graph, maintaining an array of the visited vertices in the order visited, as well as when each node has finished (when all the nodes's neighbors have been visited) in a stack\n",
        "2.   Transpose the graph (Reverse the direction of all edges in the graph\n",
        "3.   Perform a second DFS on the transposed network in the order of the stack created in step one, popping each element as they are visited."
      ],
      "metadata": {
        "id": "qdLAmz7_7gJU"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#IMPLEMENTATION\n",
        "\n",
        "from collections import defaultdict\n",
        "\n",
        "\n",
        "class Graph:\n",
        "\n",
        "  def __init__(self,v):\n",
        "    self.vertex = v\n",
        "    self.graph = defaultdict(list)\n",
        "\n",
        "  def add_edge(self, v1, v2):\n",
        "    self.graph[v1].append(v2)\n",
        "\n",
        "\n",
        "  def print_scc(self, v1):\n",
        "\n",
        "    v\n",
        "\n",
        "\n",
        "\n",
        "my_graph = Graph(3)\n",
        "\n",
        "my_graph.add_edge(\"a\", \"b\")\n",
        "\n",
        "print(my_graph.graph)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "16mUyoKx73fD",
        "outputId": "47a228e8-df54-4044-d81a-3f2daa9dc4ba"
      },
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "defaultdict(<class 'list'>, {'a': ['b']})\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "Ffg2Rczu75bY"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}