ALDS1_8_A: Binary Search Tree I (続き)
挿入のとき、最初の要素だけ特別扱いしてるのが気になった
番兵使えないかな?
from sys import maxsize
class Tree():
def __init__(self):
self.root = Node(maxsize)
def insert(self, z):
x = self.root
while x != None:
y = x
if z.key < x.key:
x = x.left
else:
x = x.right
z.parent = y
if z.key < y.key:
y.left = z
else:
y.right = z
def print_inorder(self):
:
rec(self.root.left)
print()
def print_preorder(self):
:
rec(self.root.left)
print()
できてる模様
最初にひとつ、キーを最大にしたノードを置いておいて、
そのノードの左からが本来の木という形
少しだけ短くなった
self.root.left
から見始めるのがあまり美しくないので
self.root
はなにかちがう名前にして
self.root.left
をself.root
という名前にするといいかもしれない
ついでに
再帰でやるんじゃないんだな
そこだけ半端に再帰でやってみた
もとのソースからの差異
def insert(self, z):
def rec(node):
nonlocal z
if node is None:
return z
elif z.key < node.key:
return Node(node.key,
rec(node.left),
node.right)
else:
return Node(node.key,
node.left,
rec(node.right))
self.root = rec(self.root)
class Node():
def __init__(self, key, left=None, right=None):
self.key = key
self.left = left
self.right = right
このやりかたでいちいち結果をself.root
に覚えてるのは一貫性がないかな
Node
にparent
を覚えさせるところは手を抜いた
引数にして渡すだけでできると思うけど
ソートされたデータを500000も与えられたら再帰じゃ耐えられないか
ソートはされてなかったけど当然TLE