python-tutorials/BinarySearchTree.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. Tạo 1 cây"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/BST/1.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/BST/2.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/BST/2.0.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/BST/3.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/BST/4.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/BST/5.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/BST/6.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/BST/7.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/BST/8.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 135,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [],
   "source": [
    "aList = [10, 20, -10, 40, 15, 8, 6, -15]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [],
   "source": [
    "def addANode(root, val):\n",
    "    if root is None:\n",
    "        return Node(val)\n",
    "    \n",
    "    if val < root.val:\n",
    "        root.left = addANode(root.left, val)\n",
    "    else:\n",
    "        root.right = addANode(root.right, val)\n",
    "        \n",
    "    return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [],
   "source": [
    "root = Node(aList[0])\n",
    "for idx in range(1, len(aList)):\n",
    "    root = addANode(root, aList[idx])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. In các phần từ trong một cây"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In-Order"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [],
   "source": [
    "def inOrder(root):\n",
    "    if root is None:\n",
    "        return\n",
    "    inOrder(root.left)\n",
    "    print(root.val)\n",
    "    inOrder(root.right)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Post-Order"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [],
   "source": [
    "def postOrder(root):\n",
    "    if root is None:\n",
    "        return\n",
    "    postOrder(root.left)\n",
    "    postOrder(root.right)\n",
    "    print(root.val)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pre-Order"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [],
   "source": [
    "def preOrder(root):\n",
    "    if root is None:\n",
    "        return\n",
    "    print(root.val)\n",
    "    preOrder(root.left)\n",
    "    preOrder(root.right)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. Tìm phần tử trong một cây"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findANode(root, val):\n",
    "    if root is None:\n",
    "        return None\n",
    "    \n",
    "    if val == root.val:\n",
    "        return root\n",
    "    elif val > root.val:\n",
    "        return findANode(root.right, val)\n",
    "    else:\n",
    "        return findANode(root.left, val)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [],
   "source": [
    "findANode(root, -1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4. Xóa phần tử trong một cây"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [],
   "source": [
    "def minValueNode(node): \n",
    "    current = node \n",
    "  \n",
    "    # Tìm con trái nhỏ nhất \n",
    "    while(current.left is not None): \n",
    "        current = current.left  \n",
    "  \n",
    "    return current  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "metadata": {},
   "outputs": [],
   "source": [
    "def removeANode(root, val):\n",
    "    if root is None:\n",
    "        return root\n",
    "    \n",
    "    if val > root.val:\n",
    "        root.right = removeANode(root.right, val)\n",
    "    elif val < root.val:\n",
    "        root.left = removeANode(root.left, val)\n",
    "    else:\n",
    "        # Một node có một con hoặc không con nào\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",
    "        \n",
    "        # Một node có 2 con\n",
    "        # Tìm node bên trái nhỏ nhất bên cây con phải \n",
    "        temp = minValueNode(root.right)\n",
    "        \n",
    "        print(temp.val)\n",
    "        \n",
    "        # Gắn node hiện tại với giá trị nhỏ nhất bên cây con phải\n",
    "        root.val = temp.val\n",
    "        \n",
    "        # Xóa node vừa tìm được\n",
    "        root.right = removeANode(root.right, temp.val)\n",
    "        \n",
    "    return root        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-15\n",
      "-10\n",
      "6\n",
      "8\n",
      "10\n",
      "15\n",
      "20\n",
      "40\n"
     ]
    }
   ],
   "source": [
    "inOrder(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.Node at 0x41701c0>"
      ]
     },
     "execution_count": 130,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-15\n",
      "-10\n",
      "8\n",
      "10\n",
      "15\n",
      "20\n",
      "40\n"
     ]
    }
   ],
   "source": [
    "x = inOrder(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}