|
10
|
1 {
|
|
|
2 "cells": [
|
|
|
3 {
|
|
|
4 "cell_type": "code",
|
|
|
5 "execution_count": 78,
|
|
|
6 "metadata": {},
|
|
|
7 "outputs": [],
|
|
|
8 "source": [
|
|
|
9 "# coding: utf-8\n",
|
|
|
10 "#\n",
|
|
|
11 "# llrbnode23.py : Left-Leaning Red Black Tree 用操作関数\n",
|
|
|
12 "# (2-3 木バージョン)\n",
|
|
|
13 "#\n",
|
|
|
14 "# Copyright (C) 2009 Makoto Hiroi\n",
|
|
|
15 "#\n",
|
|
|
16 "\n",
|
|
|
17 "# 終端\n",
|
|
|
18 "null = None\n",
|
|
|
19 "\n",
|
|
|
20 "# 色\n",
|
|
|
21 "BLACK = 0\n",
|
|
|
22 "RED = 1\n",
|
|
|
23 "\n",
|
|
|
24 "# 節\n",
|
|
|
25 "class Node:\n",
|
|
|
26 " def __init__(self, x, color = RED):\n",
|
|
|
27 " self.data = x\n",
|
|
|
28 " self.color = color\n",
|
|
|
29 " self.left = null\n",
|
|
|
30 " self.right = null\n",
|
|
|
31 "\n",
|
|
|
32 "# 終端の設定\n",
|
|
|
33 "def make_null():\n",
|
|
|
34 " global null\n",
|
|
|
35 " if null is None:\n",
|
|
|
36 " null = Node(None, BLACK)\n",
|
|
|
37 " null.left = None\n",
|
|
|
38 " null.right = None\n",
|
|
|
39 " return null\n",
|
|
|
40 "\n",
|
|
|
41 "# 右回転\n",
|
|
|
42 "def rotate_right(node):\n",
|
|
|
43 " lnode = node.left\n",
|
|
|
44 " node.left = lnode.right\n",
|
|
|
45 " lnode.right = node\n",
|
|
|
46 " lnode.color = node.color\n",
|
|
|
47 " node.color = RED\n",
|
|
|
48 " return lnode\n",
|
|
|
49 "\n",
|
|
|
50 "# 左回転\n",
|
|
|
51 "def rotate_left(node):\n",
|
|
|
52 " rnode = node.right\n",
|
|
|
53 " node.right = rnode.left\n",
|
|
|
54 " rnode.left = node\n",
|
|
|
55 " rnode.color = node.color\n",
|
|
|
56 " node.color = RED\n",
|
|
|
57 " return rnode\n",
|
|
|
58 "\n",
|
|
|
59 "\n",
|
|
|
60 "#\n",
|
|
|
61 "# データの挿入\n",
|
|
|
62 "#\n",
|
|
|
63 "\n",
|
|
|
64 "# 4 node の分割\n",
|
|
|
65 "def split(node):\n",
|
|
|
66 " node.color = RED\n",
|
|
|
67 " node.left.color = BLACK\n",
|
|
|
68 " node.right.color = BLACK\n",
|
|
|
69 "\n",
|
|
|
70 "# 挿入\n",
|
|
|
71 "def insert(node, x):\n",
|
|
|
72 " if node is null: return Node(x)\n",
|
|
|
73 " if x < node.data:\n",
|
|
|
74 " node.left = insert(node.left, x)\n",
|
|
|
75 " elif x > node.data:\n",
|
|
|
76 " node.right = insert(node.right, x)\n",
|
|
|
77 " # skew\n",
|
|
|
78 " if node.right.color == RED:\n",
|
|
|
79 " print(\"hoge\",node.right.data)\n",
|
|
|
80 " print_node(node, 0)\n",
|
|
|
81 " node = rotate_left(node)\n",
|
|
|
82 " # split\n",
|
|
|
83 " if node.left.color == RED and node.left.left.color == RED:\n",
|
|
|
84 " node = rotate_right(node)\n",
|
|
|
85 " split(node)\n",
|
|
|
86 " return node\n",
|
|
|
87 "\n",
|
|
|
88 "# 木の表示\n",
|
|
|
89 "def print_node(node, x):\n",
|
|
|
90 " if node is not null:\n",
|
|
|
91 " print_node(node.right, x + 1)\n",
|
|
|
92 " print(\" \" * x, node.color, node.data)\n",
|
|
|
93 " print_node(node.left, x + 1)\n",
|
|
|
94 "\n",
|
|
|
95 " \n"
|
|
|
96 ]
|
|
|
97 },
|
|
|
98 {
|
|
|
99 "cell_type": "code",
|
|
|
100 "execution_count": 79,
|
|
|
101 "metadata": {},
|
|
|
102 "outputs": [],
|
|
|
103 "source": [
|
|
|
104 "root = make_null()"
|
|
|
105 ]
|
|
|
106 },
|
|
|
107 {
|
|
|
108 "cell_type": "code",
|
|
|
109 "execution_count": 80,
|
|
|
110 "metadata": {},
|
|
|
111 "outputs": [],
|
|
|
112 "source": [
|
|
|
113 "root = insert(root, 0)\n",
|
|
|
114 "root.color = BLACK\n"
|
|
|
115 ]
|
|
|
116 },
|
|
|
117 {
|
|
|
118 "cell_type": "code",
|
|
|
119 "execution_count": 81,
|
|
|
120 "metadata": {},
|
|
|
121 "outputs": [
|
|
|
122 {
|
|
|
123 "name": "stdout",
|
|
|
124 "output_type": "stream",
|
|
|
125 "text": [
|
|
|
126 " 0 0\n"
|
|
|
127 ]
|
|
|
128 }
|
|
|
129 ],
|
|
|
130 "source": [
|
|
|
131 "print_node(root, 2)\n"
|
|
|
132 ]
|
|
|
133 },
|
|
|
134 {
|
|
|
135 "cell_type": "code",
|
|
|
136 "execution_count": 82,
|
|
|
137 "metadata": {},
|
|
|
138 "outputs": [
|
|
|
139 {
|
|
|
140 "name": "stdout",
|
|
|
141 "output_type": "stream",
|
|
|
142 "text": [
|
|
|
143 "hoge 1\n",
|
|
|
144 " 1 1\n",
|
|
|
145 " 0 0\n"
|
|
|
146 ]
|
|
|
147 }
|
|
|
148 ],
|
|
|
149 "source": [
|
|
|
150 "root = insert(root, 1)"
|
|
|
151 ]
|
|
|
152 },
|
|
|
153 {
|
|
|
154 "cell_type": "code",
|
|
|
155 "execution_count": 71,
|
|
|
156 "metadata": {},
|
|
|
157 "outputs": [
|
|
|
158 {
|
|
|
159 "name": "stdout",
|
|
|
160 "output_type": "stream",
|
|
|
161 "text": [
|
|
|
162 " 0 0\n"
|
|
|
163 ]
|
|
|
164 }
|
|
|
165 ],
|
|
|
166 "source": [
|
|
|
167 "print_node(root, 0)"
|
|
|
168 ]
|
|
|
169 },
|
|
|
170 {
|
|
|
171 "cell_type": "code",
|
|
|
172 "execution_count": 52,
|
|
|
173 "metadata": {},
|
|
|
174 "outputs": [
|
|
|
175 {
|
|
|
176 "ename": "AttributeError",
|
|
|
177 "evalue": "type object 'Node' has no attribute 'make_null'",
|
|
|
178 "output_type": "error",
|
|
|
179 "traceback": [
|
|
|
180 "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
|
|
|
181 "\u001b[0;31mAttributeError\u001b[0m Traceback (most recent call last)",
|
|
|
182 "\u001b[0;32m<ipython-input-52-6016b722b985>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0ma\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mNode\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mmake_null\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
|
|
|
183 "\u001b[0;31mAttributeError\u001b[0m: type object 'Node' has no attribute 'make_null'"
|
|
|
184 ]
|
|
|
185 }
|
|
|
186 ],
|
|
|
187 "source": [
|
|
|
188 "a=Node.make_null()"
|
|
|
189 ]
|
|
|
190 },
|
|
|
191 {
|
|
|
192 "cell_type": "code",
|
|
|
193 "execution_count": 43,
|
|
|
194 "metadata": {},
|
|
|
195 "outputs": [],
|
|
|
196 "source": [
|
|
|
197 "a = Node.insert(a, 0)"
|
|
|
198 ]
|
|
|
199 },
|
|
|
200 {
|
|
|
201 "cell_type": "code",
|
|
|
202 "execution_count": 44,
|
|
|
203 "metadata": {},
|
|
|
204 "outputs": [
|
|
|
205 {
|
|
|
206 "ename": "NameError",
|
|
|
207 "evalue": "name 'print_node' is not defined",
|
|
|
208 "output_type": "error",
|
|
|
209 "traceback": [
|
|
|
210 "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
|
|
|
211 "\u001b[0;31mNameError\u001b[0m Traceback (most recent call last)",
|
|
|
212 "\u001b[0;32m<ipython-input-44-30dbdc80e254>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mNode\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mprint_node\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ma\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
|
|
|
213 "\u001b[0;32m<ipython-input-19-ffab890a4141>\u001b[0m in \u001b[0;36mprint_node\u001b[0;34m(node, x)\u001b[0m\n\u001b[1;32m 62\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mprint_node\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnode\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 63\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mnode\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0mnull\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 64\u001b[0;31m \u001b[0mprint_node\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnode\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mleft\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mx\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 65\u001b[0m \u001b[0mprint\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;34m\" \"\u001b[0m \u001b[0;34m*\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mnode\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcolor\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mnode\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mdata\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 66\u001b[0m \u001b[0mprint_node\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnode\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mright\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mx\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
|
|
|
214 "\u001b[0;31mNameError\u001b[0m: name 'print_node' is not defined"
|
|
|
215 ]
|
|
|
216 }
|
|
|
217 ],
|
|
|
218 "source": [
|
|
|
219 "Node.print_node(a, 0)"
|
|
|
220 ]
|
|
|
221 },
|
|
|
222 {
|
|
|
223 "cell_type": "code",
|
|
|
224 "execution_count": null,
|
|
|
225 "metadata": {},
|
|
|
226 "outputs": [],
|
|
|
227 "source": []
|
|
|
228 }
|
|
|
229 ],
|
|
|
230 "metadata": {
|
|
|
231 "kernelspec": {
|
|
|
232 "display_name": "Python 3",
|
|
|
233 "language": "python",
|
|
|
234 "name": "python3"
|
|
|
235 },
|
|
|
236 "language_info": {
|
|
|
237 "codemirror_mode": {
|
|
|
238 "name": "ipython",
|
|
|
239 "version": 3
|
|
|
240 },
|
|
|
241 "file_extension": ".py",
|
|
|
242 "mimetype": "text/x-python",
|
|
|
243 "name": "python",
|
|
|
244 "nbconvert_exporter": "python",
|
|
|
245 "pygments_lexer": "ipython3",
|
|
|
246 "version": "3.7.0"
|
|
|
247 }
|
|
|
248 },
|
|
|
249 "nbformat": 4,
|
|
|
250 "nbformat_minor": 2
|
|
|
251 }
|
