Binärsuchbaum in O (log n)?

Question

Angesichts eines binären Baumes mit n Knoten, Ist es möglich zu überprüfen, ob der gegebene Baum BST ist oder nicht, in O (log n) Zeit Komplexität?

Answer 1

Wenn n die Anzahl der Knoten ist, dann nein, da Sie mindestens einmal alle Werte betrachten müssen, also benötigen Sie mindestens O (n). Aber wenn Sie n so definieren, dass es etwas Besonderes ist, wie die Gesamtzahl der Teilbäume, können Sie dies erreichen. (Es ist jedoch ein wenig dumm, dies zu tun, da es ungefähr dasselbe ist, wenn man sagt, dass man mehr Geld hat, wenn man 100 Cent statt 1 Euro hat. Es sieht vielleicht beeindruckender aus, aber auch komisch und hat keinen Mehrwert, es ist nur verwirrend mit dem arbeiten und normale Leute tun dies nicht)

Hier ist der O (n) Algorithmus: Wenn es eine BST ist, dann sind sowohl die linken als auch die rechten Bäume BST, in denen alle Werte zwischen einem bestimmten Minimum liegen und Maximalwert, so können Sie eine rekursive Methode erstellen, die ein wenig wie das geht:

public boolean isBST(subtree, minvalue, maxvalue){ 
    root=root of subtree; 
    if(root>maxvalue || root<minvalue) return false; 
    if(has left child) 
     if(!isBST(left-child-tree, minvalue, rootvalue)) return false; 
    if(has right child) 
     if(!isBST(right-child-tree, rootvalue, maxvalue)) return false; 
    return true; 
} 

und rufen Sie diese Methode mit isBST (Baum, -unendlich, + unendlich). Dies ist Pseudocode und kann natürlich besser implementiert werden.