Rechercher la valeur maximale entre 2 nœuds AVL [Duplicate

Question

Cette question a déjà une réponse ici:

AVL Tree: Trouver la clé avec les plus petites valeurs de données dans les touches entre deux valeurs en temps o (logn) (1 réponse)

Fermé il y a 4 ans.

j'ai un AVL tree Alors que chaque nœud se compose de:

• Clé
• Évaluer

La AVL tree est ordonné par le clés.

Donc, si j'ai 2 clés et maintenant je veux trouver le maximum évaluer entre ces 2 clés. J'ai essayé d'ajouter des informations supplémentaires à chaque nœud comme la valeur maximale dans le sous-arbre gauche et même pour le sous-arbre droit, mais je ne peux pas obtenir le bon algorithme sans "perdre" des nœuds entre.

Temps de complexité: O (log n) pire des cas.

Answer 1

De quelles autres opérations avez-vous besoin sur cet arbre composite et de quelles limites de complexité avez-vous besoin pour eux?

Si la seule restriction est sur cette opération de recherche (J, K) de la valeur-valeur-max, alors il y a la solution idiote de précomputer tous ces maxima n ^ 2 dans arbitrairement beaucoup temps; Vous stockez toutes les valeurs pour K fixe dans un tableau dans le nœud K dans l'arbre; Ensuite, votre opération est réduite à une recherche. Cependant, si vous souhaitez prendre en charge l'insertion ou la suppression, la complexité serait quelque chose comme O (n ^ 2).

Une option plus réaliste serait de stocker le maximum de chaque sous-arbre. Il y a au plus des sous-arbres o (log (n)) entre deux nœuds, et vous les rencontrez tous sur le chemin de la racine à vos deux clés J et K ou simplement sous eux dans l'arbre, donc ce serait O ( log (n)). De cette façon, vous auriez encore une insertion O (log (n)), mais je pense que la suppression serait potentiellement O (n) maintenant car il est compliqué de restaurer le maximum d'un sous-arbre dont vous avez supprimé une entrée.