mgechev/javascript-algorithms

Implement size/weight balanced tree for dynamic array.

lygstate opened this issue · 9 comments

lygstate commented

The array should be able to do the following operations:
Access the i-th element.
Insert element at potion i
Remove element from postion i.

All the operations should be strict O(logN);

mgechev commented

We have a couple of balanced tree, do you want to build an abstraction on top of any of them?

lygstate commented

@mgechev I've seen that, red-black-tree & avl-tree. But size-balanced tree won't cost extra space.

mgechev commented

Okay, lets keep the issue open for now. Unfortunately, I won't be able to start working on weight/size-balanced tree next a couple of weeks.

lygstate commented

@mgechev http://web.stanford.edu/~cqf/SBT.zip
I am not so sure if this algorithm is proof-OK.

mgechev commented

Sounds awesome! We're looking forward for it!

JakeHP commented

I've never used a WBT - interested in seeing your implementation. 👍

lygstate commented

@JakeHP I've already implemented of it.

JakeHP commented

Am I blind? I don't see it.

But if you did we should probably close this.