right - tree walk algorithm




Comment créer un arbre AVL à partir de ArrayList de valeurs en temps O(n)? (2)

L'insertion est O(logn) , donc vrai, personne ne peut faire mieux que O(nlogn) lors de l'insertion. Vraiment, vous ne devriez pas insérer dans l'arbre AVL. Vous devriez juste créer l'arbre. Créez tous les nœuds et choisissez les valeurs du tableau lorsque vous construisez de nouveaux nœuds. Ne trouvez pas / recherchez la valeur dont vous avez besoin, il suffit de le prendre, le tableau est trié.

Étant donné une liste qui contient 5 éléments et est triée, par exemple [1,2,3,4,5] , quelle serait la racine de l'arbre? Que diriez-vous pour 7 éléments? dix? ...?

Après avoir obtenu la racine, quelle serait la racine du sous-arbre gauche. Quelle est la liste à regarder? Quelle partie de la liste devez-vous stocker dans le sous-arbre gauche?

C'est tout.

Ma tâche consiste à créer un arbre AVL à partir d'une liste de valeurs triées dans un tableau O (n) où n est le nombre de valeurs

J'ai travaillé dessus mais je ne peux pas obtenir le temps O (n), le meilleur que je peux obtenir est O (nlog (n))

Mon problème est que chaque fois qu'un noeud qui provoque l'arbre est déséquilibré est inséré, je dois faire une autre boucle pour trouver le noeud qui est déséquilibré et appliquer des rotations pour équilibrer l'arbre à nouveau.

Toute aide est grandement appréciée, merci!


Que diriez-vous juste de créer un arbre équilibré complet, avec quelques nœuds au niveau le plus bas pouvant éventuellement manquer, par exemple, pour 6 éléments, créer

      o
    /   \
   o     o
  / \    /
 o   o  o

Faites ensuite une marche en avant et, lorsque vous visitez le i-ème noeud, réglez sa clé sur A [i].

C'est un arbre AVL valide, puisque chaque noeud a un enfant gauche et droit dont les hauteurs diffèrent d'au plus une.

L'arbre d'origine peut être construit en O (n), et l'ordre de marche en O (n), donc la complexité est O (n).

Incidemment, sur une note semi-apparentée, il existe une technique appelée heapify pour construire un tas (mix ou max) sur un tableau d'entiers qui est O (n) pour un tableau de longueur n, même si l'insertion dans un tas est O (log n ) - l'astuce est de le faire de bas en haut.





tree