ツリーは私は木がバランス探索木であるかないかどうかを検証し、検証方法を与えるために私を伝える練習面接の質問を持って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になるような検証方法を実装しようとすると、私の問題が発生します。次のように私の実装は次のとおりです。どちらも、私が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) 

...私の検証機能や、私の最小/最大機能に問題がある...任意の助けいただければ幸いです。

Answer 1

コードに4つのエラーがあります。

1. まず、ヌルの子供のチェックはtree_minです。つまり、node.leftにアクセスする前にnode.rightが存在するかどうかをチェックしています。

2. 第二に、tree.min戻っ負の無限大のリーフノード上で呼ばれます。 min計算では正の無限大を使用する必要があります（負の無限大は最大バージョンで正しい）。

3. 第三に、それは無条件に1またはそれらの両方がNoneであっても、それの子ノードにtree_minまたはtree_maxを呼び出し、それ自体として、あなたは、verify内のロジックエラーを持っています。呼び出し元に頼るのではなく、すべての関数をNoneに渡すようにしてください。これにより、minとmaxのコードも少し簡単になります。

4. 最後に、あなたは、各ノードを与えている文字列である、node.valueであなたの比較をやっています。代わりにnode.keyを使って比較したいと思う。浮動小数点数（float("-inf")など）と文字列（"ten"など）を比較すると、Python 3ではエラーとなり、Python 2では合法であっても、予想通りに動作しない可能性があります。

これらの問題が修正されたことで、有効なツリーと無効なツリーを作成すると予想される結果が得られます。あなたの2つの例はどちらも無効ですので、テストに使用している場合は、常にFalseの結果が得られます。最後に

、マイナーなスタイル（バグではありませんが、それでも改善され得るもの）の問題のカップル。 Pythonは連鎖比較をサポートしているので、最初のif文をverifyからtree_max(node.left) <= node.key <= tree_min(node.right)に簡略化することができます。追加のifステートメントをネストするのではなく、チェックをandに接続することにより、コードのその部分をさらに単純化することができます。（私はそれがすべてのPython 2との後方互換性だと思いますけれども、Pythonの3を使用して）ここ

は私のために働くあなたのコードのバージョンです：

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 

Answer 2

次のように、簡単にこれを行うことができます::

INT_MAX = 999999999 
INT_MIN = -999999999 

class Node : 
    def __init__(self,data): 
     self.data = data 
     self.left = None 
     self.right = None 

def isBST(node): 
    return (isBSTUtil(node, INT_MIN, INT_MAX)) 

def isBSTUtil(node, mini, maxi): 
    if node is None : 
     return True 
    if node.data < mini or node.data > maxi : 
     return False 
    return (isBSTUtil(node.left, mini ,node.data-1) and 
      isBSTUtil(node.right, node.data+1,maxi)) 

# Driver program to test above function 
root = Node(4) 
root.left = Node(2) 
root.right = Node(5) 
root.left.left = Node(1) 
root.left.right = Node(3) 

if (isBST(root)): 
    print "Is BST" 
else: 
    print "Not a BST"