algorithm
Vérifier si un arbre est BST ou non
Recherche…
Si une arborescence donnée suit la propriété de l'arborescence de recherche binaire ou non
Par exemple
si l'entrée est:
La sortie doit être fausse:
Comme 4 dans le sous-arbre de gauche est supérieur à la valeur de la racine (3)
Si l'entrée est:
La sortie devrait être vraie
Algorithme pour vérifier si un arbre binaire donné est BST
Un arbre binaire est BST s'il satisfait à l'une des conditions suivantes:
- C'est vide
- Il n'y a pas de sous-arbre
- Pour chaque nœud x dans l'arborescence, toutes les clés (s'il y en a) dans la sous-arborescence gauche doivent être inférieures à la clé (x) et toutes les clés (s'il y en a) dans la sous-arborescence doivent être supérieures à la clé (x).
Un algorithme récursif simple serait donc:
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)
L'algorithme récursif ci-dessus est correct mais inefficace, car il traverse chaque nœud à plusieurs reprises.
Une autre approche pour minimiser les visites multiples de chaque nœud consiste à mémoriser les valeurs min et max possibles des clés dans le sous-arbre que nous visitons. Soit la valeur minimale possible de n'importe quelle clé soit K_MIN et la valeur maximale soit K_MAX . Lorsque nous partons de la racine de l'arborescence, la plage de valeurs de l'arborescence est [K_MIN,K_MAX] . Soit la clé du noeud racine x . Ensuite, la plage de valeurs dans le sous-arbre de gauche est [K_MIN,x) et la plage de valeurs dans le sous-arbre de droite est (x,K_MAX] . Nous utiliserons cette idée pour développer un algorithme plus efficace.
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)
Il s'appellera initialement comme:
is_BST(my_tree_root,KEY_MIN,KEY_MAX)
Une autre approche consistera à effectuer une traversée de l'ordre de l'arbre binaire. Si la traversée d'inorder produit une séquence de clés triée, l'arbre donné est un BST. Pour vérifier si la séquence d'inordres est triée, mémorisez la valeur du nœud précédemment visité et comparez-la au nœud actuel.
