Messages in this thread | | | Subject | Re: [PATCH] rbtree: undo augmented damage -v2 | From | Peter Zijlstra <> | Date | Tue, 01 Jun 2010 20:42:00 +0200 |
| |
On Tue, 2010-06-01 at 11:09 -0700, Venkatesh Pallipadi wrote: > On Tue, Jun 1, 2010 at 10:42 AM, Peter Zijlstra <peterz@infradead.org> wrote: > > On Tue, 2010-06-01 at 10:34 -0700, Venkatesh Pallipadi wrote: > >> > >> Yes. This will cover all the cases on insert. But on erase, there is > >> still a case where a rotate of sibling node is done during the > >> re-coloration process. There we have a child change on sibling's > >> child. I am not able to think of any easy way to handle that case. > > > > Let me go draw some figures with pen and paper to match up the erase > > path with the rb_augment_erase_begin() code, because I can't quite spot > > the case we're missing. > > > > If you have it handy, ascii art might help.. > > It is this case > > P > / \ > N S > / \ > SL SR > > changing to > > P > / \ > N SL > \ > S > \ > SR
Right, but see: http://en.wikipedia.org/wiki/Red-black_tree That is delete_case5, however then we fall into delete_case6 and perform a left rotation.
So suppose we start with the tree:
P P P SL / \ / \ / \ / \ D S --> N S --> N SL --> P S \ / \ / \ \ / \ N SL SR SL* SR S* N SR \ SR
and then remove D, delete case 5 and finally delete case 6, * marks red.
rb_augment_erase_begin(D) will return N, and then rb_augment_path(N) will re-augment: N, P, SL and S.
| |