Potrzebuję znaleźć indeks elementu w std :: set. Indeks ten można wizualizować jako odległość iteratora od początku. Jednym ze sposobów może być:odległość między std :: set begin() i std :: set iterator w O (logn)
for(int i = 0, set<int>::iterator it = s.begin(); it != iteratorToBeFound; ++it, ++i);
Wyraźnie wykonuje O (n). Ale wiemy, że odległość od katalogu głównego w drzewie wyszukiwania binarnego zaimplementowana wewnętrznie przez zestaw może być znaleziona w czasie O (log n).
Czy istnieje sposób ich wprowadzenia w celu znalezienia indeksu w czasie O (log n) w C++?
Dlaczego potrzebny jest indeks? – paulm
Czy jesteś pewien, że można znaleźć odległość w czasie 'O (log n)' w drzewie wyszukiwania binarnego? 'set' jest zwykle drzewem czerwono-czarnym, które nie ma wielu informacji w każdym węźle o tym, ile elementów znajduje się odpowiednio w lewej i prawej poddrzewie. Pamiętaj, że nie szukasz odległości bezpośrednio od korzenia, szukasz całkowitej liczby liści po lewej stronie liścia, które masz. –
@SteveJessop: Ohh, więc ich nie ma żadnego sposobu, aby obliczyć indeks w O (logn) w drzewie R-B? – divanshu