Daily Archives: September 10, 2012

skip list

http://blog.csdn.net/caoeryingzi/article/details/6018070

Posted in Uncategorized | Leave a comment

胜者树与败者树

胜者树与败者树    一、胜者树         胜者树的一个优点是,如果一个选手的值改变了,可以很容易地修改这棵胜者树。只需要沿着从该结点到根结点的路径修改这棵二叉树,而不必改变其他比赛的结果。 Fig. 1 Fig.1是一个胜者树的示例。规定数值小者胜。 1.         b3 PK b4,b3胜b4负,内部结点ls[4]的值为3; 2.         b3 PK b0,b3胜b0负,内部结点ls[2]的值为3; 3.         b1 PK b2,b1胜b2负,内部结点ls[3]的值为1; 4.         b3 PK b1,b3胜b1负,内部结点ls[1]的值为3。. 当Fig. 1中叶子结点b3的值变为11时,重构的胜者树如Fig. 2所示。 1.         b3 PK b4,b3胜b4负,内部结点ls[4]的值为3; 2.         b3 PK b0,b0胜b3负,内部结点ls[2]的值为0; 3.         b1 PK b2,b1胜b2负,内部结点ls[3]的值为1; 4.         … Continue reading

Posted in Uncategorized | Leave a comment