issues
search
make-github-pseudonymous-again
/
js-data-structures
:herb: Data structures for JavaScript
GNU Affero General Public License v3.0
57
stars
3
forks
source link
Scapegoat trees
#38
Open
make-github-pseudonymous-again
opened
5 years ago
make-github-pseudonymous-again
commented
5 years ago
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.
Insertion only:
At each node remember: