Re: Bugfix for splay trees

G'day Arjan!

> I think I've found the bug.

I think your right :))

> >If this is the form that the tree takes after self-adjusting, sobeit. The
> >overall efficiency of the tree is still O(log n). Given that we assume
access
> >is not made evenly by all sites listed in the acl at one time, the tree will
> >be reorganised to give the best lookup for those clients that are using the
> >proxy at the time. Least checked clients will be at the end of the tree.
> >Balance is not a concern.
> >
> >Even if the tree did adjust into a linked list, a search for the last
> >element would cause the most adjustment of the tree. It would only be a
> >linked list for one search.
>
> I don't think the above is completely true. Now that I've studied the code
> some more I think you can get really heavy self-adjusting when two sites,

The splay function is called on each access no matter what. If it's the same IP
then no change is made to the tree.

> A with the smallest IP number in the list and B with the largest number in
> the list, are the two only users of the cache. Every switch in client
> leads to a complete rotation of the tree. And if you start with a linear
> list (worst case situation for a tree) it will remain a linear list:
>
> B A
> / \
> / -> \
> / \
> / \
> A B

Are you assuming just two hosts? If there are more then the tree will behave as
follows:

           5
          /
         4 0 5
        / \ /
       3 4 4
      / / \ /
     2 -> 2 5 -> 0
    / / \ \
   1 1 3 2
  / / \
 0 1 3

No more linked list. The top part of the tree will be the same no matter how
long the original linked list; ie if only rotating from min to max, they will
always only be two branches apart.

> I hope to produce a patch in the next few days which implements both splay
> trees and balanced binary trees so people can start comparing them in
> real-life situations and choose the best solution for their purposes.

Excellent.

Later
Ed

-- 
Ed Knowles aka Jasper				   Phone : +61 2 9385 4962
E-mail: ed@fatboy.geog.unsw.edu.au	           Fax   : +61 2 9313 7878
            What I lack in morals I make up for in principles.