Temps d'exécution plus efficace dans le schéma - AVL

Question

Donc j'ai en gros la fonction avl ?cette exécution est en O (n ^ 2), c'est le cas parce que chaque fois que je suis récursif, j'appelle la hauteur qui est la fonction O (n) (où n est le nombre de nœuds dans un arbre).

(define (height t)
  (cond
    [(empty? t) 0]
    [else (+ 1 (max (height (BST-left t)) (height (BST-right t))))]))

(define (avl? t)
  (cond
    [(empty? t) #t]
    [else (and (avl? (BST-left t))
               (avl? (BST-right t))
               (>= 1 (abs (- (height (BST-left t))
                             (height (BST-right t))))))]))

Mon problème est que je veux faire avl ?s'exécute en temps O(n).On m'a donné l'indice :"Vous devriez essayer de limiter l'appel de votre fonction de hauteur à un temps constant, quelle que soit la taille du BST auquel vous êtes appliqué.De cette façon, vous pouvez obtenir un temps d'exécution O(n) dans l'ensemble." ...Je ne sais pas comment faire fonctionner ma taille en temps constant.Une suggestion pour réaliser mon avl ?exécuter en O(n) plutôt qu'en O(n^2) ?

Answer 1

Si vous n'êtes pas autorisé à stocker la hauteur dans l'arbre, vous pouvez éviter de la recalculer en ayant une fonction de travail qui vous indique la hauteur d'un arbre. et si c'est un arbre AVL.Ensuite, chaque nœud est examiné exactement une fois et vous disposez d'un algorithme O(n).Appelez ensuite le travailleur depuis le wrapper qui oublie la partie hauteur du résultat du travailleur.Vous devez bien sûr raccourcir, donc si un sous-arbre est déterminé à violer la condition d'équilibrage, ne vous embêtez pas à vérifier d'autres sous-arbres, revenez #f et une fausse hauteur.

Answer 2

Une autre option stockerait la hauteur dans chaque nœud, où la valeur représente la hauteur du sous-arbre enraciné dans ce nœud.Clairement, avec cette approche renvoyant la hauteur d'un sous-arbre serait une opération O (1).

Cela implique que toutes les opérations qui modifient l'arborescence (insertion, suppression, etc.) doivent maintenir la hauteur à jour chaque fois qu'il y a un changement structurel dans l'arbre.