New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Scapegoat trees #38

Open

make-github-pseudonymous-again opened this issue Nov 23, 2018 · 1 comment

Labels

Owner

make-github-pseudonymous-again commented Nov 23, 2018

No description provided.

make-github-pseudonymous-again added the implement label

Owner Author

make-github-pseudonymous-again commented Nov 24, 2018

Insertion only:

At each node remember:

a counter initialized to the size of its subtree
a counter initialized to 0
When inserting a new node increment the second counter of each ancestor
If one of those second counters becomes equal to the first counter of the same node, rebuild its subtree from scratch in a balanced way.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment