关于替罪羊树的三个问题
查看原帖
关于替罪羊树的三个问题
69796
林聪楼主2021/11/25 18:32
1.惰性删除不会影响时间复杂度吗?

(1)指erase的时候只是cnt--,结点依然在那个地方,直到重构的时候才delete掉。

(2)测了一下惰性删除和实时删除,用时相差不大。

2.insert和erase的时候,一路上每碰到一个坏点(指子树不平衡)就立马重构,这样也不会影响时间复杂度吗?

(1)测了一下重构最高的一个点和实时重构,用时相差不大。

3.是否需要重构的关键size,应该用结点数,还是数集大小?

(1)换句话说,假设根结点是2,左儿子是1,但是有100个,右子树是条3-100的链,如果用结点数的话,那么应当重构了(左边1个结点,右边98个结点);而如果用数集大小的话,则不应重构(左边100个数,右边98个数)。当然这个例子在实际中不会出现,就是意思一下。

(2)测了一下两种size,用时相差也不大。

跪求以上问题的解答

2021/11/25 18:32
加载中...