--- Log opened Mon Jul 04 00:00:11 2022
03:20 -!- gnusha [~gnusha@user/gnusha] has joined #utreexo
03:20 [Users #utreexo]
03:20 [ achow101   ] [ dergoegge] [ fjahr     ] [ ksedgwic      ] [ sloorush   ] [ takinbo ] 
03:20 [ adiabat_   ] [ devrandom] [ gnusha    ] [ michaelfolkson] [ stevenroose] [ theStack] 
03:20 [ calvinalvin] [ FelixWeis] [ instagibbs] [ RubenSomsen   ] [ stickies-v ] 
03:20 -!- Irssi: #utreexo: Total of 17 nicks [0 ops, 0 halfops, 0 voices, 17 normal]
03:20 -!- Channel #utreexo created Wed May 19 11:14:50 2021
03:22 -!- Irssi: Join to #utreexo was synced in 171 secs
21:15 < calvinalvin> One idea I had
21:15 < calvinalvin> Why don't we just deal with the empty roots (aka zombie roots) during deletion?
21:15 < calvinalvin> After deletion happens, move up the lower root to the empty root
21:17 < calvinalvin> |---------------\
21:17 < calvinalvin> 12
21:17 < calvinalvin> |-------\       |-------\
21:17 < calvinalvin> 08      09      10
21:17 < calvinalvin> |---\   |---\   |---\   |---\
21:17 < calvinalvin> 00  01  02  03  04  05  06
21:17 < calvinalvin>   
21:18 < calvinalvin> In this tree, if we're deleting [04, 05], the tree will look like so:
21:18 < calvinalvin>   
21:18 < calvinalvin> |---------------\
21:18 < calvinalvin> 12
21:18 < calvinalvin> 08      09      --
21:18 < calvinalvin> shoot messed up
21:18 < calvinalvin>   
21:18 < calvinalvin> |---------------\
21:18 < calvinalvin> 12
21:18 < calvinalvin> |-------\       |-------\
21:19 < calvinalvin> 08      09      --
21:19 < calvinalvin> |---\   |---\   |---\   |---\
21:19 < calvinalvin> 00  01  02  03          06
21:19 < calvinalvin>   
21:19 < calvinalvin> And we end the deletion here
21:19 < calvinalvin> But why not move 06 up to where 10 should be? Then we'll never have to deal with empty roots
21:19 < calvinalvin> So add an extra step to the deletion process
21:20 < calvinalvin> After we make 10 empty, then move the next lower root up to where it is
21:20 < calvinalvin> So the final tree would look like so
21:20 < calvinalvin>   
21:21 < calvinalvin> |---------------\
21:21 < calvinalvin> 12
21:21 < calvinalvin> |-------\       |-------\
21:21 < calvinalvin> 08      09      06
21:21 < calvinalvin> |---\   |---\   |---\   |---\
21:21 < calvinalvin> 00  01  02  03
21:21 < calvinalvin> NumLeaves still stays at 6
21:22 < calvinalvin> Not sure how this effects your implementation adiabat
21:23 < calvinalvin> Ah one downside would be that you can't do bin(numLeaves) to find how many roots there are if you do this
21:23 < calvinalvin> hm...
--- Log closed Tue Jul 05 00:00:12 2022