搜索、删除、插入等二叉搜索树（BST）操作的最坏情况时间复杂度为O（n）。最坏的情况发生在树倾斜时。我们可以得到最坏情况下的时间复杂度为O（Logn） AVL 还有红黑的树。 在实际情况下，我们能比AVL或红黑树做得更好吗？ 喜欢 AVL 还有红黑相间的树，八字树也是 自平衡BST 。splay tree的主要思想是将最近访问的项目置于树的根目录下，这样，如果再次访问，则最近搜索的项目可以在O（1）时间内访问。其想法是使用参考位置（在一个典型应用中，80%的访问是对20%的项目的访问）。想象一下这样一种情况：我们拥有数百万或数十亿个密钥，而频繁访问的密钥却很少，这在许多实际应用中都很可能发生。 所有splay树操作平均运行时间为O（logn），其中n是树中的条目数。在最坏的情况下，任何单个操作都可能需要θ（n）时间。 搜索操作 Splay树中的搜索操作执行标准的BST搜索，除了搜索之外，它还显示（将节点移动到根节点）。如果搜索成功，则找到的节点将展开并成为新根。否则，在到达NULL之前访问的最后一个节点将展开，并成为新的根节点。 正在访问的节点有以下情况。 1) 节点是根 我们只返回根，不做任何其他事情，因为被访问的节点已经是根。 2） 齐格： 节点是根的子节点 （节点没有祖父母）。节点要么是根的左子节点（我们进行右旋转），要么是父节点的右子节点（我们进行左旋转）。 T1、T2和T3是以y（左侧）或x（右侧）为根的树的子树
null
y x / Zig (Right Rotation) / x T3 – - – - – - – - - -> T1 y / < - - - - - - - - - / T1 T2 Zag (Left Rotation) T2 T3
3) 节点既有父节点，也有祖父母节点 。可以有以下子类别。 …….. 3.a）之字形和之字形 节点是父节点的左子节点，父节点也是父节点的左子节点（两次右旋转），或者节点是其父节点的右子节点，父节点也是父节点的右子节点（两次左旋转）。
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）曲折和曲折 节点是父节点的右子节点，父节点是父节点的右左节点（左旋转后右旋转），或者节点是父节点的左子节点，父节点是父节点的右子节点（右旋转后左旋转）。
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(G) G P / =============> / ============> / / X T4 T2 P T1 T2 T3 T4 / / T2 T3 T3 T4
例子：
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。 实施：
C++
#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 " ; preOrder(root); return 0; } // This code is contributed by rathbhupendra |
C
// The code is adopted from http://goo.gl/SDH9hH #include<stdio.h> #include<stdlib.h> // An AVL tree node struct node { int key; struct node *left, *right; }; /* Helper function that allocates a new node with the given key and NULL left and right pointers. */ struct node* newNode( int key) { struct node* node = ( struct node*) malloc ( sizeof ( struct 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. struct node *rightRotate( struct node *x) { struct 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. struct node *leftRotate( struct node *x) { struct 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 struct node *splay( struct 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. struct node *search( struct 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( struct node *root) { if (root != NULL) { printf ( "%d " , root->key); preOrder(root->left); preOrder(root->right); } } /* Driver program to test above function*/ int main() { struct 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); printf ( "Preorder traversal of the modified Splay tree is " ); preOrder(root); return 0; } |
JAVA
// Java implementation for above approach class GFG { // An AVL tree node static class node { int key; node left, right; }; /* Helper function that allocates a new node with the given key and null left and right pointers. */ static 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. static 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. static 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 static 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. static 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 static void preOrder(node root) { if (root != null ) { System.out.print(root.key + " " ); preOrder(root.left); preOrder(root.right); } } // Driver code public static void main(String[] args) { 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 ); System.out.print( "Preorder traversal of the" + " modified Splay tree is " ); preOrder(root); } } // This code is contributed by 29AjayKumar |
C#
// C# implementation for above approach using System; class GFG { // An AVL tree node public class node { public int key; public node left, right; }; /* Helper function that allocates a new node with the given key and null left and right pointers. */ static 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. static 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. static 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 static 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. static 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 static void preOrder(node root) { if (root != null ) { Console.Write(root.key + " " ); preOrder(root.left); preOrder(root.right); } } // Driver code public static void Main(String[] args) { 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); Console.Write( "Preorder traversal of the" + " modified Splay tree is " ); preOrder(root); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript implementation for above approach // An AVL tree node class Node { /* Helper function that allocates a new node with the given key and null left and right pointers. */ constructor(key) { this .key = key; this .left = this .right = null ; } } // A utility function to right // rotate subtree rooted with y // See the diagram given above. function rightRotate(x) { let 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. function leftRotate(x) { let 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 function splay(root,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. function search(root,key) { return splay(root, key); } // A utility function to print // preorder traversal of the tree. // The function also prints height of every node function preOrder(root) { if (root != null ) { document.write(root.key + " " ); preOrder(root.left); preOrder(root.right); } } // Driver code let root = new Node(100); root.left = new Node(50); root.right = new Node(200); root.left.left = new Node(40); root.left.left.left = new Node(30); root.left.left.left.left = new Node(20); root = search(root, 20); document.write( "Preorder traversal of the" + " modified Splay tree is <br>" ); preOrder(root); // This code is contributed by rag2127 </script> |
输出：
Preorder traversal of the modified Splay tree is20 50 30 40 100 200
总结 1) 八字树有很好的地方性。经常访问的项目很容易找到。不常出现的物品都已过时。 2) 所有splay tree操作平均需要O（Logn）时间。Splay树可以严格地显示为在任何操作序列（假设我们从一个空树开始）中，每个操作的平均运行时间为O（logn） 3) 与其他树相比，八字树更简单 AVL 红黑树，因为每个树节点都不需要额外的字段。 4) 不像 平衡二叉树 ，即使使用诸如搜索之类的只读操作，splay树也可以更改。 八字树的应用 Splay树已成为过去30年中发明的最广泛使用的基本数据结构，因为它们是许多应用程序中最快的平衡搜索树类型。 在Windows NT（虚拟内存、网络和文件系统代码）、GCC编译器和GNU C++库、SED字符串编辑器、系统网络路由器、UNIX MALLC、Linux可加载内核模块以及其他许多软件中最常用的实现方式中使用了s张开树（源： http://www.cs.berkeley.edu/~jrs/61b/lec/36 ) 看见 八字树|第2组（插入） 用于插入八字树。 参考资料： http://www.cs.berkeley.edu/~jrs/61b/lec/36 http://www.cs.cornell.edu/courses/cs3110/2009fa/recitations/rec-splay.html http://courses.cs.washington.edu/courses/cse326/01au/lectures/SplayTrees.ppt 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
