python - ツリーが bst かどうかの検証 Python

Question

ツリーがバランスのとれた検索ツリーであるかどうかを確認し、確認方法を提供するように指示する練習用の面接の質問があります...クラスは次のとおりです

Class Node:
def __init__(self, k, val):
    self.key = k
    self.value = val
    self.left = None
    self.right = None

ツリーの最大値と最小値のその他の関数定義は次のとおりです。

def tree_max(node):
    maxleft  = float('-inf') if not node.left  else tree_max(node.left)
    maxright = float('-inf') if not node.right else tree_max(node.right)
    return max(node.value, maxleft, maxright)

def tree_min(node):
    minleft  = float('-inf') if not node.right else tree_min(node.left)
    minright = float('-inf') if not node.left else tree_min(node.right)
    return min(node.value, minleft, minright)

私の検証方法として

def verify(node):
    if tree_max(node.left) <= node.value and node.value <= tree_min(node.right):
       if verify(node.left) and verify(node.right):
           return True
       else:
           return False
    else:
        return False

私の問題は、検証方法を実装しようとすると発生します。BST ツリーを作成しようとしても、常に false になるようです。私の実装は次のとおりです。

root= Node(10, "Hello")
root.left = Node(15, "Fifteen")
root.right= Node(30, "Thirty")

print verify(root)

root = Node(10, "Ten")
root.right = Node(20, "Twenty")
root.left = Node(5, "Five")
root.left.right = Node(15, "Fifteen")

print verify(root)

どちらも私に False を与えています...検証機能または最小/最大機能に問題はありますか...どんな助けもいただければ幸いです。

score 8 · Accepted Answer

コードに 4 つのエラーが表示されます。

まず、null の子のチェックが逆になっていtree_minます。つまり、node.rightにアクセスする前にが存在するかどうかを確認してnode.leftおり、その逆も同様です。
次に、tree.minリーフノードで呼び出されたときに負の無限大を返します。最小計算では正の無限大を使用する必要があります (最大バージョンでは負の無限大が正しいです)。
3 番目に、のいずれかまたは両方がであっても、子ノードでorおよびそれ自体をverify無条件に呼び出すため、内に論理エラーがあります。正しいことを行うために呼び出し元に依存するのではなく、すべての関数が渡されたハンドルを作成することをお勧めします。これにより、コードも少し簡素化されます。tree_mintree_maxNoneNoneminmax
node.value最後に、各ノードに与える文字列であるで比較を行っています。node.key代わりに使用して比較したいと思います。浮動小数点数 ( などfloat("-inf")) を文字列 ( など"ten") と比較することは、Python 3 ではエラーであり、それが合法である Python 2 でさえ、期待どおりに動作しない可能性があります。

これらの問題が修正されたので、有効なツリーと無効なツリーを作成すると、期待どおりの結果が得られます。ただし、2つの例はどちらも無効であるため、それらを使用してテストすると、常にFalse結果が得られます。

最後に、いくつかのマイナーなスタイルの問題 (バグではありませんが、改善の余地があるものです)。ifPython は連鎖比較をサポートしているため、最初のステートメントをにverify単純化できますtree_max(node.left) <= node.key <= tree_min(node.right)。追加のステートメントをandネストするのではなく、チェックを接続することで、コードのその部分をさらに簡素化できます。if

これが私のために機能するコードのバージョンです（Python 3を使用していますが、Python 2とすべて下位互換性があると思います）：

class Node:
    def __init__(self, k, val):
        self.key = k
        self.value = val
        self.left = None
        self.right = None

def tree_max(node):
    if not node:
        return float("-inf")
    maxleft  = tree_max(node.left)
    maxright = tree_max(node.right)
    return max(node.key, maxleft, maxright)

def tree_min(node):
    if not node:
        return float("inf")
    minleft  = tree_min(node.left)
    minright = tree_min(node.right)
    return min(node.key, minleft, minright)

def verify(node):
    if not node:
        return True
    if (tree_max(node.left) <= node.key <= tree_min(node.right) and
        verify(node.left) and verify(node.right)):
        return True
    else:
        return False

root= Node(10, "Hello")
root.left = Node(5, "Five")
root.right= Node(30, "Thirty")

print(verify(root)) # prints True, since this tree is valid

root = Node(10, "Ten")
root.right = Node(20, "Twenty")
root.left = Node(5, "Five")
root.left.right = Node(15, "Fifteen")

print(verify(root)) # prints False, since 15 is to the left of 10

python - ツリーが bst かどうかの検証 Python

1 に答える 1

Related

Reference