一 问题描述

实现对伸展树的基本操作

二 输入和输出

1 输入

有 5 种基本操作，格式如下

0：退出程序

1 val：将 val 插入伸展树中

2：查找该伸展树的最大值

3：查找该伸展树的最小值

4 val：将 val 从伸展树中删掉

2 输出

针对操作1和操作4，进行中序遍历打印，针对操作2，打印最大值，针对操作3，打印最小值。

三 输入和输出样例

1 输入样例

1 5

1 6

1 2

1 3

2

3

1 7

1 8

4 6

0

2 输出样例

5

5 6

2 5 6

2 3 5 6

6

2

2 3 5 6 7

2 3 5 6 7 8

2 3 5 7 8

四 代码

package com.platform.modules.alg.alglib.p392;public class P392 {public String output = "";private int maxn = 100005;int n, cnt, root; // 操作类型，结点存储下标累计，树根private node tr[] = new node[maxn];public P392() {for (int i = 0; i < tr.length; i++) {tr[i] = new node();}}void init() {cnt = root = 0;tr[0].son[0] = tr[0].son[1] = 0;}// 中序遍历测试void print(int rt) {if (rt == 0) return;if (tr[rt].son[0] != 0)print(tr[rt].son[0]);output += tr[rt].val + " ";if (tr[rt].son[1] != 0)print(tr[rt].son[1]);}// 生成新结点int New(int father, int val) {tr[++cnt].fa = father;tr[cnt].val = val;tr[cnt].son[0] = tr[cnt].son[1] = 0;return cnt;}// 旋转void Rotate(int x) {int y = tr[x].fa, z = tr[y].fa;int c = (tr[y].son[0] == x) ? 1 : 0;tr[y].son[1 - c] = tr[x].son[c];tr[tr[x].son[c]].fa = y;tr[x].fa = z;if (z > 0)tr[z].son[tr[z].son[1] == y ? 1 : 0] = x;tr[x].son[c] = y;tr[y].fa = x;}// 双层伸展，将 x 旋转为 goal 的儿子void Splay(int x, int goal) {while (tr[x].fa != goal) {int y = tr[x].fa, z = tr[y].fa;if (z != goal) {if (((tr[z].son[0] == y ? 1 : 0) ^ (tr[y].son[0] == x ? 1 : 0)) == 0) {Rotate(y);} else {Rotate(x);}}Rotate(x);}// 如果 goal 是 0，则更新根为 xif (goal == 0) root = x;}void Insert(int val) {//插入值valint x;for (x = root; tr[x].son[(tr[x].val < val) ? 1 : 0] > 0; x = tr[x].son[(tr[x].val < val) ? 1 : 0]) ; // 找位置tr[x].son[(tr[x].val < val) ? 1 : 0] = New(x, val);Splay(tr[x].son[(tr[x].val < val) ? 1 : 0], 0); // 新插入结点旋转到根}// 查找值 valboolean Find(int val) {int x = root;while (x > 0) {if (tr[x].val == val) {Splay(x, 0); // x旋转到根return true;}if (tr[x].son[(tr[x].val < val) ? 1 : 0] > 0)x = tr[x].son[(tr[x].val < val) ? 1 : 0];else { // 查找失败Splay(x, 0); // x 旋转到根return false;}}return false;}// 找最大值结点void Findmax() {int x = root;if (x > 0) {while (tr[x].son[1] > 0)x = tr[x].son[1];Splay(x, 0); // x 旋转到根}}// 找最小值结点void Findmin() {int x = root;if (x > 0) {while (tr[x].son[0] > 0)x = tr[x].son[0];Splay(x, 0); // x 旋转到根}}boolean Split(int val, SubTreeRoot subTreeRoot) {if (Find(val)) { // 查找成功subTreeRoot.t1 = tr[root].son[0];subTreeRoot.t2 = tr[root].son[1];root = subTreeRoot.t1;tr[subTreeRoot.t1].fa = tr[subTreeRoot.t2].fa = 0;return true;}return false;}void Join(int t1, int t2) {if (t1 > 0) {Findmax(); // 查找 t1 的最大值tr[root].son[1] = t2;tr[t2].fa = root;} elseroot = t2;}void Delete(int val) { // 删除值 valSubTreeRoot subTreeRoot = new SubTreeRoot();subTreeRoot.t1 = 0;subTreeRoot.t2 = 0;if (Split(val, subTreeRoot))Join(subTreeRoot.t1, subTreeRoot.t2);}public String cal(String input) {String[] line = input.split("\n");init();int count = 0;while (true) {String[] opt = line[count++].split(" ");n = Integer.parseInt(opt[0]);switch (n) {case 0:return output;case 1:Insert(Integer.parseInt(opt[1]));print(root);output += "\n";break;case 2:Findmax();output += tr[root].val + "\n";break;case 3:Findmin();output += tr[root].val + "\n";break;case 4:Delete(Integer.parseInt(opt[1]));print(root);output += "\n";break;}}}
}class node {int son[] = new int[2]; // 左右孩子 0,1int val, fa; // 值，父亲
}class SubTreeRoot {int t1;int t2;
}

五 测试

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！