kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

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.leftself.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に覚えてるのは一貫性がないかな
Nodeparentを覚えさせるところは手を抜いた
引数にして渡すだけでできると思うけど

ソートされたデータを500000も与えられたら再帰じゃ耐えられないか

ソートはされてなかったけど当然TLE