Tree.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "25bdab97",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self,name,type='dir'):\n",
    "        self.name=name\n",
    "        self.type=type\n",
    "        self.children=[]\n",
    "        self.parent=None\n",
    "    def __repr__(self):\n",
    "        return self.name"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "65e4daa6",
   "metadata": {},
   "source": [
    "### Using tree to design basic Linux commands"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "f4864d56",
   "metadata": {},
   "outputs": [],
   "source": [
    "class FileSystemTree:\n",
    "    def __init__(self):\n",
    "        self.root=Node('/')\n",
    "        self.now=self.root\n",
    "    def mkdir(self,name):\n",
    "        #name should be ended up with '/'\n",
    "        if name[-1]!='/':\n",
    "            name+='/'\n",
    "        node=Node(name)\n",
    "        self.now.children.append(node)\n",
    "        node.parent=self.now\n",
    "    def ls(self):\n",
    "        return self.now.children\n",
    "    def cd(self,name):\n",
    "        if name[-1]!='/':\n",
    "            name+='/'\n",
    "        if name=='../':\n",
    "            self.now=self.now.parent\n",
    "            return\n",
    "        for child in self.now.children:\n",
    "            if child.name==name:\n",
    "                self.now=child\n",
    "                return\n",
    "        raise ValueError('invalid dir')     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "43eb1d4c",
   "metadata": {},
   "outputs": [],
   "source": [
    "tree=FileSystemTree()\n",
    "tree.mkdir('var/')\n",
    "tree.mkdir('bin/')\n",
    "tree.mkdir('usr/')\n",
    "tree.cd('bin/')\n",
    "tree.mkdir('python/')\n",
    "\n",
    "tree.cd('../')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "77015a73",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[var/, bin/, usr/]\n"
     ]
    }
   ],
   "source": [
    "print(tree.root.children)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "7f219efb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[var/, bin/, usr/]\n"
     ]
    }
   ],
   "source": [
    "print(tree.ls())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3d635a02",
   "metadata": {},
   "source": [
    "### Binary Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "id": "66d239c0",
   "metadata": {},
   "outputs": [],
   "source": [
    "class BiTreeNode:\n",
    "    def __init__(self,data):\n",
    "        self.data=data\n",
    "        self.lchild=None\n",
    "        self.rchild=None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "id": "1bd547a6",
   "metadata": {},
   "outputs": [],
   "source": [
    "a=BiTreeNode('A')\n",
    "b=BiTreeNode('B')\n",
    "c=BiTreeNode('C')\n",
    "d=BiTreeNode('D')\n",
    "e=BiTreeNode('E')\n",
    "f=BiTreeNode('F')\n",
    "g=BiTreeNode('G')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "id": "c7475ff0",
   "metadata": {},
   "outputs": [],
   "source": [
    "e.lchild=a\n",
    "e.rchild=g\n",
    "a.rchild=c\n",
    "g.rchild=f\n",
    "c.lchild=b\n",
    "c.rchild=d\n",
    "root=e"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "id": "4abc9d9c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "C\n"
     ]
    }
   ],
   "source": [
    "print(root.lchild.rchild.data)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7308509b",
   "metadata": {},
   "source": [
    "### 二叉树的前序遍历"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "id": "e96cc479",
   "metadata": {},
   "outputs": [],
   "source": [
    "def pre_order(root):\n",
    "    if root: #如果root不是空\n",
    "        print(root.data,end=',')\n",
    "        pre_order(root.lchild)\n",
    "        pre_order(root.rchild)     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "id": "7f1083a5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "E,A,C,B,D,G,F,"
     ]
    }
   ],
   "source": [
    "pre_order(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "22936263",
   "metadata": {},
   "source": [
    "### 二叉树的中序遍历"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "id": "16d2b288",
   "metadata": {},
   "outputs": [],
   "source": [
    "def in_order(root):\n",
    "    if root:\n",
    "        in_order(root.lchild)\n",
    "        print(root.data,end=',')\n",
    "        in_order(root.rchild)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "id": "4744542f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A,B,C,D,E,G,F,"
     ]
    }
   ],
   "source": [
    "in_order(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "af6f607e",
   "metadata": {},
   "source": [
    "### 二叉树的后序遍历"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "id": "50711801",
   "metadata": {},
   "outputs": [],
   "source": [
    "def post_order(root):\n",
    "    if root:\n",
    "        post_order(root.lchild)\n",
    "        post_order(root.rchild)\n",
    "        print(root.data,end=',')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "id": "ef5dae9d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "B,D,C,A,F,G,E,"
     ]
    }
   ],
   "source": [
    "post_order(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dbb57b22",
   "metadata": {},
   "source": [
    "### 已知二叉树的某两种遍历，要求还原出这棵树（只给一种遍历是无法确定树的形状，但两种可以）"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0cc243cf",
   "metadata": {},
   "source": [
    "#### 1.前序遍历第一个一定是根；中序遍历中间的一定是根，子树在左右两边；后序遍历最后一个一定是根"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6d6d655f",
   "metadata": {},
   "source": [
    "### 二叉树的层次遍历"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "id": "612caf10",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "id": "51aec501",
   "metadata": {},
   "outputs": [],
   "source": [
    "def level_order(root):\n",
    "    queue=deque()\n",
    "    queue.append(root)\n",
    "    while len(queue)>0: #只要队不空，一直访问\n",
    "        node=queue.popleft()#出队\n",
    "        print(node.data,end=',')\n",
    "        if node.lchild:\n",
    "            queue.append(node.lchild)\n",
    "        if node.rchild:\n",
    "            queue.append(node.rchild)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "id": "b629873c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "E,A,G,C,F,B,D,"
     ]
    }
   ],
   "source": [
    "level_order(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0d8d3cb2",
   "metadata": {},
   "source": [
    "### 二叉搜索树 ：查询，插入，删除"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "14f0b261",
   "metadata": {},
   "source": [
    "#### 二叉搜索树是一棵二叉树且满足性质：设x是二叉树的一个节点。如果y是x\n",
    "#### 左子树的一个节点，那么y.key<=x.key，如果y是x右子树的一个节点，那么\n",
    "#### y.key>=x.key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "id": "1bf4f72d",
   "metadata": {},
   "outputs": [],
   "source": [
    "class BST:\n",
    "    def __init__(self):\n",
    "        self.root=None\n",
    "    def insert(self,node,val):\n",
    "        if not node:\n",
    "            node=BiTreeNode(val)\n",
    "        elif val<node.data:\n",
    "            node.lchild=self.insert(node.lchild,val)\n",
    "            node.lchild.parent=node\n",
    "        elif val>node.data:\n",
    "            node.rchild=self.insert(node.rchild,val)\n",
    "            node.rchild.parent=node\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "id": "41e1fbcb",
   "metadata": {},
   "outputs": [],
   "source": [
    "def insert_no_recur(self,val):\n",
    "    p=self.root\n",
    "    if not p: #空树的情况特殊处理\n",
    "        self.root=BiTreeNode(val)\n",
    "        return\n",
    "    while True:\n",
    "        if val<p.data:\n",
    "            if p.lchild: \n",
    "                p=p.lchild\n",
    "            else:\n",
    "                p.lchild=BiTreeNode(val)\n",
    "                p.lchild.parent=p\n",
    "                return\n",
    "        if val>p.data:\n",
    "            if p.rchild:\n",
    "                p=p.rchild\n",
    "            else:\n",
    "                p.rchild=BiTreeNode(val)\n",
    "                p.rchild.parent=p\n",
    "                return\n",
    "        else:\n",
    "            return"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cfb7f1f2",
   "metadata": {},
   "source": [
    "### 二叉搜索树：插入"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "id": "3702d468",
   "metadata": {},
   "outputs": [],
   "source": [
    "class BiTreeNode:\n",
    "    def __init__(self,data):\n",
    "        self.data=data\n",
    "        self.lchild=None\n",
    "        self.rchild=None\n",
    "        self.parent=None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 157,
   "id": "69476c33",
   "metadata": {},
   "outputs": [],
   "source": [
    "class BST:\n",
    "    def __init__(self,li=None): #传一个列表进来\n",
    "        self.root=None\n",
    "        if li: #如果li不是none\n",
    "            for val in li:\n",
    "                self.insert_no_recur(val) #调用函数插入val\n",
    "\n",
    "    def insert(self,node,val):\n",
    "        if not node:\n",
    "            node=BiTreeNode(val)\n",
    "        elif val<node.data:\n",
    "            node.lchild=self.insert(node.lchild,val)\n",
    "            node.lchild.parent=node\n",
    "        elif val>node.data:\n",
    "            node.rchild=self.insert(node.rchild,val)\n",
    "            node.rchild.parent=node\n",
    "        return node\n",
    "\n",
    "    def insert_no_recur(self,val):\n",
    "        p=self.root\n",
    "        if not p: #空树的情况特殊处理\n",
    "            self.root=BiTreeNode(val)\n",
    "            return\n",
    "        while True:\n",
    "            if val<p.data:\n",
    "                if p.lchild: \n",
    "                    p=p.lchild\n",
    "                else:\n",
    "                    p.lchild=BiTreeNode(val)\n",
    "                    p.lchild.parent=p\n",
    "                    return\n",
    "            elif val>p.data:\n",
    "                if p.rchild:\n",
    "                    p=p.rchild\n",
    "                else:\n",
    "                    p.rchild=BiTreeNode(val)\n",
    "                    p.rchild.parent=p\n",
    "                    return\n",
    "            else:\n",
    "                return\n",
    "            \n",
    "    def pre_order(self,root):\n",
    "        if root: #如果root不是空\n",
    "            print(root.data,end=',')\n",
    "            self.pre_order(root.lchild)\n",
    "            self.pre_order(root.rchild)    \n",
    "\n",
    "    def in_order(self,root):\n",
    "        if root:\n",
    "            self.in_order(root.lchild)\n",
    "            print(root.data,end=',')\n",
    "            self.in_order(root.rchild)\n",
    "            \n",
    "    def post_order(self,root):\n",
    "        if root:\n",
    "            self.post_order(root.lchild)\n",
    "            self.post_order(root.rchild)\n",
    "            print(root.data,end=',')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 160,
   "id": "064a3910",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4,2,1,3,6,5,7,9,8,\n",
      "1,2,3,4,5,6,7,8,9,\n",
      "1,3,2,5,8,9,7,6,4,"
     ]
    }
   ],
   "source": [
    "tree=BST([4,6,7,9,2,1,3,5,8])\n",
    "tree.pre_order(tree.root)\n",
    "print('')\n",
    "tree.in_order(tree.root)\n",
    "print('')\n",
    "tree.post_order(tree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 161,
   "id": "36413820",
   "metadata": {},
   "outputs": [],
   "source": [
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 162,
   "id": "4dbdaff0",
   "metadata": {},
   "outputs": [],
   "source": [
    "li=list(range(500))\n",
    "random.shuffle(li)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "810ca7f4",
   "metadata": {},
   "source": [
    "### 中序遍历输出的一定是升序的，因为中序先输出左结点（小）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 164,
   "id": "8539a8b4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,256,257,258,259,260,261,262,263,264,265,266,267,268,269,270,271,272,273,274,275,276,277,278,279,280,281,282,283,284,285,286,287,288,289,290,291,292,293,294,295,296,297,298,299,300,301,302,303,304,305,306,307,308,309,310,311,312,313,314,315,316,317,318,319,320,321,322,323,324,325,326,327,328,329,330,331,332,333,334,335,336,337,338,339,340,341,342,343,344,345,346,347,348,349,350,351,352,353,354,355,356,357,358,359,360,361,362,363,364,365,366,367,368,369,370,371,372,373,374,375,376,377,378,379,380,381,382,383,384,385,386,387,388,389,390,391,392,393,394,395,396,397,398,399,400,401,402,403,404,405,406,407,408,409,410,411,412,413,414,415,416,417,418,419,420,421,422,423,424,425,426,427,428,429,430,431,432,433,434,435,436,437,438,439,440,441,442,443,444,445,446,447,448,449,450,451,452,453,454,455,456,457,458,459,460,461,462,463,464,465,466,467,468,469,470,471,472,473,474,475,476,477,478,479,480,481,482,483,484,485,486,487,488,489,490,491,492,493,494,495,496,497,498,499,"
     ]
    }
   ],
   "source": [
    "tree=BST(li)\n",
    "tree.in_order(tree.root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "abdc0c18",
   "metadata": {},
   "source": [
    "### 二叉搜索树：查询"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 165,
   "id": "8d5d2414",
   "metadata": {},
   "outputs": [],
   "source": [
    "class BiTreeNode:\n",
    "    def __init__(self,data):\n",
    "        self.data=data\n",
    "        self.lchild=None\n",
    "        self.rchild=None\n",
    "        self.parent=None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 176,
   "id": "cc34e764",
   "metadata": {},
   "outputs": [],
   "source": [
    "class BST:\n",
    "    def __init__(self,li=None): #传一个列表进来\n",
    "        self.root=None\n",
    "        if li: #如果li不是none\n",
    "            for val in li:\n",
    "                self.insert_no_recur(val) #调用函数插入val\n",
    "            \n",
    "    def insert_no_recur(self,val):\n",
    "        p=self.root\n",
    "        if not p: #空树的情况特殊处理\n",
    "            self.root=BiTreeNode(val)\n",
    "            return\n",
    "        while True:\n",
    "            if val<p.data:\n",
    "                if p.lchild: \n",
    "                    p=p.lchild\n",
    "                else:\n",
    "                    p.lchild=BiTreeNode(val)\n",
    "                    p.lchild.parent=p\n",
    "                    return\n",
    "            elif val>p.data:\n",
    "                if p.rchild:\n",
    "                    p=p.rchild\n",
    "                else:\n",
    "                    p.rchild=BiTreeNode(val)\n",
    "                    p.rchild.parent=p\n",
    "                    return\n",
    "            else:\n",
    "                return node\n",
    "\n",
    "    def query(self,node,val):\n",
    "        if not node: #如果是空树\n",
    "            return None\n",
    "        if val>node.data:\n",
    "            return self.query(node.rchild,val)\n",
    "        elif val<node.data:\n",
    "            return self.query(node.lchild,val)\n",
    "        else: \n",
    "            return\n",
    "        \n",
    "    def no_recur_query(self,val):\n",
    "        p=self.root\n",
    "        while p:\n",
    "            if p.data<val:\n",
    "                p=p.rchild\n",
    "            elif p.data>val:\n",
    "                p=p.lchild\n",
    "            else:\n",
    "                return p\n",
    "        return None\n",
    "\n",
    "    def pre_order(self,root):\n",
    "        if root: #如果root不是空\n",
    "            print(root.data,end=',')\n",
    "            self.pre_order(root.lchild)\n",
    "            self.pre_order(root.rchild)    \n",
    "\n",
    "    def in_order(self,root):\n",
    "        if root:\n",
    "            self.in_order(root.lchild)\n",
    "            print(root.data,end=',')\n",
    "            self.in_order(root.rchild)\n",
    "            \n",
    "    def post_order(self,root):\n",
    "        if root:\n",
    "            self.post_order(root.lchild)\n",
    "            self.post_order(root.rchild)\n",
    "            print(root.data,end=',')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 180,
   "id": "964688b2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n"
     ]
    }
   ],
   "source": [
    "li=list(range(0,500,2))\n",
    "random.shuffle(li)\n",
    "\n",
    "tree=BST(li)\n",
    "print(tree.no_recur_query(4).data) #.data is used to get the value to a key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 181,
   "id": "2b8989a3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    }
   ],
   "source": [
    "print(tree.no_recur_query(3))#3不可能存在"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4fbebae2",
   "metadata": {},
   "source": [
    "### 二叉搜索树：删除"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5f5776db",
   "metadata": {},
   "source": [
    "#### 分三种情况：\n",
    "#### 1.如果要删叶子结点：直接删除\n",
    "#### 2.如果要删除的节点只有一个孩子：将此节点的父亲与孩子链接，然后删除该节点\n",
    "#### 3.如果要删除的节点有两个孩子，将其右子树的最小节点（该节点最多有一个右孩子）删除，并替换当前节点\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 209,
   "id": "140d7f2b",
   "metadata": {},
   "outputs": [],
   "source": [
    "class BST:\n",
    "    def __init__(self,li=None): #传一个列表进来\n",
    "        self.root=None\n",
    "        if li: #如果li不是none\n",
    "            for val in li:\n",
    "                self.insert_no_recur(val) #调用函数插入val\n",
    "            \n",
    "    def insert_no_recur(self,val):\n",
    "        p=self.root\n",
    "        if not p: #空树的情况特殊处理\n",
    "            self.root=BiTreeNode(val)\n",
    "            return\n",
    "        while True:\n",
    "            if val<p.data:\n",
    "                if p.lchild: \n",
    "                    p=p.lchild\n",
    "                else:\n",
    "                    p.lchild=BiTreeNode(val)\n",
    "                    p.lchild.parent=p\n",
    "                    return\n",
    "            elif val>p.data:\n",
    "                if p.rchild:\n",
    "                    p=p.rchild\n",
    "                else:\n",
    "                    p.rchild=BiTreeNode(val)\n",
    "                    p.rchild.parent=p\n",
    "                    return\n",
    "            else:\n",
    "                return node\n",
    "\n",
    "    def query(self,node,val):\n",
    "        if not node: #如果是空树\n",
    "            return None\n",
    "        if val>node.data:\n",
    "            return self.query(node.rchild,val)\n",
    "        elif val<node.data:\n",
    "            return self.query(node.lchild,val)\n",
    "        else: \n",
    "            return\n",
    "        \n",
    "    def no_recur_query(self,val):\n",
    "        p=self.root\n",
    "        while p:\n",
    "            if p.data<val:\n",
    "                p=p.rchild\n",
    "            elif p.data>val:\n",
    "                p=p.lchild\n",
    "            else:\n",
    "                return p\n",
    "        return None\n",
    "\n",
    "    def pre_order(self,root):\n",
    "        if root: #如果root不是空\n",
    "            print(root.data,end=',')\n",
    "            self.pre_order(root.lchild)\n",
    "            self.pre_order(root.rchild)    \n",
    "\n",
    "    def in_order(self,root):\n",
    "        if root:\n",
    "            self.in_order(root.lchild)\n",
    "            print(root.data,end=',')\n",
    "            self.in_order(root.rchild)\n",
    "            \n",
    "    def post_order(self,root):\n",
    "        if root:\n",
    "            self.post_order(root.lchild)\n",
    "            self.post_order(root.rchild)\n",
    "            print(root.data,end=',')\n",
    "\n",
    "    def __remove_node_1(self,node):\n",
    "        #situation1: node is leaf node\n",
    "        if not node.parent: #if the node's parent is null\n",
    "            self.root=None\n",
    "        if node==node.parent.lchild: # if node is his parent's left child\n",
    "            node.parent.lchild=None\n",
    "        else:# if node is his parent's right child\n",
    "            node.parent.rchild=None\n",
    "            \n",
    "    def __remove_node_21(self,node):       \n",
    "        #situation2_1: node has only 1 child,The child is left child\n",
    "        if not node.parent: #if the node is root node 根节点\n",
    "            self.root=node.lchild \n",
    "            node.lchild.parent=None\n",
    "        elif node==node.parent.lchild:\n",
    "            node.parent.lchild=node.lchild #父亲的左孩子等于他的左孩子\n",
    "            node.lchild.parent=node.parent\n",
    "        else:#node是他父亲的右孩子\n",
    "            node.parent.rchild=node.lchild\n",
    "            node.lchild.parent=node.parent\n",
    "            \n",
    "    def __remove_node_22(self,node):       \n",
    "        #situation2_2: node has only 1 child,The child is right child\n",
    "        if not node.parent: #if the node is root node 根节点\n",
    "            self.root=node.rchild \n",
    "            node.rchild.parent=None\n",
    "        elif node==node.parent.lchild:\n",
    "            node.parent.lchild=node.rchild #父亲的左孩子等于他的右孩子\n",
    "            node.rchild.parent=node.parent\n",
    "        else:#node是他父亲的右孩子\n",
    "            node.parent.rchild=node.rchild #父亲的右孩子等于他的右孩子\n",
    "            node.rchild.parent=node.parent\n",
    "    \n",
    "    def delete(self,val):       \n",
    "        #situation3: 要删除的节点有两个孩子\n",
    "        #先判断是不是空树\n",
    "        if self.root:\n",
    "            node=self.no_recur_query(val) #先调用query找到这个节点\n",
    "            if not node: #不存在这个node\n",
    "                return False #or Raise Error\n",
    "            if not node.lchild and not node.rchild: #这个节点没有左右孩子\n",
    "                self.__remove_node_1(node)\n",
    "            elif not node.rchild:#这个节点没有右孩子，只有一个左孩子\n",
    "                self.__remove_node_21(node)\n",
    "            elif not node.lchild:#这个节点没有左孩子，只有一个右孩子\n",
    "                self.__remove__node_22(node)\n",
    "            else:\n",
    "                #两个孩子都有\n",
    "                #先找右子树里最小的节点\n",
    "                min_node=node.rchild\n",
    "                while min_node.lchild: #当min_node有左孩子\n",
    "                    min_node=min_node.lchild #min_node等于右子树里最小节点，及在有左结点情况下的左结点的值\n",
    "                node.data=min_node.data #把node里的值替换成min_node的值\n",
    "                #删除min_node--又要考虑两种情况：情况1和情况2\n",
    "                if min_node.rchild:\n",
    "                    self.__remove_node_22(min_node)\n",
    "                else:\n",
    "                    self.__remove_node_1(min_node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 210,
   "id": "9ce9a28c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1,2,3,4,5,6,7,8,9,\n",
      "1,2,3,5,6,7,8,9,"
     ]
    }
   ],
   "source": [
    "tree=BST([1,4,2,5,3,8,6,9,7])\n",
    "tree.in_order(tree.root)\n",
    "print('')\n",
    "tree.delete(4)\n",
    "tree.in_order(tree.root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2b6f14d6",
   "metadata": {},
   "source": [
    "#### 二叉搜索树的效率  \n",
    "#### 平均情况下，二叉搜索树进行搜索的时间复杂度为o(lgn)  \n",
    "#### 最坏情况下，二叉搜索树可能非常偏斜  \n",
    "#### 解决方案：随机化插入／AVL树"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0f97cdb6",
   "metadata": {},
   "source": [
    "### AVL树\n",
    "##### AVL树是一棵自平衡的二叉搜索树。  \n",
    "##### AVL树具有以下性质：  \n",
    "##### 根的左右子树的高度之差的绝对值不能超过1  \n",
    "##### 根的左右子树都是平衡二叉树"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "16cdd8f7",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0c528cab",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7d5b75bb",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dbb20447",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1ece3fe5",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1caa638d",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4769cbb0",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}