algorithm
Controleer of een boom BST is of niet

Als een gegeven invoerboom de eigenschap Binaire zoekboom volgt of niet

Bijvoorbeeld

als de invoer is:

Uitvoer moet onwaar zijn:

Omdat 4 in de linker subboom groter is dan de rootwaarde (3)

Als de invoer is:

De uitvoer moet waar zijn

Algoritme om te controleren of een gegeven binaire boom BST is

Een binaire boom is BST als deze voldoet aan een van de volgende voorwaarden:

1. Het is leeg
2. Het heeft geen ondertitels
3. Voor elk knooppunt x in de boom moeten alle sleutels (indien aanwezig) in de linker subboom kleiner zijn dan sleutel (x) en alle sleutels (indien aanwezig) in de rechter subboom moeten groter zijn dan sleutel (x).

Een eenvoudig recursief algoritme zou dus zijn:

is_BST(root):
  if root == NULL:
   return true

  // Check values in left subtree
  if root->left != NULL:
    max_key_in_left = find_max_key(root->left)
    if max_key_in_left > root->key:
        return false

  // Check values in right subtree
  if root->right != NULL:
    min_key_in_right = find_min_key(root->right)
    if min_key_in_right < root->key:
        return false

  return is_BST(root->left) && is_BST(root->right)

Het bovenstaande recursieve algoritme is correct maar inefficiënt, omdat het meerdere knooppunttijden doorloopt.

Een andere benadering om het aantal bezoeken van elk knooppunt te minimaliseren, is om de min en max mogelijke waarden van de sleutels te onthouden in de substructuur die we bezoeken. Laat de minimaal mogelijke waarde van elke sleutel K_MIN en de maximale waarde K_MAX . Wanneer we beginnen vanuit de root van de boom, is het bereik van waarden in de boom [K_MIN,K_MAX] . Laat de sleutel van root node x . Dan is het bereik van waarden in de linker [K_MIN,x) en het bereik van waarden in de rechter (x,K_MAX] . We zullen dit idee gebruiken om een efficiënter algoritme te ontwikkelen.

is_BST(root, min, max):
    if root == NULL:
        return true

    // is the current node key out of range?
    if root->key < min || root->key > max:
        return false

    // check if left and right subtree is BST
    return is_BST(root->left,min,root->key-1) && is_BST(root->right,root->key+1,max)

Het zal in eerste instantie worden genoemd als:

is_BST(my_tree_root,KEY_MIN,KEY_MAX)

Een andere benadering zal zijn om de binaire boom in volgorde te doorlopen. Als de volgorde van de volgorde een gesorteerde reeks toetsen oplevert, is de gegeven boom een BST. Om te controleren of de volgorde in volgorde is gesorteerd, onthoudt u de waarde van het eerder bezochte knooppunt en vergelijkt u dit met het huidige knooppunt.