Re: "Size Balanced Tree" - more efficient than any known algorithm?

On 2月27日, 下午10时03分, "Chen Qifeng" <344368...@xxxxxx> wrote:
On Feb 25, 1:50 am, Ben Pfaff <b...@xxxxxxxxxxxxxxx> wrote:

"sqybi" <sqybi...@xxxxxxxxx> writes:
Surely, SBT is faster than normal BSTs

In what context? If your data arrive in random order, I doubt
any kind of balanced tree will be faster than an unbalanced tree,
because you spend unneeded time doing balancing. See
http://benpfaff.org/papers/libavl.pdf
--
Ben Pfaff
b...@xxxxxxxxxxxxxxxxxxx://benpfaff.org

I agree with Ben Pfaff. In my comprehension what sqybi said was that
SBT is faster than many ordinary balanced BSTs such as treap, AVL,
Splay in his practice. But I don't think there is a balanced BST which
is faster than a simple unbalanced tree while data are random. I know
SBT does not always beat another BST under all possible cases. But I
do think SBT is the best one in some aspects.

Sorry...I meant that SBT is faster than other balanced BSTs...
My poor English...

.