本页使用了标题或全文手工转换

伸展树

维基百科,自由的百科全书
(重定向自伸展樹
跳到导航 跳到搜索
伸展树
类型
发明时间 1985
发明者 丹尼尔·斯立特羅伯特·塔揚
大O符号时间复杂度
算法 平均 最差
空间 O(n) O(n)
搜索 O(log n) 均摊O(log n)
插入 O(log n) 均摊O(log n)
删除 O(log n) 均摊O(log n)

伸展树英语:Splay Tree)是一种能够自我平衡的二叉查找树,它能在均摊O(log n)的时间内完成基于伸展(Splay)操作的插入、查找、修改和删除操作。它是由丹尼尔·斯立特Daniel Sleator)和羅伯特·塔揚在1985年发明的[1]

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

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

优点[编辑]

伸展树的自我平衡使其拥有良好的性能,因为频繁访问的节点会被移动到更靠近根节点,进而获得更快的访问速度。

  • 可靠的性能——它的平均效率不输于其他平衡树[2]
  • 存储所需的内存少——伸展树无需记录额外的什么值来维护树的信息,相对于其他平衡树,内存占用要小。

缺点[编辑]

伸展树最显著的缺点是它有可能会变成一条。例如,在以非递减顺序访问全部n个之后就会出现这种情况。此时树的高度对应于最坏情况的时间效率,操作的实际时间效率可能很低。然而均摊的最坏情况是对数级的——O(log n)。

即使以“只读”方式(例如通过查找操作)访问伸展树,其结构也可能会发生变化。这使得伸展树在多线程环境下会变得很复杂。具体而言,如果允许多个线程同时执行查找操作,则需要额外的维护和操作。这也使得它们不适合在纯粹的函数式编程中普遍使用,尽管用于实现优先级队列的方式不多。

操作[编辑]

伸展(splay)[编辑]

当一个节点x被访问过后,伸展操作会将x移动到根节点。为了进行伸展操作,我们会进行一系列的旋转,每次旋转会使x离根节点更近。通过每次访问节点后的伸展操作,最近访问的节点都会离根节点更近,且伸展树也会大致平衡,这样我们就可以得到期望均摊时间复杂度的下界——均摊O(logn)。

每次旋转操作由三个因素决定:

  • x是其父节点p的左儿子还是右儿子
  • p是否为根,如果不是
  • p是其父节点gx的祖父节点)的左儿子还是右儿子

在每次旋转操作后,设置g的儿子为x是很重要的。如果g为空,那么x显然就是根节点了。

共有三种旋转操作,每种都有左旋和右旋两种情况。为了简单起见,对每种旋转操作只展示一种情况。这些旋转操作是:

Zig:当p为根节点时进行。Zig通常只在伸展操作的最后一步进行。

Splay tree zig.svg

Zig-zig:当p不为根节点且xp都为左儿子或都为右儿子时进行。下面这幅图为xp都为左儿子时的情况。在这种情况下,先右旋pg的位置,再右旋xp的位置。

Zigzig.gif

Zig-zag;当p不为根节点且x为左儿子而p为右儿子时进行,反之亦然。在这种情况下,先旋转px的位置,再旋转pg的位置。

Zigzag.gif

连接(join)[编辑]

给出两棵树S和T,且S的所有元素都比T的元素要小。下面的步骤可以把它们连接成一棵树:

  • 伸展S中最大的节点。现在这个节点变为S的根节点,且没有右儿子。
  • 令T的根节点变为其右儿子。

分割(split)[编辑]

插入(insert)[编辑]

删除(delete)[编辑]

查找(find)[编辑]

实现[编辑]

以下是伸展树的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

时间效率分析[编辑]

m次伸展操作的均摊时间效率 [3]

实际时间效率 [4]

参考来源[编辑]

  1. ^ Sleator, Daniel D.; Tarjan, Robert E., Self-Adjusting Binary Search Trees (PDF), Journal of the ACM, 1985, 32 (3): 652–686, doi:10.1145/3828.3835 (英语) 
  2. ^ Goodrich, Michael; Tamassia, Roberto; Goldwasser, Michael. Data Structures and Algorithms in Java 6. John Wiley & Sons, Inc. : 506. ISBN 978-1-118-77133-4 (英语). The surprising thing about splaying is that it allows us to guarantee a logarithmic amortized running time, for insertions, deletions, and searches. 
  3. ^ Splay中的旋转操作用单旋与双旋的区别是什么? - 知乎. www.zhihu.com. [2018-06-23] (中文). 
  4. ^ Splay tree - Wikipedia. [2018-06-23].