Advertisement

このページを編集する際は,編集に関する方針に従ってください.

概要

引数

実装

135 /* Bottom up splay of key.  */
136 
137 static void
138 splay_tree_splay (splay_tree sp, splay_tree_key key)
139 {

  • ルートがなければ終了

140   if (sp->root == 0)
141     return;
142 
143   do {
144     int cmp1, cmp2;
145     splay_tree_node n, c;
146 

  • ルートのキーと比較

147     n = sp->root;
148     cmp1 = (*sp->comp) (key, n->key);
149 

  • ルートが探していたものなら終了

150     /* Found.  */
151     if (cmp1 == 0)
152       return;
153 

  • ルートとの比較から見に行くのを左にするか右にするか決める

154     /* Left or right?  If no child, then we're done.  */
155     if (cmp1 < 0)
156       c = n->left;
157     else
158       c = n->right;
159     if (!c)
160       return;
161 
162     /* Next one left or right?  If found or no child, we're done
163        after one rotation.  */
164     cmp2 = (*sp->comp) (key, c->key);
165     if (cmp2 == 0
166         || (cmp2 < 0 && !c->left)
167         || (cmp2 > 0 && !c->right))
168       {
169         if (cmp1 < 0)
170           rotate_left (&sp->root, n, c);
171         else
172           rotate_right (&sp->root, n, c);
173         return;
174       }
175 
176     /* Now we have the four cases of double-rotation.  */
177     if (cmp1 < 0 && cmp2 < 0)
178       {
179         rotate_left (&n->left, c, c->left);
180         rotate_left (&sp->root, n, n->left);
181       }
182     else if (cmp1 > 0 && cmp2 > 0)
183       {
184         rotate_right (&n->right, c, c->right);
185         rotate_right (&sp->root, n, n->right);
186       }
187     else if (cmp1 < 0 && cmp2 > 0)
188       {
189         rotate_right (&n->left, c, c->right);
190         rotate_left (&sp->root, n, n->left);
191       }
192     else if (cmp1 > 0 && cmp2 < 0)
193       {
194         rotate_left (&n->right, c, c->left);
195         rotate_right (&sp->root, n, n->right);
196       }
197   } while (1);
198 }



リンク元

特に記載のない限り、コミュニティのコンテンツはCC-BY-SAライセンスの下で利用可能です。