１次元配列から二分探索木を作成するクラスを作成し、ルートノードから始めた探索結果をMySQLに格納します。親ノードと子ノードの関係性はFOREIGN KEYで結びつけます。再帰深さの制限と速度に難がありますが、今回はJavaを使用せず、Pythonのみで実行できるようにします。
目次
データベースへの接続準備
MySQLを使用するために、Pythonからデータベースの操作を行えるようにします。
from mysql import connector
import user
class Table:
def __init__(self,table_name:str,columns:list[str]) -> None:
self.table_name:str = table_name
self.columns : list[str] = ['id INT PRIMARY KEY AUTO_INCREMENT'] + columns
def get_columns(self) -> list:
return [i.split(" ")[0] for i in self.columns][1:]
def get_table_name(self) -> str:
return self.table_name
class Database:
def __init__(self,db_name:str)-> None:
self.show_exception:bool = True
self.db_name : str = db_name
self.host_name : str = 'localhost'
self.user_name : str = 'root'
self.user_password : str = f'{user.password}'
self.mysql_connection = self.create_connection()
self.create_database()
self.db_connection = self.create_database_connection()
def create_connection(self) ->connector.connection.MySQLConnection:
connection = None
try:
connection = connector.connect(
host=self.host_name,
user=self.user_name,
password=self.user_password,
)
if connection.is_connected:
print("Connection created successfully.")
except Exception as e:
if self.show_exception:
print(f"Exception caught -> {e}")
return connection
def create_database(self) -> connector.connection.MySQLConnection:
c = self.mysql_connection.cursor()
try:
c.execute(f'CREATE database {self.db_name}')
print(f"Database {self.db_name} created successfully.")
except Exception as e:
print(f"Caution: Database {self.db_name} already exists.")
if self.show_exception:
print(f"Exception caught -> {e}")
def create_database_connection(self) -> connector.connection.MySQLConnection:
connection = None
try:
connection = connector.connect(
host=self.host_name,
user=self.user_name,
password=self.user_password,
database = self.db_name
)
if connection.is_connected:
print(f"Connected to database {self.db_name}...")
except Exception as e:
if self.show_exception:
print(f"Exception caught -> {e}")
return connection
def execute(self,query:str) -> connector:
c = self.db_connection.cursor()
try:
c.execute(query)
self.db_connection.commit()
print(f"Query ({query}) excuted successfully.")
except Exception as e:
if self.show_exception:
print(f"Exception caught -> {e}")
print("->Could not execute {}".format(query.replace('\n','')))
return c
def drop_database(self,toDrop) -> None:
if toDrop:
self.execute(f"DROP DATABASE {self.db_name}")
else:
pass 探索木クラスの作成
今回は平衡二分探索木ではなく、一次元配列の順にデータを更新していくようなメソッドを持たせた探索木クラスを作成していきます。
class Node:
def __init__(self,data) -> None:
self.data = data
self.left:Node = None
self.right:Node = None
pass
def getData(self):
return self.data
def setLeft(self,leftNode) -> None:
self.left = Node(leftNode)
def getLeft(self):
return self.left
def setRight(self,rightNode) -> None:
self.right = Node(rightNode)
def getRight(self):
return self.right
class BinarySearchTree:
def __init__(self,data) -> None:
self.root:Node = Node(data)
self.btSTR:str = ""
def __str__(self) -> str:
return self.btSTR
def addAuto(self,data) -> None:
currNode:Node = self.root
while True:
if data <= currNode.getData():
if currNode.getRight() != None:
currNode = currNode.getRight()
else:
currNode.setRight(data)
break
else:
if currNode.getLeft() != None:
currNode = currNode.getLeft()
else:
currNode.setLeft(data)
break
def out(self,node:Node):
if node.getLeft() != None:
self.btSTR += f"{node.getData()}->{node.getLeft().getData()}\n"
self.out(node.getLeft())
if node.getRight() != None:
self.btSTR += f"{node.getData()}->{node.getRight().getData()}\n"
self.out(node.getRight())探索木とテーブルの生成
上記で作成したクラスを使用して、探索木と各ノードに対応するテーブルを生成していきます。再帰的に行うと速いですが、やり方がわからなかったのでイテラティブな方法で行いました。
from BinaryTree import BinarySearchTree as BST
from database import Database, Table
def main(db:Database,arr_raw:list[int],drop_mode:bool) -> None:
#Add root node
Root = Table(table_name=f'N{str(arr_raw[0])}',columns=['LeftNode INT','RightNode INT'])
db.execute(f'CREATE TABLE {Root.table_name} ({",".join(Root.columns)})')
db.execute(f'INSERT INTO {Root.get_table_name()} ({Root.get_columns()}) VALUES(NULL,NULL)')
#Create BST
bt = BST(arr_raw[0])
arr = arr_raw[1:]
for i in arr:
bt.addAuto(i)
tmpRoot = Table(table_name=f'N{str(i)}',columns=['LeftNode INT','RightNode INT'])
db.execute(f'CREATE TABLE {tmpRoot.table_name} ({",".join(tmpRoot.columns)})')
db.execute(f'INSERT INTO {tmpRoot.get_table_name()} ({tmpRoot.get_columns()}) VALUES(NULL,NULL)')
bt.out(bt.root)
bt_result = bt.btSTR[:-1]
for i,r in enumerate(bt_result.split()):
r = r.split('->')
parent = r[0]
child = r[1]
if int(parent) > int(child):
db.execute(f'UPDATE N{parent} SET LeftNode = {child} WHERE ID = 1')
else:
db.execute(f'UPDATE N{parent} SET RightNode = {child} WHERE ID = 1')
for i,r in enumerate(bt_result.split()):
r = r.split('->')
parent = r[0]
child = r[1]
db.execute(f'ALTER TABLE N{child} ADD FOREIGN KEY N{child}(id) REFERENCES N{parent}(id)')
db.drop_database(drop_mode)一次元配列を代入します。
#Create a new connection
db = Database('BinarySearchTree')
#Create a binary search tree
arr = [8,4,12,2,6,10,14,1,3,5,7,9,11,13,15]
if __name__ == '__main__':
main(db,arr,False)DBeaverによるERDの取得
DBeaverクライアントからMySQLに接続してERDを作成します。
接続成功後に以下の写真のようなアイコンを選択することでERDをPNGとして出力することができます。
出力結果
