24Tree(findまで).ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 282,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Pythonで再帰を書いてもあまりいいことがないが\n",
    "class Tree24:\n",
    "    class INode:\n",
    "        def __init__(self, parent, children):  # children should be sorted\n",
    "            self.parent = parent\n",
    "            self.children = children\n",
    "            self.value = self.children[0].value\n",
    "            #self.value = min(x.value for x in self.children)\n",
    "        def add_fixup(self, tree):\n",
    "            if len(self.children) == 5:\n",
    "                if self.parent is None:\n",
    "                    self.parent = Tree24.INode(None, [self])\n",
    "                    tree.root = self.parent\n",
    "                    tree.height += 1\n",
    "                self.parent.children.remove(self)\n",
    "                newself1 = Tree24.INode(self.parent, self.children[:2])\n",
    "                for child in newself1.children:\n",
    "                    child.parent = newself1\n",
    "                newself2 = Tree24.INode(self.parent, self.children[2:])\n",
    "                for child in newself2.children:\n",
    "                    child.parent = newself2\n",
    "                self.parent.children.append(newself1)\n",
    "                self.parent.children.append(newself2)\n",
    "                self.parent.children.sort(key=lambda x: x.value)\n",
    "                self.parent.add_fixup(tree)\n",
    "            if self.value != self.children[0].value:\n",
    "                self.value = self.children[0].value\n",
    "                if self.parent is not None:\n",
    "                    self.parent.add_fixup(tree)\n",
    "        def remove_fixup(self, tree):\n",
    "            pass\n",
    "        def showR(self, depth):\n",
    "            print(' ' * depth + '(' + str(self.value) + ')')\n",
    "            for child in self.children:\n",
    "                child.showR(depth + 1)\n",
    "    class ONode:\n",
    "        def __init__(self, parent, value):\n",
    "            self.parent = parent\n",
    "            self.value = value\n",
    "        def showR(self, depth):\n",
    "            print(' ' * depth + '[' + str(self.value) + ']')\n",
    "            \n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "        self.length = 0\n",
    "        self.height = -1\n",
    "    def __len__(self):\n",
    "        return self.length\n",
    "    def add(self, x, debug=False):\n",
    "        if self.root == None:\n",
    "            self.root = Tree24.ONode(None, x)\n",
    "            self.height = 0\n",
    "        else:\n",
    "            cursor = self.root\n",
    "            while isinstance(cursor, Tree24.INode):\n",
    "                index = 0\n",
    "                for child in cursor.children[1:]:\n",
    "                    if x >= child.value:\n",
    "                        index += 1\n",
    "                    else:\n",
    "                        break\n",
    "                cursor = cursor.children[index]\n",
    "            if cursor.parent is None:\n",
    "                cursor.parent = Tree24.INode(None, [cursor])\n",
    "                self.root = cursor.parent\n",
    "                self.height += 1\n",
    "            cursor.parent.children.append(Tree24.ONode(cursor.parent, x))\n",
    "            cursor.parent.children.sort(key=lambda x: x.value)\n",
    "            cursor.parent.add_fixup(self)\n",
    "        self.length += 1\n",
    "    def find(self, x):\n",
    "        if self.root == None:\n",
    "            return False\n",
    "        else:\n",
    "            cursor = self.root\n",
    "            while isinstance(cursor, Tree24.INode):\n",
    "                index = 0\n",
    "                for child in cursor.children[1:]:\n",
    "                    if x >= child.value:\n",
    "                        index += 1\n",
    "                    else:\n",
    "                        break\n",
    "                cursor = cursor.children[index]\n",
    "            return x == cursor.value\n",
    "    def show(self):\n",
    "        if self.root is not None:\n",
    "            self.root.showR(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 283,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = Tree24()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 284,
   "metadata": {},
   "outputs": [],
   "source": [
    "t.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 285,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5]\n"
     ]
    }
   ],
   "source": [
    "t.add(5)\n",
    "t.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 286,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(4)\n",
      " [4]\n",
      " [5]\n"
     ]
    }
   ],
   "source": [
    "t.add(4)\n",
    "t.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 287,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(4)\n",
      " [4]\n",
      " [5]\n",
      " [6]\n"
     ]
    }
   ],
   "source": [
    "t.add(6)\n",
    "t.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 288,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(3)\n",
      " [3]\n",
      " [4]\n",
      " [5]\n",
      " [6]\n"
     ]
    }
   ],
   "source": [
    "t.add(3)\n",
    "t.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 289,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(3)\n",
      " (3)\n",
      "  [3]\n",
      "  [4]\n",
      " (5)\n",
      "  [5]\n",
      "  [6]\n",
      "  [7]\n"
     ]
    }
   ],
   "source": [
    "t.add(7)\n",
    "t.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 290,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(3)\n",
      " (3)\n",
      "  [3]\n",
      "  [4]\n",
      " (5)\n",
      "  [5]\n",
      "  [5.5]\n",
      "  [6]\n",
      "  [7]\n"
     ]
    }
   ],
   "source": [
    "t.add(5.5)\n",
    "t.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 291,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1)\n",
      " (1)\n",
      "  [1]\n",
      "  [3]\n",
      "  [4]\n",
      " (5)\n",
      "  [5]\n",
      "  [5.5]\n",
      "  [6]\n",
      "  [7]\n"
     ]
    }
   ],
   "source": [
    "t.add(1)\n",
    "t.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 292,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1)\n",
      " (1)\n",
      "  [1]\n",
      "  [3]\n",
      "  [4]\n",
      " (5)\n",
      "  [5]\n",
      "  [5]\n",
      " (5.5)\n",
      "  [5.5]\n",
      "  [6]\n",
      "  [7]\n"
     ]
    }
   ],
   "source": [
    "t.add(5)\n",
    "t.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 299,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 299,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "t.find(6.5)"
   ]
  },
  {
   "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}