Valider l'arbre de recherche binaire de comparables en un seul passage

Question

L'algorithme habituel de validation d'un arbre de recherche binaire consiste à vérifier de manière récursive que chaque valeur se situe dans une plage de nombres valides, en divisant cette plage en deux sur chaque noeud.

Certains échantillons Python pour illustrer l'algorithme (pour les valeurs non-double):

def walker(node, low, high): 
    if node is None: 
     return True 
    if not (low < node.data < high): 
     return False 

    return walker(node.left, low, node.data) and walker(node.right, node.data, high) 

def checkBST(root): 
    if root is None: 
     return True 
    return walker(root, -2**32, 2**32) 

Cela suppose que les valeurs sont des nombres entiers, et qu'ils sont tous à (-2^32, 2^32).

Et si je voulais écrire cet algorithme pour un type comparable? Trouver les valeurs les plus petites et les plus grandes dans l'arbre peut être fait en temps linéaire en utilisant un autre passage sur l'arbre, mais y a-t-il un moyen qui ne nécessite pas deux passes complètes?

Answer 1

Cela peut être fait en O(2*log n + n) temps, pour un arbre équilibré, qui est très proche d'un seul passage.

Si l'arbre de recherche binaire est valide, le plus petit élément est trouvé en descendant les sous-arbres de gauche jusqu'à la fin.

def least(node): 
    if node.left is None: 
     return node.data 
    return least(node.left) 

De même, l'élément le plus important est trouvé en descendant les sous-arbres de droite jusqu'à la fin.

def most(node): 
    if node.right is None: 
     return node.data 
    return most(node.right) 

Comme nous supposons least(root) nous donne la plus petite valeur de l'arbre, et most(root) nous donne la plus grande valeur, toutes les autres valeurs doivent être dans la gamme (least(root), most(root)).

Si l'arbre est pas valide, il y aura une plus petite valeur s quelque part dans l'arbre de telle sorte que s < least(root), et/ou une valeur plus grande l quelque part dans l'arbre de telle sorte que most(root) < l. L'une de ces étapes échouera à l'étape de validation (low < node.data < high).

Answer 2

Vous n'avez pas besoin de trouver les valeurs les plus petites et les plus grandes. Vous pouvez simplement désactiver la vérification des contraintes sur les parties de l'arbre sans limite inférieure ou supérieure.

En Python, vous pouvez simplement utiliser un objet None, ou tout autre objet, pour exprimer que la contrainte de limite inférieure ou supérieure est non active. Par exemple:

def walker(node, low= None, high= None): 
    if node is None: 
     return True 
    if low is not None and low >= node.data: 
     return False 
    if high is not None and high <= node.data: 
     return False 
    return walker(node.left, low, node.data) and walker(node.right, node.data, high) 

def checkBST(root): 
    if root is None: 
     return True 
    return walker(root) # look ma, no parameters

En python-3.x, le None est considéré comme non commandable. Néanmoins, si c'est le cas (par exemple dans un autre langage de programmation), il vous suffit d'inventer un système (par exemple en transmettant des paramètres supplémentaires) qui spécifie qu'une borne inférieure ou supérieure est active.

Vous pouvez par exemple définir quatre méthodes pour définir un arbre, comme:

def lwalker(node, low): 
    if node is None: 
     return True 
    if low >= node.data: 
     return False 
    return lwalker(node.right,low) and luwalker(node.left, low, node.data) 

def uwalker(node, upper): 
    if node is None: 
     return True 
    if upper <= node.data: 
     return False 
    return uwalker(node.left,upper) and luwalker(node.right, node.data, upper) 

def luwalker(node, low, upper): 
    if node is None: 
     return True 
    if low >= node.data or upper <= node.data: 
     return False 
    return luwalker(node.left,low,node.data) and luwalker(node.right,node.data, upper) 

def checkBST(root): 
    if root is None: 
     return True 
    return uwalker(root.left,root.data) and lwalker(root.right,root.data)