王位继承

tbian 发表于 2019-3-13 23:43
请问怎么让birth 也是O(1), 我只能想出O(logn)

insert a node just before its younger brother. O(1)

我还以为是白天晚上系列

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

sorry, should be "the youngest older brother"
Say, Here Tom has one son, Tom II, and two brothers, Frank and John. Here Tom points to Frank and Frank points to John via "brother pointer"
  
Tom <-> Tom II <-> Frank <-> John.

Say Tom has another child, Tom III, then Tom uses brother pointer to find Frank, and insert a new node Tom III just before Frank. O(1).

jscw 发表于 2019/03/06 14:09:30
put nodes into double linked list, the double listed list keep the order of inheritance.
Also, has...

一个人死了怎么改变树的结构，比如一个人死了，他的哥哥的子孙又出生了，会不会很buggy？

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

what if younger brother is dead, or his descendants dead? how do we handle death in treeNode, worse case still be O(N) to finish the preorder

tbian 发表于 2019-3-15 09:42
what if younger brother is dead, or his descendants dead? how do we handle death in treeNode, wors ...

death(Tom)

1) use HashMap to find Tom's Node in double linked list, O(1)
2) update the double linked list and associated brother pointer by removing Tom, O(1)
3) remove Tom from HashMap, O(1)

jscw 发表于 2019-3-14 06:28
sorry, should be "the youngest older brother"
Say, Here Tom has one son, Tom II, and two brothers ...

你这里并没有update TomII 的brother pointer，所以在TomII有小孩的时候会出错

14417335 发表于 2019-3-13 22:26
**** 本内容被作者隐藏 ****

请问楼主这是从哪copy过来的？
我一直怀疑是不是真的有很好的方法做到birth和death都O(1)

莫可可小姐 发表于 2019-3-20 07:26
你这里并没有update TomII 的brother pointer，所以在TomII有小孩的时候会出错

not exactly. the way to handle Tom II's children is the same as the way to handle Tom's children.

In a nutshell, each node has two kinds of pointers. One is for double linked list and the other is for their brothers. When birth/death event happens, all related pointers should be modified. HashMap saved the mapping between the name and the node address to have O(1) possible.

This approach is just a variation of skip-list. Nothing new, to be honesty.
http://ticki.github.io/blog/skip-lists-done-right/

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. 这是我想说的