Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Runtime.InteropServices;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;
public static class P
{
public static void Main()
{
int n = 2000;
SplayTree<int> tree = new SplayTree<int>();
HashSet<int> set = new HashSet<int>();
Random rng = new Random();
while (true)
{
var a = rng.Next(0, n);
//var a = int.Parse(Console.ReadLine());
Debug.Assert(tree.Add(a) == set.Add(a));
Debug.Assert(tree.Count == set.Count);
}
}
}
class SplayTree<T> where T : IComparable<T>
{
Node root;
public int Count => root?.Size ?? 0;
public bool Add(T value)
{
if (root == null) { root = new Node() { Value = value, Size = 1 }; return true; }
Splay(value);
var compareRes = value.CompareTo(root.Value);
if (compareRes < 0 /*value < root.Value*/)
{
var topNode = new Node() { Value = value, Left = root.Left, Right = root };
root.Left = null;
root.CalcSize();
root = topNode;
}
else if (compareRes > 0 /*value > root.Value*/)
{
var topNode = new Node() { Value = value, Left = root, Right = root.Right };
root.Right = null;
root.CalcSize();
root = topNode;
}
else return false;
root.CalcSize();
return true;
}
public bool Remove(T value)
{
if (root == null) return false;
Splay(value);
if (value.CompareTo(root.Value) != 0) return false;
var lRoot = root.Left;
var rRoot = root.Right;
if (lRoot == null) root = rRoot;
else if (rRoot == null) root = lRoot;
else
{
root = lRoot;
Splay(value);
root.Right = rRoot;
root.CalcSize();
}
return true;
}
private void Splay(T value)
{
if (root == null) return;
Node leftRoot = null;
Node rightRoot = null;
Node currentNode = root;
while (true)
{
Node tmpSubtree;
int direction, compareRes;
compareRes = value.CompareTo(currentNode.Value);
if (compareRes < 0/*value < currentNode.Value*/)
{
if (currentNode.Left == null) break;
direction = -1;
tmpSubtree = currentNode;
currentNode = tmpSubtree.Left;
//tmpSubtree.Left = null; ←あとで追加できる
}
else if (compareRes > 0/*value > currentNode.Value*/)
{
if (currentNode.Right == null) break;
direction = 1;
tmpSubtree = currentNode;
currentNode = tmpSubtree.Right;
//tmpSubtree.Right = null; ←あとで追加できる
}
else break;
compareRes = value.CompareTo(currentNode.Value);
if (compareRes < 0 //value < currentNode.Value
&& currentNode.Left != null)
{
if (direction == -1)
{
//Zig-Zig
tmpSubtree.Left = currentNode.Right;
currentNode.Right = tmpSubtree;
var nextNode = currentNode.Left;
currentNode.Left = rightRoot;
rightRoot = currentNode;
currentNode = nextNode;
}
else
{
//Zig-Zag
tmpSubtree.Right = leftRoot;
leftRoot = tmpSubtree;
var nextNode = currentNode.Left;
currentNode.Left = rightRoot;
rightRoot = currentNode;
currentNode = nextNode;
}
}
else if (compareRes > 0 //value > currentNode.Value
&& currentNode.Right != null)
{
if (direction == 1)
{
//Zig-Zig
tmpSubtree.Right = currentNode.Left;
currentNode.Left = tmpSubtree;
var nextNode = currentNode.Right;
currentNode.Right = leftRoot;
leftRoot = currentNode;
currentNode = nextNode;
}
else
{
//Zig-Zag
tmpSubtree.Left = rightRoot;
rightRoot = tmpSubtree;
var nextNode = currentNode.Right;
currentNode.Right = leftRoot;
leftRoot = currentNode;
currentNode = nextNode;
}
}
else
{
//Zig
if (direction == -1)
{
tmpSubtree.Left = rightRoot;
rightRoot = tmpSubtree;
}
else
{
tmpSubtree.Right = leftRoot;
leftRoot = tmpSubtree;
}
break;
}
tmpSubtree.CalcSize();
}
root = currentNode;
//foldタイム
while (leftRoot != null)
{
var nextRoot = leftRoot.Right;
leftRoot.Right = root.Left;
leftRoot.CalcSize();
root.Left = leftRoot;
leftRoot = nextRoot;
}
while (rightRoot != null)
{
var nextRoot = rightRoot.Left;
rightRoot.Left = root.Right;
rightRoot.CalcSize();
root.Right = rightRoot;
//rightRoot.Right = null;
rightRoot = nextRoot;
}
root.CalcSize();
}
class Node
{
public T Value;
public Node Left;
public Node Right;
public int Size;
public void CalcSize()
{
if (this == Left) throw new Exception();
if (this == Right) throw new Exception();
Size = 1 + (Left?.Size ?? 0) + (Right?.Size ?? 0);
}
}
}
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Runtime.InteropServices;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;
public static class P
{
public static void Main()
{
int n = 2000;
SplayTree<int> tree = new SplayTree<int>();
HashSet<int> set = new HashSet<int>();
Random rng = new Random();
while (true)
{
var a = rng.Next(0, n);
Debug.Assert(tree.Add(a) == set.Add(a));
}
}
}
class SplayTree<T> where T : IComparable<T>
{
Node root;
public bool Add(T value)
{
if (root == null) { root = new Node() { Value = value, Size = 1 }; return true; }
Splay(value);
var compareRes = value.CompareTo(root.Value);
if (compareRes < 0 /*value < root.Value*/)
{
var topNode = new Node() { Value = value, Left = root.Left, Right = root };
root.Left = null;
root.CalcSize();
root = topNode;
}
else if (compareRes > 0 /*value > root.Value*/)
{
var topNode = new Node() { Value = value, Left = root, Right = root.Right };
root.Right = null;
root.CalcSize();
root = topNode;
}
else return false;
root.CalcSize();
return true;
}
public bool Remove(T value)
{
if (root == null) return false;
Splay(value);
if (value.CompareTo(root.Value) != 0) return false;
var lRoot = root.Left;
var rRoot = root.Right;
if (lRoot == null) root = rRoot;
else if (rRoot == null) root = lRoot;
else
{
root = lRoot;
Splay(value);
root.Right = rRoot;
root.CalcSize();
}
return true;
}
private void Splay(T value)
{
if (root == null) return;
Node leftRoot = null;
Node rightRoot = null;
Node leftJoint = null;
Node rightJoint = null;
Node currentNode = root;
while (true)
{
Node tmpSubtree;
int direction, compareRes;
compareRes = value.CompareTo(currentNode.Value);
if (compareRes < 0/*value < currentNode.Value*/)
{
if (currentNode.Left == null) break;
direction = -1;
tmpSubtree = currentNode;
currentNode = tmpSubtree.Left;
tmpSubtree.Left = null;
}
else if (compareRes > 0/*value > currentNode.Value*/)
{
if (currentNode.Right == null) break;
direction = 1;
tmpSubtree = currentNode;
currentNode = tmpSubtree.Right;
tmpSubtree.Right = null;
}
else break;
compareRes = value.CompareTo(currentNode.Value);
if (compareRes < 0 //value < currentNode.Value
&& currentNode.Left != null)
{
if (direction == -1)
{
//Zig-Zig
tmpSubtree.Left = currentNode.Right;
currentNode.Right = tmpSubtree;
if (rightRoot == null) rightRoot = (rightJoint = currentNode);
else rightJoint = (rightJoint.Left = currentNode);
currentNode = currentNode.Left;
//rightJoint.Left = null;
}
else
{
//Zig-Zag
if (leftRoot == null) { leftJoint = (leftRoot = tmpSubtree); }
else { leftJoint = (leftJoint.Right = tmpSubtree); }
if (rightRoot == null) { rightJoint = (rightRoot = currentNode); }
else { rightJoint = (rightJoint.Left = currentNode); ; }
currentNode = rightJoint.Left;
//rightJoint.Left = null;
}
}
else if (compareRes > 0 //value > currentNode.Value
&& currentNode.Right != null)
{
if (direction == 1)
{
//Zig-Zig
tmpSubtree.Right = currentNode.Left;
currentNode.Left = tmpSubtree;
if (leftRoot == null) leftRoot = (leftJoint = currentNode);
else leftJoint = (leftJoint.Right = currentNode);
currentNode = currentNode.Right;
//leftJoint.Right = null;
}
else
{
//Zig-Zag
if (rightRoot == null) { rightJoint = (rightRoot = tmpSubtree); }
else { rightJoint = (rightJoint.Left = tmpSubtree); }
if (leftRoot == null) { leftJoint = (leftRoot = currentNode); }
else { leftJoint = (leftJoint.Right = currentNode); ; }
currentNode = leftJoint.Right;
//leftJoint.Right = null;
}
}
else
{
//Zig
if (direction == -1)
{
if (rightRoot == null) { rightJoint = (rightRoot = tmpSubtree); }
else { rightJoint = (rightJoint.Left = tmpSubtree); }
}
else
{
if (leftRoot == null) { leftJoint = (leftRoot = tmpSubtree); }
else { leftJoint = (leftJoint.Right = tmpSubtree); }
}
break;
}
}
if (leftJoint != null) leftJoint.Right = null;
if (rightJoint != null) rightJoint.Left = null;
if (currentNode.Left != null)
if (leftRoot == null) leftRoot = currentNode.Left;
else leftJoint.Right = currentNode.Left; //currentNode.Left = null
if (currentNode.Right != null)
if (rightRoot == null) rightRoot = currentNode.Right;
else rightJoint.Left = currentNode.Right; //currentNode.Right = null
currentNode.Left = leftRoot;
currentNode.Right = rightRoot;
root = currentNode;
}
class Node
{
public T Value;
public Node Left;
public Node Right;
public int Size;
public void CalcSize() => Size = 1 + (Left?.Size ?? 0) + (Right?.Size ?? 0);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment