伸展樹

伸展樹
伸展樹
類型	樹
發明時間	1985年
發明者	丹尼爾·斯萊托和羅伯特·塔揚
用大O符號表示的時間複雜度
算法
算法
空間
搜尋
插入
刪除

伸展樹（英語：Splay Tree）是一種能夠自我平衡的二叉查找樹，它能在均攤 $O(\log n)$ 的時間內完成基於伸展（Splay）操作的插入、查找、修改和刪除操作。它是由丹尼爾·斯萊托和羅伯特·塔揚在1985年發明的^[1]。

在伸展樹上的一般操作都基於伸展操作：假設想要對一個二叉查找樹執行一系列的查找操作，為了使整個查找時間更小，被查頻率高的那些條目就應當經常處於靠近樹根的位置。於是想到設計一個簡單方法，在每次查找之後對樹進行調整，把被查找的條目搬移到離樹根近一些的地方。伸展樹應運而生。伸展樹是一種自調整形式的二叉查找樹，它會沿着從某個節點到樹根之間的路徑，通過一系列的旋轉把這個節點搬移到樹根去。

它的優勢在於不需要記錄用於平衡樹的冗餘信息。

優點

伸展樹的自我平衡使其擁有良好的性能，因為頻繁訪問的節點會被移動到更靠近根節點，進而獲得更快的訪問速度。

可靠的性能——它的平均效率不輸於其他平衡樹^[2]。
存儲所需的內存少——伸展樹無需記錄額外的什麼值來維護樹的信息，相對於其他平衡樹，內存占用要小。

缺點

伸展樹最顯著的缺點是它有可能會變成一條鏈。例如，在以非遞減順序訪問全部n個之後就會出現這種情況。此時樹的高度對應於最壞情況的時間效率，操作的實際時間效率可能很低。然而均攤的最壞情況是對數級的—— $O(\log n)$ 。

即使以「只讀」方式（例如通過查找操作）訪問伸展樹，其結構也可能會發生變化。這使得伸展樹在多線程環境下會變得很複雜。具體而言，如果允許多個線程同時執行查找操作，則需要額外的維護和操作。這也使得它們不適合在純粹的函數式編程中普遍使用，儘管用於實現優先級隊列的方式不多。

操作

伸展(splay)

當一個節點x被訪問過後，伸展操作會將x移動到根節點。為了進行伸展操作，我們會進行一系列的旋轉，每次旋轉會使x離根節點更近。通過每次訪問節點後的伸展操作，最近訪問的節點都會離根節點更近，且伸展樹也會大致平衡，這樣我們就可以得到期望均攤時間複雜度的下界——均攤 $O(\log n)$ 。

每次旋轉操作由三個因素決定：

x是其父節點p的左兒子還是右兒子；
p是否為根；
p是其父節點g（x的祖父節點）的左兒子還是右兒子。

在每次旋轉操作後，設置p的兒子為x是很重要的。如果p為空，那麼x顯然就是根節點了。

共有三種旋轉操作，每種都有右旋（Zig）和左旋（Zag）兩種情況。為了簡單起見，對每種旋轉操作只展示一種情況。這些旋轉操作是：

Zig：當p為根節點時進行。Zig通常只在伸展操作的最後一步進行。

Zig-zig和Zag-zag：當p不為根節點且x和p都為左兒子或都為右兒子時進行。下圖為x和p都為左兒子時的情況（即Zig-zig），需先將p右旋到g的位置，再將x右旋到p的位置。

Zig-zag和Zag-zig：當p不為根節點且x為左兒子而p為右兒子時進行，反之亦然。下圖為前述情況（即Zig-zag），需先將x左旋到p到的位置，再將x右旋到g的位置。

連接(join)

給出兩棵樹S和T，且S的所有元素都比T的元素要小。下面的步驟可以把它們連接成一棵樹：

伸展S中最大的節點。現在這個節點變為S的根節點，且沒有右兒子。
令T的根節點變為其右兒子。

分割(split)

給出一棵樹和一個元素x，返回兩棵樹：一棵中所有的元素均小於等於x，另一棵中所有的元素大於x。下面的步驟可以完成這個操作：

伸展x。這樣的話x成為了這棵樹的根所以它的左子樹包含了所有比x小的元素，右子樹包含了所有比x大的元素。

把x的右子樹從樹中分割出來。

插入(insert)

插入操作是一個比較複雜的過程，具體步驟如下: 我們假定要插入的值為k。

如果當前樹為空，則直接插入根。

如果當前節點的權值等於k則增加當前節點的大小並更新節點和父親的信息，將當前節點進行splay操作。

否則按照二叉查找樹的性質向下找，找到空節點就插入即可，當然在最後還要進行一次splay操作。 ^[3]

刪除(delete)

令要刪除的節點為x，對x進行一次splay操作將其移動到根節點的位置。

若x的大小大於1，則將x的大小減一然後結束刪除操作。

否則將x刪除然後執行join操作合併x的左右子樹並重新指定根。

查找(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 ) {
        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 ) {
        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次伸展操作的均攤時間效率 $T_{\mathrm {amortized} }(m)=O(m\log n)$

實際時間效率 $T_{\mathrm {actual} }(m)=O(m\log n+n\log n)$ ^[4]

參考來源

^ Sleator, Daniel D.; Tarjan, Robert E., Self-Adjusting Binary Search Trees (PDF), Journal of the ACM, 1985, 32 (3): 652–686 [2015-03-05], doi:10.1145/3828.3835, （原始內容存檔 (PDF)於2015-03-05）（英語）
^ Goodrich, Michael; Tamassia, Roberto; Goldwasser, Michael. Data Structures and Algorithms in Java 6. John Wiley & Sons, Inc. 2014: 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.
^ Splay tree - OIwiki. [2019-07-14]. （原始內容存檔於2019-07-14）.
^ Splay tree - Wikipedia. [2018-06-23]. （原始內容存檔於2018-05-05）.

[SleatorTarjan-1] Sleator, Daniel D.; Tarjan, Robert E., Self-Adjusting Binary Search Trees (PDF), Journal of the ACM, 1985, 32 (3): 652–686 [2015-03-05], doi:10.1145/3828.3835, （原始內容存檔 (PDF)於2015-03-05）（英語）

[2] Goodrich, Michael; Tamassia, Roberto; Goldwasser, Michael. Data Structures and Algorithms in Java 6. John Wiley & Sons, Inc. 2014: 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 tree - OIwiki. [2019-07-14]. （原始內容存檔於2019-07-14）.

[4] Splay tree - Wikipedia. [2018-06-23]. （原始內容存檔於2018-05-05）.

[1]

[2]

[3]

[4]