87 lines
3.0 KiB
Markdown
87 lines
3.0 KiB
Markdown
对一棵初始为空的高度平衡树（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 |