algorithm
Sprawdź, czy drzewo jest BST, czy nie

Jeśli dane drzewo wejściowe jest zgodne z właściwością drzewa wyszukiwania binarnego, czy nie

Na przykład

jeśli dane wejściowe to:

Dane wyjściowe powinny być fałszywe:

Ponieważ 4 w lewym poddrzewie jest większe niż wartość główna (3)

Jeśli dane wejściowe to:

Dane wyjściowe powinny być prawdziwe

Algorytm sprawdzający, czy dane drzewo binarne to BST

Drzewo binarne to BST, jeśli spełnia jeden z następujących warunków:

1. To jest puste
2. Nie ma poddrzewa
3. Dla każdego węzła x w drzewie wszystkie klucze (jeśli występują) w lewym poddrzewie muszą być mniejsze niż klucz (x), a wszystkie klucze (jeśli występują) w prawym poddrzewie muszą być większe niż klucz (x).

Prostym algorytmem rekurencyjnym byłoby:

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)

Powyższy algorytm rekurencyjny jest poprawny, ale nieefektywny, ponieważ przemierza każdy węzeł wielokrotnie.

Innym podejściem do zminimalizowania wielokrotnych odwiedzin każdego węzła jest zapamiętanie minimalnych i maksymalnych możliwych wartości kluczy w poddrzewie, które odwiedzamy. Niech minimalną możliwą wartością dowolnego klucza będzie K_MIN a maksymalną wartością K_MAX . Kiedy zaczynamy od katalogu głównego drzewa, zakres wartości w drzewie wynosi [K_MIN,K_MAX] . Niech kluczem węzła głównego będzie x . Zatem zakres wartości w lewym poddrzewie to [K_MIN,x) a zakres wartości w prawym poddrzewie to (x,K_MAX] . Wykorzystamy ten pomysł do opracowania bardziej wydajnego algorytmu.

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)

Będzie początkowo nazywany:

is_BST(my_tree_root,KEY_MIN,KEY_MAX)

Innym podejściem będzie wykonanie przemierzania drzewa binarnego. Jeśli przemiana wewnętrzna powoduje posortowanie sekwencji kluczy, to dane drzewo jest BST. Aby sprawdzić, czy sekwencja wewnętrzna jest posortowana, zapamiętaj wartość poprzednio odwiedzonego węzła i porównaj go z bieżącym węzłem.