Warum dauert das Einfügen sequenzieller Elemente in einem Baum mehr Zeit als das Einfügen zufälliger Elemente in einen Baum?

Question

Dies ist keine Hausaufgaben Ich nehme eine Datenstruktur-Klasse und wir haben vor kurzem Bäume abgeschlossen. Am Ende des Kurses zeigte mein Professor dieses Bild.

ConcreteBTree ist ein binärer Baum, der nicht selbst ausbalanciert. Ich habe ein paar Fragen zu den Zeiten, die ich brauchte, um diese Verfahren abzuschließen.

1. Warum dauert das Einfügen von 100.000 sequenziellen Elementen in ConcreteBTree so viel länger als das Einfügen zufälliger Elemente? Meine Intuition wäre, dass Elemente, die sequenziell sind, weniger Zeit brauchen, als 1.000.000 zufällige Elemente einzufügen.

2. Warum sind die Zeiten von insert() und find() von ConcreteBTree mit zufälligen Elementen so nahe beieinander? Liegt es daran, dass beide die gleiche Zeit Komplexität haben? Ich dachte, Einsatz war O (1) und finden war O (n)

ich wirklich verstehen möchte, was hier los ist, wäre eine Erklärung sehr geschätzt. Danke

Answer 1

Das Einfügen von sequentiellen Elementen (1,2,3,4 ...) in einen Binärbaum führt dazu, dass die Knoten immer auf derselben Seite (zum Beispiel links) hinzugefügt werden. Wenn Sie zufällige Elemente einfügen, fügen Sie Knoten zufällig links und rechts hinzu.

Das sequentielle Hinzufügen führt dazu, dass sich die Liste wie eine normale verkettete Liste verhält (für die sequentiellen Elemente), da neue Elemente jedes zuvor hinzugefügte Element aufrufen müssen und O (n) Schritte benötigt O (log N) Schritte im Durchschnitt.

Answer 2

Armins beantwortet Q1.

2.Warum sind die Zeiten von insert() und find() von ConcreteBTree mit zufälligen Elementen so nahe beieinander? Liegt es daran, dass beide die gleiche Zeit Komplexität haben? Ich dachte, Einsatz war O (1) und finden Sie wurde O (n)

insert und find haben die gleiche Arbeit zu tun - sie gehen nach unten durch, was auch immer seltsam Baum Sie zusammengestellt haben die Suche nach dem letzten Knoten, unter der der Wert ist entweder verknüpft oder wäre (und wäre im Fall von insert), so dass sie die gleiche Anzahl von Vergleichen und Knoten-Traversalen durchführen, wobei sie ähnliche Zeit benötigen.

Die Einfügung zufälliger Elemente in einen ausgeglichenen Baum ist O (log N). Ihre Einfügungen zufälliger Werte in einen Baum, der sich nicht selbst ausgleicht, werden ein wenig, aber nicht dramatisch schlechter, da einige Zweige wesentlich länger als andere enden werden - Sie werden wahrscheinlich eine Art Glockenkurve von Zweiglängen erhalten. insert ist nur O (1), wenn Sie bereits den Knoten in dem Baum kennen, unter dem die Einfügung erfolgen soll (d. H. Normalerweise wird der Schritt find oben benötigt). find ist nur O (n), wenn jeder Knoten im Baum besucht werden muss, was nur für einen pathologisch unausgeglichenen Baum der Fall ist, der effektiv eine verkettete Liste bildet, wie Sie bereits gesagt haben sortierte Elemente.