算法导论-14-2-Josephus排列

题目： Josephus问题的定义如下：假设n个人排成环形，且有以正整数m<=n。从某个制定的人开始，沿环报数，每遇到第m个人就让其出列，且报数进行下去。这个过程一直进行到所有人都出列为止。每个人出列的次序定义了整数1，2，...，n的(n, m)-Josephus排列。例如，(7,3)-Josephus排列为<3,6,2,7,5,1,4>。 a)假设m为整数。请描述一个O(n)时间的算法，使之对给定的整数n，输出(n, m)-Josephus排列。 b)假设m不是个常数。请描述一个O(nlgn)时间的算法，使给定的整数n和m，输出(n, m)-Josephus排列。 思考： 利用14.1中的动态顺序统计，假设刚刚删除的是剩余点中的第start个点（初始时为0），此时还剩下t个点，那么下一个要删除的是剩余点的第（start+m-1）%t个点 步骤1：基础数据结构 红黑树 步骤2：附加信息 size[x]：以x为根的子树的（内部）结点数（包括x本身），即子树的大小。size[nil[T]]=0 步骤3：对信息的维护 size[x] = size[left[x]] + size[right[x]] + 1 插入操作：从插入结点到根结点都要更新O(lgn) 旋转操作：只需要更新旋转轴上的两个点O(1) 删除操作：从删除结点的父结点开始到根结点都要更新O(lgn) 代码： https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter14/exercise14_2.cpp