Comment valider un arbre de recherche binaire?

en fait c'est l'erreur que tout le monde fait dans une interview.

Leftchild doit être comparé à (minLimitof node,node.valeur)

Rightchild doit être comparé à (node.valeur, limite maximale du noeud)

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): Faites une commande de traversée de l'arbre et stockez les valeurs des noeuds dans un tableau. Si le tableau est dans l'ordre trié, c'est un TSB valide autrement pas.

"valider" un arbre de recherche binaire signifie que vous vérifiez qu'il a en effet tous les petits éléments sur la gauche et les grands éléments sur la droite. Essentiellement, c'est une vérification pour voir si un arbre binaire est un arbre binaire recherche .

la meilleure solution que j'ai trouvée est O(n) et il n'utilise pas d'espace supplémentaire. Il est similaire à Inorder traversal, mais au lieu de le stocker dans array et de vérifier s'il est trié, nous pouvons prendre une variable statique et vérifier si array 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;
}

solution itérative utilisant inordersal.

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

voici ma solution dans 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)))

puisque la traversée en ordre d'un BST est une séquence non-décroissante, nous pourrions utiliser cette propriété pour juger si un arbre binaire est un BST ou non. En utilisant Morris traversal et en maintenant le noeud pre , nous pourrions obtenir une solution dans O(n) time et O(1) space complexité. Voici mon code

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

voici ma réponse en python, il a tous les cas corner traités et bien testé dans site web 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;
}

" il est préférable de définir d'abord un invariant. Ici l'invariant est -- n'importe quels deux éléments séquentiels du BST dans l'ordre transversal doivent être dans l'ordre strictement croissant de leur apparition (ne peut pas être égal, toujours croissant dans l'ordre transversal). Ainsi la solution peut être juste une traversée simple dans l'ordre avec la mémorisation du dernier noeud visité et la comparaison du noeud courant contre le dernier visité à '<' (ou '>')."

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

j'ai eu cette question lors d'un entretien téléphonique récemment et j'ai eu plus de mal que j'aurais dû. J'essayais de garder une trace des minimums et des maximums dans les noeuds enfant et je ne pouvais pas enrouler mon cerveau autour des différents cas sous la pression d'une interview.

après y avoir pensé en m'endormant hier soir, je me suis rendu compte que c'était aussi simple que de garder la trace du dernier noeud que vous avez visité lors d'une traversée en ordre. En Java:

public <T extends Comparable<T>> boolean isBst(TreeNode<T> root) {
    return isBst(root, null);
}

private <T extends Comparable<T>> boolean isBst(TreeNode<T> node, TreeNode<T> prev) {
    if (node == null)
        return true;

    if (isBst(node.left, prev) && (prev == null || prev.compareTo(node) < 0 ))
        return isBst(node.right, node);

    return false;
}

en Java et permettant des noeuds de même valeur dans l'un ou l'autre sous-arborescence:

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

pour savoir si BT donné est BST pour tout type de données, vous devez aller avec l'approche ci-dessous. 1. fonction d'appel récursif jusqu'à l'extrémité du noeud foliaire en utilisant l'ordre transversal 2. Construisez vos valeurs min et max vous-même.

doit avoir une valeur inférieure ou supérieure à la valeur définie par l'opérateur.

#define MIN (FirstVal, SecondVal) ((FirstVal) < (SecondVal)) ? (FirstVal):(SecondVal)
#define MAX (FirstVal, SecondVal) ((FirstVal) > (SecondVal)) ? (FirstVal):(SecondVal)

template <class T>
bool IsValidBST (treeNode &root)
{

   T min,  max;
   return IsValidBST (root, &min, &max);
}

template <class T>
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;
}

Fonctionne Très Bien :)

la récursion est facile mais l'approche itérative est meilleure, il y a une version itérative au-dessus mais c'est beaucoup trop complexe que nécessaire. Voici la meilleure solution dans c++ vous trouverez jamais n'importe où:

Cet algorithme s'exécute en O(N) le temps et les besoins O(lgN) de l'espace.

struct TreeNode
{
    int value;
    TreeNode* left;
    TreeNode* right;
};

bool isBST(TreeNode* root) {
    vector<TreeNode*> 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;
}

j'ai écrit une solution pour utiliser L'ordre transversal BST et vérifier si les noeuds est ordre croissant pour l'espace O(1) et le temps O(n) . TreeNode predecessor est le noeud de prev. Je ne suis pas sûr que la solution est juste ou pas. Parce que L'ordre transversal ne peut pas définir un arbre entier.

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;

}

ci-dessous est l'implémentation Java de la validation BST, où nous parcourons L'arborescence dans l'ordre DFS et il retourne false si nous obtenons n'importe quel nombre qui est plus grand que le dernier nombre.

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

solution Récursive:

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)

    }

solution itérative.

private static boolean checkBst(bst node) {

    Stack<bst> s = new Stack<bst>();
    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;
}

Cela fonctionne pour les doublons.

// 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)

cela fonctionne même pour les valeurs int.min et int.max en utilisant les types 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)

inspiré de http://www.jiuzhang.com/solutions/validate-binary-search-tree /

il y a deux solutions générales: traversal et divide & conquer.

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

One liner

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

Assez longue ligne.

Voici la solution itérative sans utiliser d'espace supplémentaire.

Node{
     int value;
     Node right, left
  }

  public boolean ValidateBST(Node root){
    Node currNode = root;
    Node prevNode = null;
    Stack<Node> stack = new Stack<Node>();
    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));
}

voici ma solution récursive écrite en 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);
}