伸展树

维基百科，自由的百科全书
跳转至： 导航、 搜索

伸展树（英语：Splay Tree）是一种二叉查找树，它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和羅伯特·塔揚创造。

它的优势在于不需要记录用于平衡树的冗余信息。

在伸展树上的一般操作都基于伸展操作。

假设想要对一个二叉查找树执行一系列的查找操作。为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法， 在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。

优点[编辑]

  • 实现起来简单——相对于红黑树、AVL树等其他平衡树来说，伸展树实现起来更简单。
  • 可靠的性能——它的平均效率在平衡树的家族里面是可观的。
  • 存储所需的内存少——伸展树无需记录额外的什么值来维护树的信息，相对于其他平衡树，内存占用要小。
  • 支持可持久化——可以将其改造成可持久化伸展树。可持久化数据结构允许查询修改之前数据结构的信息，对于一般的数据结构，每次操作都有可能移除一些信息，而可持久化的数据结构允许在任何时间查询到之前某个版本的信息。可持久化这一特性在函数式编程当中非常有用。另外，可持久化伸展树每次一般操作的均摊复杂度是O(log n)

缺点[编辑]

伸展树最显著的缺点是它有可能会变成一条链。这种情况可能发生在以非降顺序访问n个元素之后。然而均摊的最坏情况是对数级的——O(log n)

实现[编辑]

以下是伸展树的C++实现（用指针实现）

#include <functional>
 
#ifndef SPLAY_TREE
#define SPLAY_TREE
 
template< typename T, typename Comp = std::less< T > >
class splay_tree {
private:
  Comp comp;
  unsigned long p_size;
 
  struct node {
    node *left, *right;
    node *parent;
    T key;
    node( const T& init = T( ) ) : left( 0 ), right( 0 ), parent( 0 ), key( init ) { }
  } *root;
 
  void left_rotate( node *x ) {
    node *y = x->right;
    x->right = y->left;
    if( y->left ) y->left->parent = x;
    y->parent = x->parent;
    if( !x->parent ) root = y;
    else if( x == x->parent->left ) x->parent->left = y;
    else x->parent->right = y;
    y->left = x;
    x->parent = y;
  }
 
  void right_rotate( node *x ) {
    node *y = x->left;
    x->left = y->right;
    if( y->right ) y->right->parent = x;
    y->parent = x->parent;
    if( !x->parent ) root = y;
    else if( x == x->parent->left ) x->parent->left = y;
    else x->parent->right = y;
    y->right = x;
    x->parent = y;
  }
 
  void splay( node *x ) {
    while( x->parent ) {
      if( !x->parent->parent ) {
        if( x->parent->left == x ) right_rotate( x->parent );
        else left_rotate( x->parent );
      } else if( x->parent->left == x && x->parent->parent->left == x->parent ) {
        right_rotate( x->parent->parent );
        right_rotate( x->parent );
      } else if( x->parent->right == x && x->parent->parent->right == x->parent ) {
        left_rotate( x->parent->parent );
        left_rotate( x->parent );
      } else if( x->parent->left == x && x->parent->parent->right == x->parent ) {
        right_rotate( x->parent );
        left_rotate( x->parent );
      } else {
        left_rotate( x->parent );
        right_rotate( x->parent );
      }
    }
  }
 
  void replace( node *u, node *v ) {
    if( !u->parent ) root = v;
    else if( u == u->parent->left ) u->parent->left = v;
    else u->parent->right = v;
    if( v ) v->parent = u->parent;
  }
 
  node* subtree_minimum( node *u ) {
    while( u->left ) u = u->left;
    return u;
  }
 
  node* subtree_maximum( node *u ) {
    while( u->right ) u = u->right;
    return u;
  }
public:
  splay_tree( ) : root( 0 ), p_size( 0 ) { }
 
  void insert( const T &key ) {
    node *z = root;
    node *p = 0;
 
    while( z ) {
      p = z;
      if( comp( z->key, key ) ) z = z->right;
      else z = z->left;
    }
 
    z = new node( key );
    z->parent = p;
 
    if( !p ) root = z;
    else if( comp( p->key, z->key ) ) p->right = z;
    else p->left = z;
 
    splay( z );
    p_size++;
  }
 
  node* find( const T &key ) {
    node *z = root;
    while( z ) {
      if( comp( z->key, key ) ) z = z->right;
      else if( comp( key, z->key ) ) z = z->left;
      else return z;
    }
    return 0;
  }
 
  void erase( const T &key ) {
    node *z = find( key );
    if( !z ) return;
 
    splay( z );
 
    if( !z->left ) replace( z, z->right );
    else if( !z->right ) replace( z, z->left );
    else {
      node *y = subtree_minimum( z->right );
      if( y->parent != z ) {
        replace( y, y->right );
        y->right = z->right;
        y->right->parent = y;
      }
      replace( z, y );
      y->left = z->left;
      y->left->parent = y;
    }
 
    p_size--;
  }
 
  const T& minimum( ) { return subtree_minimum( root )->key; }
  const T& maximum( ) { return subtree_maximum( root )->key; }
 
  bool empty( ) const { return root == 0; }
  unsigned long size( ) const { return p_size; }
};
 
#endif // SPLAY_TREE


以下是C#的Splay树实现

using System;
using System.Collections.Generic;
 
namespace Trees {
	class SplayNode<T> where T : IComparable 
	{
		public SplayNode<T> Left = null;
		public SplayNode<T> Right = null;
		public SplayNode<T> Parent = null;
		public T Node;
	}
	class SplayTree<T> where T : IComparable
	{
		public SplayTree()
		{
			Root = null;
		}
 
		public void Insert(T node)
		{
			if(node == null)
			{
				return;
			}
			SplayNode<T> z = Root;
			SplayNode<T> p = null;
			while (z != null)
			{
				p = z;
				if(node.CompareTo(p.Node) < 0)
				{
					z = z.Right;
				}
				else
				{
					z = z.Left;
				}
			}
			z = new SplayNode<T>();
			z.Node = node;
			z.Parent = p;
			if (p == null)
			{
				Root = z;
			}
			else if (node.CompareTo(p.Node) < 0)
			{
				p.Right = z;
			}
			else
			{
				p.Left = z;
			}
			Splay(z);
			Count++;
		}
 
		public int Find(T node)
		{
			SplayNode<T> find = FindNode(node);
			if (find != null)
			{
				node = find.Node;
				Splay(find);
			}
			return Depth;
		}
 
		public void Remove(T node)
		{
			SplayNode<T> find = FindNode(node);
			Remove(find);
		}
 
		private void Remove(SplayNode<T> node)
		{
			if (node == null)
			{
				return;
			}
			Splay(node);
			if( (node.Left != null) && (node.Right !=null))
			{ 
				SplayNode<T> min = node.Left;
				while(min.Right!=null)
				{
					min = min.Right;
				}
				min.Right = node.Right;
				node.Right.Parent = min;
				node.Left.Parent = null;
				Root = node.Left;
			}
			else if (node.Right != null)
			{
				node.Right.Parent = null;
				Root = node.Right;
			} 
			else if( node.Left !=null)
			{
				node.Left.Parent = null;
				Root = node.Left;
			}
			else
			{
				Root = null;
			}
			node.Parent = null;
			node.Left = null;
			node.Right = null;
			node = null;
			Count--;
		}
 
		private SplayNode<T> FindNode(T node)
		{
			SplayNode<T> z = Root;
			while (z != null)
			{
				if (node.CompareTo(z.Node) < 0)
				{
					z = z.Right;
				} 
				else if (node.CompareTo(z.Node) > 0)
				{
					z = z.Left;
				}
				else
				{
					return z;
				}
			}
			return null;
		}
 
		void MakeLeftChildParent(SplayNode<T> c, SplayNode<T> p)
		{
			if ((c == null) || (p == null) || (p.Left != c) || (c.Parent != p))
			{
				throw new Exception("WRONG");
			}
			if (p.Parent != null)
			{
				if (p == p.Parent.Left)
				{
					p.Parent.Left = c;
				} 
				else 
				{
					p.Parent.Right = c;
				}
			}
			if (c.Right != null)
			{
				c.Right.Parent = p;
			}
			c.Parent = p.Parent;
			p.Parent = c;
			p.Left = c.Right;
			c.Right = p;
		}
 
		void MakeRightChildParent(SplayNode<T> c, SplayNode<T> p)
		{
			if ((c == null) || (p == null) || (p.Right != c) || (c.Parent != p))
			{
				throw new Exception("WRONG");
			}
			if (p.Parent != null)
			{
				if (p == p.Parent.Left)
				{
					p.Parent.Left = c;
				} 
				else
				{
					p.Parent.Right = c;
				}
			}
			if (c.Left != null)
			{
				c.Left.Parent = p;
			}
			c.Parent = p.Parent;
			p.Parent = c;
			p.Right = c.Left;
			c.Left = p;
		}
 
		void Splay(SplayNode<T> x)
		{
			while (x.Parent != null)
			{
				SplayNode<T> Parent = x.Parent;
				SplayNode<T> GrandParent = Parent.Parent;
				if (GrandParent == null)
				{
					if (x == Parent.Left)
					{
						MakeLeftChildParent(x, Parent);
					} 
					else
					{
						MakeRightChildParent(x, Parent);
					}
				} 
				else
				{
					if (x == Parent.Left)
					{
						if (Parent == GrandParent.Left)
						{
							MakeLeftChildParent(Parent, GrandParent);
							MakeLeftChildParent(x, Parent);
						}
						else 
						{
							MakeLeftChildParent(x, x.Parent);
							MakeRightChildParent(x, x.Parent);
						}
					}
					else 
					{
						if (Parent == GrandParent.Left)
						{
							MakeRightChildParent(x, x.Parent);
							MakeLeftChildParent(x, x.Parent);
						} 
						else 
						{
							MakeRightChildParent(Parent, GrandParent);
							MakeRightChildParent(x, Parent);
						}
					}
				}
			}
            		Root = x;
		}
 
		public void Clear()
		{
			while (Root != null) 
			{
				Remove(Root);
			}
		}
 
		SplayNode<T> Root = null;
		int Count = 0;
	}
}
二叉树
自平衡二叉查找树
B树
Trie
二叉空间分割（BSP）树
非二叉树
空间数据分割树
其他树
取自“http://zh.wikipedia.org/w/index.php?title=伸展树&oldid=34311913”