[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Pika-dev] fsplay_delete is b0rked
From: |
Tom Lord |
Subject: |
Re: [Pika-dev] fsplay_delete is b0rked |
Date: |
Fri, 7 May 2004 07:46:21 -0700 (PDT) |
> From: Tom Lord <address@hidden>
> > From: Matthew Dempsky <address@hidden>
> > /* delete
> > *
> > * Have:
> > *
> > * T
> > * / \
> > * _Tl _Tr
> > *
> > * and want to remove T.
> > *
> > * Removing T is the same as inserting _Tr after _Tl.
> > */
> > Yes and no... it would be if insert_after preserved the children of
> > the node to be inserted, but it doesn't. As it is, delete drops all
> > of Tr's children.
> > The two possible solutions to this are either to rewrite
insert_after
> > (and insert_before for consistancy) to protect children from being
> > lost or add a new operation fsplay_join. I'm leaning towards the
> > latter and plan on writing it unless someone thinks the
> > insert_(before|after) modification would be better.
> Gah. You're right. I was (probably) being too cute there. The
> insert_* routines presume that the new tree is just a single node with
> no children.
> Please deal with it this way: spend a little time trying to figure out
> what the generalization of the insert_* routines is (to deal with
> children). If it's simple, use that. If it needs to call raise, then
> screw it -- go with your current plan. If we later discover you get
> it wrong -- we'll force you to blush and then fix it :-)
Ugh. It's worse than that.
I realized when I woke up this morning that we need an "insert subtree
that has children" operation anyway -- for "insert substring".
I _think_ that's can be done no better than a combination of a raise
and two simple inserts. E.g. to insert:
T1
/ \
_T1L _T1R
on the right of the root in:
T2
/ \
_T2L _T2R
it's:
tmp = T2'
/ \
_T2L T1
/ \
_T1L _T1R
tmp2 = raise_rightmost (tmp)
== _T2R_last
/ \
{_T2L .. _T2R-1} nil
answer = _T2R_last'
/ \
{_T2L .. _T2R-1} _T1R
-t