Comment valider un arbre de recherche binaire?

Question

J'ai lu ici un exercice d'interviews connu sous le nom de validation d'un arbre de recherche binaire.

Comment est-ce que cela fonctionne exactement? Que rechercherait-on pour valider un arbre de recherche binaire? J'ai écrit un arbre de recherche de base, mais je n'ai jamais entendu parler de ce concept.

Answer 1

En fait, c’est l’erreur que tout le monde commet dans une interview.

Leftchild doit être coché (minLimitof node, node.value)

Rightchild doit être coché (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;
}
 

Une autre solution (si l’espace n’est pas une contrainte): effectuez une traversée en ordre de l’arbre et stockez les valeurs de nœud dans un tableau. Si le tableau est dans l'ordre trié, c'est un BST valide sinon pas.

Answer 2

"Valider" un arbre de recherche binaire signifie que vous vérifiez qu'il a bien tous les éléments plus petits à gauche et les éléments de grande taille à droite. Essentiellement, il s'agit de vérifier si une arborescence binaire est une arborescence de recherche binaire.

Cette page vous permet de dessiner un arbre binaire et de le valider pour voir s’il s’agit d’un arbre de recherche binaire.

Answer 3

La meilleure solution que j'ai trouvée est O (n) et n'utilise pas d'espace supplémentaire. Il est similaire à inorder traversal mais au lieu de le stocker dans un tableau, puis de vérifier s'il est trié, nous pouvons prendre une variable statique et vérifier en ordre si le tableau est trié.

 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;
}
 

Answer 4

Solution itérative utilisant in travers order.

 bool is_bst(Node *root) {
  if (!root)
    return true;

  std::stack<Node*> 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;
}
 

Answer 5

Voici ma solution à 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 [[a b]] (< a  b))
    (partition 2 1 col)))

(defn is-valid-BST [bst]
  (is-strictly-sorted? (in-order bst)))