Binärbaum Elemente einfügen in log(n), sodass höhe =log(n)?

Question

Hallo,

zerbreche mir schon 2 Tage lang den Kopf über die b. Die a war einfach, einfach 1,2,...,n als Folge angeben

und die Suche wird zu O(n). Aber bei der b habe ich mir folgendes gedacht:

Folge= (1,3,5,7,2,6,4, 8,10,12,14,9,13,11, ...,n)

Was haltet Ihr davon? Ich bin mir schon fast sicher, dass es falsch ist, und nicht allgemein genug ist oder so..

Brauche Eure Hilfe, danke im Voraus!

Viele Grüße und schöne Feiertage

Brezel

Answer 1

Zeichne einen binären Suchbaum mit den Schlüsseln 1, 2, ..., 15, der 4 Ebenen hat. Wenn dieser Baum neu aufgebaut werden müsste, dann könnten die Elemente dazu in der Reihenfolge

8,
4, 12,
2, 6, 10, 14,
1, 3, 5, 7, 9, 11, 13, 15

eingefügt werden.

Verallgemeinere dies auf beliebige n.

Comments

Genau das ist mein Problem, kriege es nicht verallgemeinert.

Könntest du es bitte veralgemeinern?

Ich weis leider garnicht wie, besten dank!

---

Für n = 16:

1/2·n,
1/4·n, 3/4·n,
1/8·n, 3/8·n, 5/8·n, 7/8·n,
1/16·n, 3/16·n, 5/16·n, 7/16·n, 9/16·n, 11/16·n, 13/16·n, 15/16·n,
16/16·n

Die 16 rutscht dann zwar in die fünfte Ebene, das ändert aber an dem Θ nichts.

---

Kann man das irgendwie als summe schreiben? Danke für die schnellsten antworten!