计算机科学

首页 > 计算机科学

伸展树

2018-07-27 09:57:34     所属分类:数据结构
伸展树
类型
发明时间 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]

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

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

目录

  • 1 优点
  • 2 缺点
  • 3 操作
    • 3.1 伸展(splay)
    • 3.2 连接(join)
    • 3.3 分割(split)
    • 3.4 插入(insert)
    • 3.5 删除(delete)
    • 3.6 查找(find)
  • 4 实现
  • 5 时间效率分析
  • 6 参考来源

优点

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

  • 可靠的性能——它的平均效率不输于其他平衡树[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 - . [2018-06-23]. 

感谢您的支持,我会继续努力的!

扫码支持
1分,2分不嫌少,钱不钱的无所谓,重要的是你的话语激励我前行!

愿你每天温暖如春!!!

显示全文

取消

感谢您的支持,我会继续努力的!

扫码支持
无需打赏可直接关闭阅读全文
1分,2分不嫌少,钱不钱的无所谓,重要的是你的话语激励我前行!

愿你每天温暖如春!!!


上一篇:顺序表
下一篇:霍夫曼编码
相关推荐