Fusion de deux tas binaires parfaits?

Je suis coincé sur une question pendant un certain temps et je me demandais si quelqu'un peut me diriger dans la bonne direction:Fusion de deux tas binaires parfaits?

tas binaires sont représentés à l'aide Supposons une représentation arborescente à base de pointeurs au lieu d'un tableau. Considérez le problème de fusion de tas LHS binaire avec RHS. Supposons que les deux tas sont des arbres complets complets, contenant (2^L - 1) et (2^R -1) nœuds, respectivement.
Donner deux algorithmes O (log N) pour fusionner les deux tas, un si L = R et un si | L - R | = 1.

Ceci est un problème de devoirs, j'ai juste besoin d'être pointé dans la bonne direction.

Source

2010-01-22 user220755

Est-ce que l'arbre LHS doit commencer à gauche, ou est-ce juste un nom pour plus de commodité? – outis

Conseil pour L = R: faites comme si vous veniez de supprimer la racine. Faites-moi savoir si vous avez besoin de plus.

Source

2010-01-22 03:03:31 outis

Merci beaucoup! Je l'ai maintenant! – user220755

C'est un bon indice. Ce que je ne peux pas comprendre, c'est quel est le prof. arriver avec le | L-R | = 1? On dirait que l'algorithme qui est le résultat de votre indice fonctionnerait également dans ce cas. – PeterAllenWebb

Pensez aux propriétés d'un tas basé sur un tableau, et la façon dont l'algorithme est allumé violerait certaines de ces propriétés si | L-R | = 1. En fait, ce ne sont pas seulement les tas basés sur des tableaux; Pensez à la propriété de forme. – outis

Fusion de deux tas binaires parfaits?

Répondre

Questions connexes