js-data-structures icon indicating copy to clipboard operation
js-data-structures copied to clipboard

Published 20 hours ago • verified publisher icon make-github-pseudonymous-again

Scapegoat trees

Open make-github-pseudonymous-again opened this issue 6 years ago • 1 comments

make-github-pseudonymous-again avatar Nov 23 '18 10:11 make-github-pseudonymous-again

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.

make-github-pseudonymous-again avatar Nov 24 '18 10:11 make-github-pseudonymous-again