3.0 KiB
对一棵初始为空的高度平衡树（AVL树）进行若干插入或删除操作，请输出旋转信息和最后得到的AVL树。
备注： 当有多种旋转方案时，优先选择旋转次数少的方案。
输入格式: 输出包含多组数据。对于每组数据：输入第一行为一个整数 T，表示操作数目；随后 T 行，每行为Insert K（表示插入关键词为K的结点，若树中已有关键词为K的结点，则不插入）或Remove K（表示删除关键词为K的结点，若树中无关键词为K的结点，则不删除），其中K为整数； T 不超过2×10 5 。
输出格式: 对于每组数据，首先输出一行CaseX：表示第X组数据，X≥1，然后输出2部分。
输出的第1部分为平衡的信息。对于每个Insert/Remove操作： 若未引起结点失衡，则不输出任何信息。 若引起了结点失衡从而导致旋转，则依次输出旋转的信息。具体为：首先输出该Insert或Remove操作，其后加一个冒号和一个空格。若该操作引起结点A失衡，则输出"Rebalance subtree rooted at node A on level L "，即平衡以A为根的子树，其中结点A在树的第L层，A为结点的关键词。若平衡以A为根的子树需要单旋转，则接着输出" with X rotation. " ；若平衡以A为根的子树需要双旋转，则输出" with X rotation and Y rotation. " ；其中X和Y为left或right。注意Remove操作可能引起多个点失衡，应对自底向上的每个失衡点都输出旋转信息，即可能输出多句话，每句话后一个空格。 输出的第2部分为最后得到的高度平衡树的中根序列和先根序列，序列中每个整数后一个空格，两个序列之间用空行间隔。 若存在第1部分，则第1部分和第2部分之间用空行间隔。若没有第1部分（给出的所有Insert/Remove操作都没引起旋转操作），则直接输出第2部分。 每组数据之后都有一个空行。
输入样例: 16 Insert 17 Insert 31 Insert 13 Insert 11 Insert 20 Insert 35 Insert 25 Insert 8 Insert 4 Insert 11 Insert 24 Insert 40 Insert 27 Insert 9 Remove 17 Remove 13 13 Insert 5 Insert 3 Insert 8 Insert 2 Insert 4 Insert 7 Insert 10 Insert 1 Insert 6 Insert 9 Insert 11 Insert 12 Remove 4 3 Insert 6 Insert 5 Insert 8 输出样例: Case 1: Insert 8: Rebalance subtree rooted at node 13 on level 1 with right rotation. Insert 24: Rebalance subtree rooted at node 20 on level 2 with right rotation and left rotation. Remove 17: Rebalance subtree rooted at node 24 on level 2 with left rotation. Remove 13: Rebalance subtree rooted at node 11 on level 1 with right rotation.
4 8 9 11 20 24 25 27 31 35 40
20 8 4 11 9 31 25 24 27 35 40
Case 2: Remove 4: Rebalance subtree rooted at node 3 on level 1 with right rotation. Rebalance subtree rooted at node 5 on level 0 with left rotation.
1 2 3 5 6 7 8 9 10 11 12
8 5 2 1 3 7 6 10 9 11 12
Case 3: 5 6 8
6 5 8
Code Size Limit 16 KB Time Limit 500 ms Memory Limit 64 MB Stack size limit 8192 KB