rot-schwarz-bäume Aufgabe d

Question

kann mir jemand helfen, Aufgabe d)

Answer 1

Hallo Alex,

steht ganz oben im Wiki-Artikel - und ist auch irgendwie logisch(!). Die Komplexität bei $n$ Elementen im Baum ist$$O(\log n)$$Genauer wäre es $\log_2(n)$, da die Suche ja binär geschieht. Mit jedem Suchschritt halbiert sich die Anzahl der verbleibenden Elemente.