Sprawdzanie, czy drzewo jest BST lub nie Python

Question

Mam pytanie wywiad praktyka, która mówi mi, aby sprawdzić, czy drzewo jest zrównoważony drzewo wyszukiwania lub nie i dać metodę weryfikacji ... Mam klasę jako

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

i inne definicje funkcji w drzewie maksymalnej i wartości min jako

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) 

My metoda weryfikacji, jak

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 

Mój problem występuje, gdy próbuję wdrożyć metodę weryfikacji, wydaje się, że zawsze otrzymuję fałsz, nawet gdy próbuję utworzyć drzewo BST. Moje wdrożenia jest w następujący sposób:

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) 

Oba dają mi fałsz ... Czy jest jakiś problem z moją funkcją weryfikacji lub mój min/max funkcji ... Każda pomoc będzie mile widziane.

Answer 1

Widzę cztery błędy w kodzie.

1. Po pierwsze, Twoje sprawdzenie zerowych dzieci jest cofane w tree_min. Oznacza to, że sprawdzasz, czy istnieje node.right przed uzyskaniem dostępu do node.left i vice versa.

2. Po drugie, tree.min zwraca ujemną nieskończoność po wywołaniu na węźle liści. Musisz użyć dodatniej nieskończoności w obliczeniach min (ujemna nieskończoność jest poprawna w wersji max).

3. Po trzecie, masz błąd logiczny w ciągu verify, ponieważ bezwarunkowo wymaga tree_min lub tree_max i sama na jego węzłów potomnych, nawet jeśli jedno z nich lub oboje są None. Sugeruję, aby wszystkie funkcje były przekazywane pod nr None, zamiast polegać na tym, że wywołujący robi właściwe rzeczy. To również upraszcza nieco kod min i max!

4. Wreszcie, dokonujesz porównań na node.value, który jest ciągiem, który podajesz każdemu węzłowi. Podejrzewam, że chcesz porównać, używając zamiast tego node.key. Porównywanie float (np. float("-inf")) do ciągu znaków (np. "ten") jest błędem w Pythonie 3, a nawet w Pythonie 2, gdzie jest legalne, prawdopodobnie nie działa tak, jak byś się spodziewał.

Po naprawieniu problemów uzyskuję oczekiwane wyniki, gdy tworzę ważne i nieprawidłowe drzewa. Twoje dwa przykłady są jednak nieprawidłowe, więc jeśli używałeś ich do testowania, zawsze uzyskasz wynik False.

Wreszcie kilka drobnych problemów związanych z stylem (które nie są błędami, ale nadal można je ulepszyć). Python obsługuje powiązane porównania, dzięki czemu można uprościć pierwsze oświadczenie if w verify do tree_max(node.left) <= node.key <= tree_min(node.right). Możesz dodatkowo uprościć tę część kodu, łącząc sprawdzenia z and zamiast zagnieżdżać dodatkową instrukcję if.

Oto wersja kodu, który działa dla mnie (przy użyciu Python 3, choć myślę, że to wszystko jest wstecznie kompatybilny z Pythonem 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 

Answer 2

Można łatwo to zrobić w następujący sposób ::

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"