关于替罪羊树的重构
查看原帖
关于替罪羊树的重构
68882
灵华楼主2022/4/27 15:40

RT,对于替罪羊树插入的时候如果树极为不平衡时的重构问题。

现在网上的大部分代码都是往上返回的时候一旦找到一个就立刻重构当前节点。

那为啥不能把路径上深度最小的那个不平衡点记录下来,等到插入函数执行完了,返回到主函数的时候再重构这个记录下来的节点啊?

一个节点的重构并不会影响他父亲的某个儿子的子树大小(即一个节点的重构不会影响他父亲(或祖先)是否需要重构)。但是如果他父亲(或祖先)重构了,那么这个节点也会跟着重构,之前的重构不就没有作用了么?

所以为啥不能记录到最后再重构啊?

我试了试,好像确实过不了,但是不知道原因。(还是我的代码写错了?)

2022/4/27 15:40
加载中...