Come si convalida un albero di ricerca binario?

Leggo qui di un esercizio in interviste noto come validazione di un albero di ricerca binario.

Come funziona esattamente? Cosa si cercherebbe nella convalida di un albero di ricerca binario? Ho scritto un albero di ricerca di base, ma non ho mai sentito parlare di questo concetto.

In realtà questo è l’errore che tutti fanno in un’intervista.

Leftchild deve essere controllato contro (minLimitof node, node.value)

Rightchild deve essere verificato rispetto a (node.value, MaxLimit of node)

IsValidBST(root,-infinity,infinity); bool IsValidBST(BinaryNode node, int MIN, int MAX) { if(node == null) return true; if(node.element > MIN && node.element < MAX && IsValidBST(node.left,MIN,node.element) && IsValidBST(node.right,node.element,MAX)) return true; else return false; } 

Un'altra soluzione (se lo spazio non è un vincolo): eseguire un attraversamento interno dell'albero e memorizzare i valori del nodo in una matrice. Se la matrice è nell'ordine ordinato, è un BST valido altrimenti no.

“Convalidare” un albero di ricerca binario significa che controlli che abbia effettivamente tutti gli oggetti più piccoli a sinistra e gli oggetti più grandi a destra. In sostanza, è un controllo per vedere se un albero binario è un albero di ricerca binario.

La soluzione migliore che ho trovato è O (n) e non usa spazio extra. È simile alla traversal inorder, ma invece di archiviarla in array e quindi verificare se è ordinata, possiamo prendere una variabile statica e controllare mentre l’inorder attraversa se l’array è ordinato.

 static struct node *prev = NULL; bool isBST(struct node* root) { // traverse the tree in inorder fashion and keep track of prev node if (root) { if (!isBST(root->left)) return false; // Allows only distinct valued nodes if (prev != NULL && root->data <= prev->data) return false; prev = root; return isBST(root->right); } return true; } 

Soluzione iterativa con attraversamento inorder.

 bool is_bst(Node *root) { if (!root) return true; std::stack stack; bool started = false; Node *node = root; int prev_val; while(true) { if (node) { stack.push(node); node = node->left(); continue; } if (stack.empty()) break; node = stack.top(); stack.pop(); /* beginning of bst check */ if(!started) { prev_val = node->val(); started = true; } else { if (prev_val > node->val()) return false; prev_val = node->val(); } /* end of bst check */ node = node->right(); } return true; } 

Ecco la mia soluzione in Clojure:

 (defstruct BST :val :left :right) (defn in-order [bst] (when-let [{:keys [val, left, right]} bst] (lazy-seq (concat (in-order left) (list val) (in-order right))))) (defn is-strictly-sorted? [col] (every? (fn [[ab]] (< ab)) (partition 2 1 col))) (defn is-valid-BST [bst] (is-strictly-sorted? (in-order bst))) 

Poiché l’attraversamento in ordine di un BST è una sequenza non decrescente, potremmo usare questa proprietà per giudicare se un albero binario è BST o no. Usando Morris traversal e mantenendo il pre nodo, potremmo ottenere una soluzione in O (n) time e O (1) complessità dello spazio . Ecco il mio codice

 public boolean isValidBST(TreeNode root) { TreeNode pre = null, cur = root, tmp; while(cur != null) { if(cur.left == null) { if(pre != null && pre.val >= cur.val) return false; pre = cur; cur = cur.right; } else { tmp = cur.left; while(tmp.right != null && tmp.right != cur) tmp = tmp.right; if(tmp.right == null) { // left child has not been visited tmp.right = cur; cur = cur.left; } else { // left child has been visited already tmp.right = null; if(pre != null && pre.val >= cur.val) return false; pre = cur; cur = cur.right; } } } return true; } 

Ecco la mia risposta in Python, ha tutti i casi d’angolo indirizzati e ben testati nel sito web di hackerrank

 """ Node is defined as class node: def __init__(self, data): self.data = data self.left = None self.right = None """ def checkBST(root): return checkLeftSubTree(root, root.left) and checkRightSubTree(root, root.right) def checkLeftSubTree(root, subTree): if not subTree: return True else: return root.data > subTree.data \ and checkLeftSubTree(root, subTree.left) \ and checkLeftSubTree(root, subTree.right) \ and checkLeftSubTree(subTree, subTree.left) \ and checkRightSubTree(subTree, subTree.right) def checkRightSubTree(root, subTree): if not subTree: return True else: return root.data < subTree.data \ and checkRightSubTree(root, subTree.left) \ and checkRightSubTree(root, subTree.right) \ and checkRightSubTree(subTree, subTree.right) \ and checkLeftSubTree(subTree, subTree.left) 
 bool BinarySearchTree::validate() { int minVal = -1; int maxVal = -1; return ValidateImpl(root, minVal, maxVal); } bool BinarySearchTree::ValidateImpl(Node *currRoot, int &minVal, int &maxVal) { int leftMin = -1; int leftMax = -1; int rightMin = -1; int rightMax = -1; if (currRoot == NULL) return true; if (currRoot->left) { if (currRoot->left->value < currRoot->value) { if (!ValidateImpl(currRoot->left, leftMin, leftMax)) return false; if (leftMax != currRoot->left->value && currRoot->value < leftMax) return false; } else return false; } else { leftMin = leftMax = currRoot->value; } if (currRoot->right) { if (currRoot->right->value > currRoot->value) { if(!ValidateImpl(currRoot->right, rightMin, rightMax)) return false; if (rightMin != currRoot->right->value && currRoot->value > rightMin) return false; } else return false; } else { rightMin = rightMax = currRoot->value; } minVal = leftMin < rightMin ? leftMin : rightMin; maxVal = leftMax > rightMax ? leftMax : rightMax; return true; } 

“È meglio definire prima un invariante: qui l’invariante è – qualsiasi due elementi sequenziali del BST nella traversata in ordine deve essere in ordine strettamente crescente del loro aspetto (non può essere uguale, sempre in aumento in ordine attraversamento). Quindi la soluzione può essere solo una semplice traversata in ordine con la memorizzazione dell’ultimo nodo visitato e il confronto tra il nodo corrente e l’ultimo visitato a “<" (o ">“). ”

 bool ValidateBST(Node *pCurrentNode, int nMin = INT_MIN, int nMax = INT_MAX) { return ( pCurrentNode == NULL ) || ( ( !pCurrentNode->pLeftNode || ( pCurrentNode->pLeftNode->value < pCurrentNode->value && pCurrentNode->pLeftNode->value < nMax && ValidateBST(pCurrentNode->pLeftNode, nMin, pCurrentNode->value) ) ) && ( !pCurrentNode->pRightNode || ( pCurrentNode->pRightNode->value > pCurrentNode->value && pCurrentNode->pRightNode->value > nMin && ValidateBST(pCurrentNode->pRightNode, pCurrentNode->value, nMax) ) ) ); } 

Recentemente ho ricevuto questa domanda in un’intervista telefonica e mi sono sforzata più di quanto avrei dovuto. Stavo cercando di tenere traccia dei minimi e dei massimi nei nodes figli e non potevo semplicemente avvolgere il mio cervello intorno ai diversi casi sotto la pressione di un’intervista.

Dopo averci pensato mentre stavo dormendo la notte scorsa, ho realizzato che è semplice tenere traccia dell’ultimo nodo che hai visitato durante un traversal inorder. In Java:

 public > boolean isBst(TreeNode root) { return isBst(root, null); } private > boolean isBst(TreeNode node, TreeNode prev) { if (node == null) return true; if (isBst(node.left, prev) && (prev == null || prev.compareTo(node) < 0 )) return isBst(node.right, node); return false; } 

In Java e consentendo nodes con lo stesso valore in entrambi i sotto-alberi:

 public boolean isValid(Node node) { return isValid(node, Integer.MIN_VALUE, Integer.MAX_VALUE); } private boolean isValid(Node node, int minLimit, int maxLimit) { if (node == null) return true; return minLimit <= node.value && node.value <= maxLimit && isValid(node.left, minLimit, node.value) && isValid(node.right, node.value, maxLimit); } 
 // using inorder traverse based Impl bool BinarySearchTree::validate() { int val = -1; return ValidateImpl(root, val); } // inorder traverse based Impl bool BinarySearchTree::ValidateImpl(Node *currRoot, int &val) { if (currRoot == NULL) return true; if (currRoot->left) { if (currRoot->left->value > currRoot->value) return false; if(!ValidateImpl(currRoot->left, val)) return false; } if (val > currRoot->value) return false; val = currRoot->value; if (currRoot->right) { if (currRoot->right->value < currRoot->value) return false; if(!ValidateImpl(currRoot->right, val)) return false; } return true; } 

Per sapere se BT è BST per qualsiasi tipo di dati, è necessario andare con l’approccio seguente. 1. chiama la funzione ricorsiva fino alla fine del nodo foglia usando inorder traversal 2. Costruisci te stesso i valori min e max.

L’elemento ad albero deve avere un numero di caratteri inferiore o superiore a quello definito dall’operatore.

 #define MIN (FirstVal, SecondVal) ((FirstVal) < (SecondVal)) ? (FirstVal):(SecondVal) #define MAX (FirstVal, SecondVal) ((FirstVal) > (SecondVal)) ? (FirstVal):(SecondVal) template  bool IsValidBST (treeNode &root) { T min, max; return IsValidBST (root, &min, &max); } template  bool IsValidBST (treeNode *root, T *MIN , T *MAX) { T leftMin, leftMax, rightMin, rightMax; bool isValidBST; if (root->leftNode == NULL && root->rightNode == NULL) { *MIN = root->element; *MAX = root->element; return true; } isValidBST = IsValidBST (root->leftNode, &leftMin, &leftMax); if (isValidBST) isValidBST = IsValidBST (root->rightNode, &rightMin, &rightMax); if (isValidBST) { *MIN = MIN (leftMIN, rightMIN); *Max = MAX (rightMax, leftMax); } return isValidBST; } 
 bool isBST(struct node* root) { static struct node *prev = NULL; // traverse the tree in inorder fashion and keep track of prev node if (root) { if (!isBST(root->left)) return false; // Allows only distinct valued nodes if (prev != NULL && root->data <= prev->data) return false; prev = root; return isBST(root->right); } return true; } 

Funziona bene 🙂

La ricorsione è facile ma l’approccio iterativo è migliore, c’è una versione iterativa sopra ma è troppo complessa del necessario. Ecco la migliore soluzione in c++ che troverai mai da nessuna parte:

Questo algoritmo funziona in tempo O(N) e necessita dello spazio O(lgN) .

 struct TreeNode { int value; TreeNode* left; TreeNode* right; }; bool isBST(TreeNode* root) { vector stack; TreeNode* prev = nullptr; while (root || stack.size()) { if (root) { stack.push_back(root); root = root->left; } else { if (prev && stack.back()->value <= prev->value) return false; prev = stack.back(); root = prev->right; stack.pop_back(); } } return true; } 

Ho scritto una soluzione per utilizzare inorder Traversal BST e verificare se i nodes stanno aumentando l’ordine per lo spazio O(1) E ora O(n) . TreeNode predecessor è il nodo precedente. Non sono sicuro che la soluzione sia giusta o meno. Poiché l’inorder Traversal non può definire un intero albero.

 public boolean isValidBST(TreeNode root, TreeNode predecessor) { boolean left = true, right = true; if (root.left != null) { left = isValidBST(root.left, predecessor); } if (!left) return false; if (predecessor.val > root.val) return false; predecessor.val = root.val; if (root.right != null) { right = isValidBST(root.right, predecessor); } if (!right) return false; return true; } 

Di seguito è riportata l’implementazione Java della convalida BST, in cui percorriamo l’albero in ordine DFS e restituisce false se otteniamo un numero maggiore dell’ultimo numero.

 static class BSTValidator { private boolean lastNumberInitialized = false; private int lastNumber = -1; boolean isValidBST(TreeNode node) { if (node.left != null && !isValidBST(node.left)) return false; // In-order visiting should never see number less than previous // in valid BST. if (lastNumberInitialized && (lastNumber > node.getData())) return false; if (!lastNumberInitialized) lastNumberInitialized = true; lastNumber = node.getData(); if (node.right != null && !isValidBST(node.right)) return false; return true; } } 

Soluzione ricorsiva:

 isBinary(root) { if root == null return true else if( root.left == NULL and root.right == NULL) return true else if(root.left == NULL) if(root.right.element > root.element) rerturn isBInary(root.right) else if (root.left.element < root.element) return isBinary(root.left) else return isBInary(root.left) and isBinary(root.right) } 

Soluzione iterativa

 private static boolean checkBst(bst node) { Stack s = new Stack(); bst temp; while(node!=null){ s.push(node); node=node.left; } while (!s.isEmpty()){ node = s.pop(); System.out.println(node.val); temp = node; if(node.right!=null){ node = node.right; while(node!=null) { //Checking if the current value is lesser than the previous value and ancestor. if(node.val < temp.val) return false; if(!s.isEmpty()) if(node.val>s.peek().val) return false; s.push(node); if(node!=null) node=node.left; } } } return true; } 

Questo funziona per i duplicati.

 // time O(n), space O(logn) // pseudocode is-bst(node, min = int.min, max = int.max): if node == null: return true if node.value <= min || max < node.value: return false return is-bst(node.left, min, node.value) && is-bst(node.right, node.value, max) 

Funziona anche con i valori int.min e int.max usando i tipi Nullable .

 // time O(n), space O(logn) // pseudocode is-bst(node, min = null, max = null): if node == null: return true if min != null && node.value <= min return false if max != null && max < node.value: return false return is-bst(node.left, min, node.value) && is-bst(node.right, node.value, max) 

Ispirato da http://www.jiuzhang.com/solutions/validate-binary-search-tree/

Ci sono due soluzioni generali: attraversare e dividere e conquistare.

 public class validateBinarySearchTree { public boolean isValidBST(TreeNode root) { return isBSTTraversal(root) && isBSTDivideAndConquer(root); } // Solution 1: Traversal // The inorder sequence of a BST is a sorted ascending list private int lastValue = 0; // the init value of it doesn't matter. private boolean firstNode = true; public boolean isBSTTraversal(TreeNode root) { if (root == null) { return true; } if (!isValidBST(root.left)) { return false; } // firstNode is needed because of if firstNode is Integer.MIN_VALUE, // even if we set lastValue to Integer.MIN_VALUE, it will still return false if (!firstNode && lastValue >= root.val) { return false; } firstNode = false; lastValue = root.val; if (!isValidBST(root.right)) { return false; } return true; } // Solution 2: divide && conquer private class Result { int min; int max; boolean isBST; Result(int min, int max, boolean isBST) { this.min = min; this.max = max; this.isBST = isBST; } } public boolean isBSTDivideAndConquer(TreeNode root) { return isBSTHelper(root).isBST; } public Result isBSTHelper(TreeNode root) { // For leaf node's left or right if (root == null) { // we set min to Integer.MAX_VALUE and max to Integer.MIN_VALUE // because of in the previous level which is the leaf level, // we want to set the min or max to that leaf node's val (in the last return line) return new Result(Integer.MAX_VALUE, Integer.MIN_VALUE, true); } Result left = isBSTHelper(root.left); Result right = isBSTHelper(root.right); if (!left.isBST || !right.isBST) { return new Result(0,0, false); } // For non-leaf node if (root.left != null && left.max >= root.val && root.right != null && right.min <= root.val) { return new Result(0, 0, false); } return new Result(Math.min(left.min, root.val), Math.max(right.max, root.val), true); } } 

Una fodera

 bool is_bst(Node *root, int from, int to) { return (root == NULL) ? true : root->val >= from && root->val <= to && is_bst(root->left, from, root->val) && is_bst(root->right, root->val, to); } 

Una linea piuttosto lunga però.

Ecco la soluzione iterativa senza utilizzare spazio extra.

 Node{ int value; Node right, left } public boolean ValidateBST(Node root){ Node currNode = root; Node prevNode = null; Stack stack = new Stack(); while(true){ if(currNode != null){ stack.push(currNode); currNode = currNode.left; continue; } if(stack.empty()){ return; } currNode = stack.pop(); if(prevNode != null){ if(currNode.value < prevNode.value){ return false; } } prevNode = currNode; currNode = currNode.right; } } 
  private void validateBinarySearchTree(Node node) { if (node == null) return; Node left = node.getLeft(); if (left != null) { if (left.getData() < node.getData()) { validateBinarySearchTree(left); } else { throw new IllegalStateException("Not a valid Binary Search tree"); } } Node right = node.getRight(); if (right != null) { if (right.getData() > node.getData()) { validateBinarySearchTree(right); } else { throw new IllegalStateException("Not a valid Binary Search tree"); } } } 
 boolean isBST(Node root) { if (root == null) { return true; } return (isBST(root.left) && (isBST(root.right) && (root.left == null || root.left.data <= root.data) && (root.right == null || root.right.data > root.data)); } 

Ecco la mia soluzione ricorsiva scritta in JavaScript

 function isBST(tree) { if (tree === null) return true; if (tree.left != undefined && tree.left.value > tree.value) { return false; } if (tree.right != undefined && tree.right.value <= tree.value) { return false; } return isBST(tree.left) && isBST(tree.right); }