王位继承

jscw 发表于 2019-3-20 19:42
not exactly. the way to handle Tom II's children is the same as the way to handle Tom's children.
...

这当然不是什么new technology， 可是按照你的说法，只maintain一个younger brother pointer 是做不到的，包括你的链接里面也写的很清楚，每一层下面也是一个list，而不是一个指针。当你新加入一个node的时候，当前只有parent信息，要如何update当前node的brother信息？ 所以parent应该有一个child list. 这是我想说的

莫可可小姐 发表于 2019-3-21 03:13
这当然不是什么new technology， 可是按照你的说法，只maintain一个younger brother pointer 是做不到的 ...

start to write the code and the details will be clear. imho.

I also believe O(1) cannot cover all the cases. what if the new born does not have any younger brother, and his elder brothers have many children descendants, we should insert this new born after all the descendants of all his elder brothers, no matter whether his brother are dead or not.
1) in that case, only with younger brother pointer, we do not know where to insert
2) if his elder brothers are dead, but his nephews(his brothers' descendants) are alive, since the elder brother is already removed from orderlies,
we do not know where to insert.
I believe we need more information, probably we need a pointer for the right most node in a subtree, not just a younger brother pointer.

jscw 发表于 2019-3-14 01:50
insert a node just before its younger brother. O(1)

Can you write the complete code for us to check?
I feel probably the best case is log(n) for birth and death.

jscw 发表于 2019-3-21 19:13
start to write the code and the details will be clear. imho.

我是写完了才过来评论的

莫可可小姐 发表于 2019-3-23 07:39
我是写完了才过来评论的

大概写了一下map + dlinkedlist还是可以O（1）的。对于你所说的问题我觉得可以再维护一个lastKid的field，用这个field可以帮助set这个younger brother。

gegeyongfu 发表于 2019-3-24 06:41
大概写了一下map + dlinkedlist还是可以O（1）的。对于你所说的问题我觉得可以再维护一个lastKid的field ...

不好意思，没弄懂，能再解释下嘛？ 假如A有三个孩子a1, a2, a3, a4, 对于A来说lastKid指针指向a4，此时如果a2 去世，那么如何用O（1）更新a1的younger brother 指向a3 ？ 我的解决方法是A的孩子本身也是dlinklist，单用一个指针我没想到如何解决。

莫可可小姐 发表于 2019-3-24 06:49
不好意思，没弄懂，能再解释下嘛？ 假如A有三个孩子a1, a2, a3, a4, 对于A来说lastKid指针指向a4，此时如 ...

这种情况我们可以用older brother field 去set啊。。在我的这个node的def里面有5个field，lastKid， ybro， obro，next， prev。 next和prev是为了维护getOrder那个list用的

gegeyongfu 发表于 2019-3-24 06:52
这种情况我们可以用older brother field 去set啊。。在我的这个node的def里面有5个field，lastKid， ybro ...

对呀，如果你有ybro 和 obro两个指针就相当于parent的孩子本身也是一个dlinklist

tbian 发表于 2019-3-22 03:19
I also believe O(1) cannot cover all the cases. what if the new born does not have any younger broth ...

I agree, we need to know the last person (right most) in each subtree