BST Suche Problem

Question

Ich habe eine BST implementiert, die in ihren n Knoten ein Objekt vom Typ Point (x, y) enthält, die Reihenfolge in der Struktur ist entsprechend den X-Werten.

Ich brauche eine Funktion zu implementieren, die als Eingabe den Bereich von X wird immer (x links, x rechts) und der Ausgang ist (EDIT): Die Summe der Y der Koordinaten in-Bereich (inklusive).

Es ist nicht so schwer, es durch "Gehen" durch alle Knoten zu machen, das Problem ist, dass ich es in O (Logn) -Komplexität tun wollte.

Ich dachte über die Initialisierung von Feldern von Bereichen und Summe von Y, aber irgendwie funktioniert es nicht mit den Einfüge- und Löschfunktionen. irgendwelche Ideen?

Answer 1

Die Suche nach jedem Ende des Bereichs ist O(log n) Komplexität. Es müssen nicht alle Knoten in der Struktur betrachtet werden.

Wenn Sie die Nummern eines Bereichs summieren müssen, dann ist die Verwendung der oberen Grenze minus der unteren Grenze (unter Annahme eines fortlaufenden linearen Bereichs) eine konstante Zeitoperation.