侯瑞哲的博客

Ruizhe's Blog

0%

Splay Tree

发表于 更新于 Valine：

二叉搜索树最坏的时间复杂度比如查找、删除、插入是O(n)的。最坏的情况发生在这棵树已经倾斜了。我们可以使最坏情况的时间复杂度也为O(logn)使用AVL和红黑树。

我们可以比AVL和红黑树在实践中做得更好吗？

像AVL和红黑树一样，splay tree也是自平衡二叉搜索树。splay tree的主要思想是将最近访问的项目放到树的根节点，这使得最近搜索过的项目可以在O(1)的时间复杂度内被搜索到，如果它再次被搜索。思想是使用访问的局部性（在一个典型的应用中，80%的访问是访问其中20%的项目）。想象一个场景，我们有数百万或数十亿的键但是只有它们中很少一部分会被经常访问，这在实际应用中非常有可能发生。

所有的splay tree操作都平均是O(logn)时间复杂度的，n是树中节点的数量。任何一个操作在最坏的情况下可能使用Theta(n)的时间。

查找操作

splay tree的查找操作使用标准的BST查找，在查找同时，它同时还伸展（splay）（将一个节点移到根）。如果查找是成功的，那么找到的那个节点就被伸展并成为新根节点。否则，在到达NULL之前最后被访问的节点被伸展并成为新的根节点。

被访问的节点有以下几种情况。

  1. 节点是根节点。我们简单地返回根节点，不会做任何事，因为访问的节点已经是根节点。

  2. Zig：节点是root的子节点（该节点没有祖父母）。节点要么是根的左子节点（我们做右旋），要么是根的右子节点（我们做左旋）。

    T1，T2和T3是树的子树，其根为y（在左侧）或x（在右侧）。

1
2
3
4
5
    y                                     x
   / \     Zig (Right Rotation)          /  \
  x   T3   – - – - – - – - - ->         T1   y 
 / \       < - - - - - - - - -              / \
T1  T2     Zag (Left Rotation)            T2   T3

  1. 节点既有父节点，也有祖父节点。可以有以下几种情况。

    3.a. Zig-Zig和Zag-Zag 节点是父节点的左儿子而且父节点同样也是祖父节点的左儿子（两次右旋），或者，节点是父节点的右儿子而且父节点也是祖父节点的右儿子（两次左旋）。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    Zig-Zig (Left Left Case):
           G                        P                           X       
          / \                     /   \                        / \      
         P  T4   rightRotate(G)  X     G     rightRotate(P)  T1   P     
        / \      ============>  / \   / \    ============>       / \    
       X  T3                   T1 T2 T3 T4                      T2  G
      / \                                                          / \ 
     T1 T2                                                        T3  T4 

    Zag-Zag (Right Right Case):
      G                          P                           X       
     /  \                      /   \                        / \      
    T1   P     leftRotate(G)  G     X     leftRotate(P)    P   T4
        / \    ============> / \   / \    ============>   / \   
       T2   X               T1 T2 T3 T4                  G   T3
           / \                                          / \ 
          T3 T4                                        T1  T2

    3.b. Zig-Zag and Zag-Zig 节点是父节点的左儿子，父节点是祖父节点的右儿子（左旋，接着右旋），或者，节点父节点的右儿子，父节点是祖父节点的左儿子（右旋，接着左旋）。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    Zag-Zig (Left Right Case):
           G                        G                            X       
          / \                     /   \                        /   \      
         P   T4  leftRotate(P)   X     T4    rightRotate(G)   P     G     
       /  \      ============>  / \          ============>   / \   /  \    
      T1   X                   P  T3                       T1  T2 T3  T4 
          / \                 / \                                       
        T2  T3              T1   T2                                     

    Zig-Zag (Right Left Case):
      G                          G                           X       
     /  \                      /  \                        /   \      
    T1   P    rightRotate(P)  T1   X     leftRotate(P)    G     P
        / \   =============>      / \    ============>   / \   / \   
       X  T4                    T2   P                 T1  T2 T3  T4
      / \                           / \                
     T2  T3                        T3  T4

例子

1
2
3
4
5
6
7
8
9
         100                      100                       [20]
         /  \                    /   \                        \ 
       50   200                50    200                      50
      /          search(20)    /          search(20)         /  \  
     40          ======>     [20]         ========>         30   100
    /            1. Zig-Zig    \          2. Zig-Zig         \     \
   30               at 40       30            at 100         40    200  
  /                               \     
[20]                              40

需要注意的是，搜索或splay操作不仅将被搜索的键带到了根节点，还平衡了BST。例如在上面的案例中，BST的高度减少了1。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <bits/stdc++.h> 
using namespace std; 

// An AVL tree node 
class node 
{ 
    public: 
 int key; 
    node *left, *right; 
}; 

/* Helper function that allocates 
a new node with the given key and 
  NULL left and right pointers. */
node* newNode(int key) 
{ 
 node* Node = new node(); 
    Node->key = key; 
  Node->left = Node->right = NULL; 
  return (Node); 
} 

// A utility function to right 
// rotate subtree rooted with y 
// See the diagram given above. 
node *rightRotate(node *x) 
{ 
  node *y = x->left; 
    x->left = y->right; 
    y->right = x; 
 return y; 
} 

// A utility function to left 
// rotate subtree rooted with x 
// See the diagram given above. 
node *leftRotate(node *x) 
{ 
 node *y = x->right; 
   x->right = y->left; 
    y->left = x; 
  return y; 
} 

// This function brings the key at 
// root if key is present in tree. 
// If key is not present, then it 
// brings the last accessed item at 
// root. This function modifies the 
// tree and returns the new root 
node *splay(node *root, int key) 
{ 
 // Base cases: root is NULL or 
  // key is present at root 
   if (root == NULL || root->key == key) 
       return root; 

  // Key lies in left subtree 
 if (root->key > key) 
  { 
       // Key is not in tree, we are done 
      if (root->left == NULL) return root; 

     // Zig-Zig (Left Left) 
      if (root->left->key > key) 
     { 
           // First recursively bring the 
          // key as root of left-left 
         root->left->left = splay(root->left->left, key); 

           // Do first rotation for root, 
          // second rotation is done after else 
           root = rightRotate(root); 
        } 
       else if (root->left->key < key) // Zig-Zag (Left Right) 
      { 
           // First recursively bring 
          // the key as root of left-right 
            root->left->right = splay(root->left->right, key); 

         // Do first rotation for root->left 
          if (root->left->right != NULL) 
               root->left = leftRotate(root->left); 
       } 

     // Do second rotation for root 
      return (root->left == NULL)? root: rightRotate(root); 
   } 
   else // Key lies in right subtree 
  { 
       // Key is not in tree, we are done 
      if (root->right == NULL) return root; 

        // Zag-Zig (Right Left) 
     if (root->right->key > key) 
        { 
           // Bring the key as root of right-left 
          root->right->left = splay(root->right->left, key); 

         // Do first rotation for root->right 
         if (root->right->left != NULL) 
               root->right = rightRotate(root->right); 
        } 
       else if (root->right->key < key)// Zag-Zag (Right Right) 
     { 
           // Bring the key as root of 
         // right-right and do first rotation 
            root->right->right = splay(root->right->right, key); 
         root = leftRotate(root); 
     } 

     // Do second rotation for root 
      return (root->right == NULL)? root: leftRotate(root); 
   } 
} 

// The search function for Splay tree. 
// Note that this function returns the 
// new root of Splay Tree. If key is 
// present in tree then, it is moved to root. 
node *search(node *root, int key) 
{ 
  return splay(root, key); 
} 

// A utility function to print 
// preorder traversal of the tree. 
// The function also prints height of every node 
void preOrder(node *root) 
{ 
    if (root != NULL) 
  { 
       cout<<root->key<<" "; 
     preOrder(root->left); 
     preOrder(root->right); 
    } 
} 

/* Driver code*/
int main() 
{ 
   node *root = newNode(100); 
   root->left = newNode(50); 
 root->right = newNode(200); 
   root->left->left = newNode(40); 
    root->left->left->left = newNode(30); 
   root->left->left->left->left = newNode(20); 

    root = search(root, 20); 
 cout << "Preorder traversal of the modified Splay tree is \n"; 
 preOrder(root); 
  return 0; 
} 

// This code is contributed by rathbhupendra

输出

1
2
Preorder traversal of the modified Splay tree is
20 50 30 40 100 200

总结

  1. splay tree有优异的局部性特质。经常访问的元素很容易被找到。不长访问的元素都不在查找的路上。
  2. 所有的splay操作都平均使用O(logn)的时间复杂度。splay tree可以严格的证明，在任何操作的序列上，每次操作的平均时间为O(logn)（假设我们从一颗空树开始）。
  3. splay tree与AVL树和红黑树相比更简单，因为每个树节点都不需要额外的空间。
  4. 与AVL树不同，splay树即使进行搜索操作等只读操作也可能改变。

splay tree 的应用场景

splay tree已经成为了过去30年中发明的应用最广泛的基本数据结构，因为它是许多应用中最快的平衡搜索树类型。splay tree被用于Windows NT（在虚拟内存、网络和文件系统代码中）、gcc编译器和GNU C++库、sed字符串编辑器、Fore Systems网络路由器、Unix malloc最流行的实现、Linux可加载的内核模块和许多其他软件中（来源：http://www.cs.berkeley.edu/~jrs/61b/lec/36）。

参考

https://www.geeksforgeeks.org/splay-tree-set-1-insert/?ref=lbp

下一节我们讲splay的插入操作