1

皆さん、こんばんは。

二分探索ツリーを構築する関数を Python で設計する任務を負っています。私が自分で関数を見てみると、それは完全に理にかなっているように見え、機能するはずです。ただし、何らかの理由で、最後の「ツリー」を構築するだけで、以前のツリー情報は保存されません。クラス、コンストラクター、そしてもちろん関数を含めました。どんなヒントでも大歓迎です！関数をテストするために、次の行を使用しています。 

newMap = mapInsert1('one', 1, mapInsert1('two', 2, mkEmptyMap()))


///CODE///
class EmptyMap():
    __slots__ = ()

class NonEmptyMap():
    __slots__ = ('left', 'key', 'value', 'right')

def mkEmptyMap():
    return EmptyMap()

def mkNonEmptyMap(left, key, value, right):
    nonEmptyMap = NonEmptyMap()
    nonEmptyMap.left = left
    nonEmptyMap.key = key
    nonEmptyMap.value = value
    nonEmptyMap.right = right

    return nonEmptyMap

def mapInsert1(key, value, node):
    if isinstance(node, EmptyMap):
        node = mkNonEmptyMap(mkEmptyMap(), key, value, mkEmptyMap())
        return node
    else:
        if key > node.key:
            return mapInsert1(key, value, node.right)
        elif key < node.key:
            return mapInsert1(key, value, node.left)
        elif key == node.key:
            node.value = value
            return mapInsert1(key, value, node)
        else:
            raise TypeError('Bad Map')
4

1 に答える 1

2

わかりました、ここにあなたの答えがあります。ロジック自体に問題はありませんでした。Python でアルゴリズムを実装しようとしていた方法に問題があっただけです。

また、アルゴリズムを実装しようとしている方法にはいくつかの問題があります。これらの最初のものは、変数が関数に渡される方法に関係しています。変数が関数 Python にどのように渡されるかについて説明しているこのStackOverflow Question hereを読むことをお勧めします。簡単に言うと、コードで変数を渡したり更新したりする方法が原因で、変数のローカル スコープ コピーを常に更新しているため、更新する変数には実際には影響しません。

コードでこれを確認するには、次のことを試してください。

>>> newMap = mapInsert1('one', 1, mapInsert1('two', 2, mkEmptyMap()))

あなたが言ったように、これはうまくいきません。しかし、これは：

>>> newMap = mapInsert1('one', 1, mkEmptyMap())
>>> newMap.right = mapInsert1('two', 2, mkEmptyMap()))

しかし、新しいノードを追加しようとする前に、どのノードを更新したいかを知る必要があるため、これはあまり役に立ちません。

コードを修正するために、クラスの実装をクリーンアップしました。次の変更を加えました。

  1. まず、適切なコンストラクターの使用を開始しました。Python クラスはinit関数をコンストラクタとして使用します。詳しくはこちらをご覧ください。
  2. 次に、挿入機能を追加しました。これが実際に問題を解決するものです。この関数を使用すると、ローカル スコープの変数を上書きするのではなく、外側の変数を変更することになります。繰り返しになりますが、詳細については、上記でリンクした変数渡しの質問をご覧ください。
  3. 3 番目に、空のマップをマップ クラスの空のインスタンス化にすぎないようにし、isinstance() チェックを取り除きました。Python では、通常、可能な限り isinstance を避けるのが最善です。 isinstance の回避に関する詳細はこちら
  4. 4 番目に、コードの無限ループのバグを修正しました。条件を見ると、同じ引数で再度elif key == node.key呼び出しているため、無限再帰ループが発生しています。mapInsert1

結果のコードは次のとおりです。

class Map():
    __slots__ = ('left', 'key', 'value', 'right')

    def __init__(self, left, key, value, right):
        self.left = left
        self.key = key
        self.value = value
        self.right = right

    def insert(self, left, key, value, right):
        self.left = left
        self.key = key
        self.value = value
        self.right = right

    def isEmpty(self):
        return self.left == self.right == self.key == self.value == None

def mkEmptyMap():
    return Map(None, None, None, None)

def mapInsert1(key, value, node):
    if node.isEmpty():
        print '0'
        node.insert(mkEmptyMap(), key, value, mkEmptyMap())
        return node
    else:
        if key > node.key:
            print '1'
            return mapInsert1(key, value, node.right)
        elif key < node.key:
            print '2'
            return mapInsert1(key, value, node.left)
        elif key == node.key:
            print '3'
            node.value = value
            return node
        else:
            raise TypeError('Bad Map')

そして、ここに簡単なテストがあります：

>>> root = mapInsert1('five', 5, mkEmptyMap())
>>> mapInsert1('four', 4, root)
>>> mapInsert1('ace', 1, root)
>>> mapInsert1('five', 'five', root)
>>> root.left.isEmpty()
Out: False
>>> root.left.key
Out: 'ace'
>>> root.left.value
Out: 1
>>> root.right.isEmpty()
Out: False
>>> root.right.key
Out: 'four'
>>> root.right.value
Out: 4
>>> root.key
Out: 'five'
>>> root.value
Out: 'five'
于 2012-11-03T04:34:32.737 に答える