参考过好几篇关于将伸展树的代码，发现看不懂。看图能看懂原理。就尝试自己实现了下。
自顶向上的算法。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Threading;
using System.IO;
using System.Collections;
using System.Threading.Tasks; namespace ConsoleApplication2
{
public class Program
{
public static void Main()
{
SplayTree<int> tree = new SplayTree<int>();
tree.Insert();
tree.Insert();
tree.Insert();
tree.Insert();
tree.Insert();
tree.Insert();
tree.Insert(); tree.Search(); Console.Read();
}
} public class SplayTreeNode<T> where T : IComparable
{
public T Key { get; set; }
public SplayTreeNode<T> LeftNode { get; set; }
public SplayTreeNode<T> RightNode { get; set; }
public SplayTreeNode(T _key, SplayTreeNode<T> _leftNode, SplayTreeNode<T> _rightNode)
{
this.Key = _key;
this.LeftNode = _leftNode;
this.RightNode = _rightNode;
} public SplayTreeNode()
{ } public override string ToString()
{
return Key + "";
}
} public class SplayTree<T> where T : IComparable
{
public SplayTreeNode<T> RootNode { get; set; } public void Splay(T key)
{
RootNode = Splay(RootNode, key);
} public SplayTreeNode<T> Splay(SplayTreeNode<T> node, T key)
{
if (node == null)
{
return node;
} return null;
} public void Insert(T key)
{
var node = RootNode;
if (node == null)
{
RootNode = new SplayTreeNode<T>(key, null, null);
return;
} while (true)
{
int result = node.Key.CompareTo(key);
if (result > )
{
if (node.LeftNode == null)
{
node.LeftNode = new SplayTreeNode<T>(key, null, null);
}
node = node.LeftNode;
}
else if (result < )
{
if (node.RightNode == null)
{
node.RightNode = new SplayTreeNode<T>(key, null, null);
}
node = node.RightNode;
}
else
{
break;
}
}
} public SplayTreeNode<T> Search(T key)
{
Search(RootNode, key);
return RootNode;
} private void Search(SplayTreeNode<T> node, T key)
{
int result = node.Key.CompareTo(key);
if (result < )
{
node= RightRotation(node);
if (node.RightNode != null)
{
RootNode = node;
}
else
{
Search(node, key);
} }
else if (result > )
{
node = LeftRotation(node);
if (node.LeftNode != null)
{
RootNode = node;
}else
{
Search(node, key);
}
}
else
{
RootNode = node;
}
} private SplayTreeNode<T> LeftRotation(SplayTreeNode<T> node)
{
SplayTreeNode<T> temp = node.LeftNode;
node.LeftNode = temp.RightNode;
temp.RightNode = node;
return temp;
} private SplayTreeNode<T> RightRotation(SplayTreeNode<T> node)
{
SplayTreeNode<T> temp = node.RightNode;
node.RightNode = temp.LeftNode;
temp.LeftNode = node;
return temp;
}
}
}