建议将以下职位作为本职位的先决条件。 八字树|集1（搜索） 正如在 以前的职位 ，Splay tree是一种自平衡数据结构，最后访问的密钥始终位于根。插入操作类似于二叉搜索树插入，但需要额外的步骤来确保新插入的密钥成为新的根。 以下是在splay树中插入密钥k的不同情况。 1) Root为NULL：我们只需分配一个新节点并将其作为Root返回。 2) 张开 给定的密钥k。如果k已经存在，那么它将成为新的根。如果不存在，则最后访问的叶节点将成为新的根节点。 3) 如果新根的密钥与k相同，则不要执行任何操作，因为k已经存在。 4) 否则，为新节点分配内存，并将root的密钥与k进行比较。 ……. 4.a） 如果k小于root的键，则将root设置为新节点的右子级，将root的左子级复制为新节点的左子级，并将root的左子级设置为NULL。 ……. 4.b） 如果k大于root的键，则将root设置为新节点的左子级，将root的右子级复制为新节点的右子级，并将root的右子级设置为NULL。 5) 将新节点作为树的新根返回。 例子：
null
100 [20] 25 / / 50 200 50 20 50 / insert(25) / insert(25) / 40 ======> 30 100 ========> 30 100 / 1. Splay(25) 2. insert 25 30 40 200 40 200 / [20]
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; // Zig-Zag (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); } } // Function to insert a new key k // in splay tree with given root node *insert(node *root, int k) { // Simple Case: If tree is empty if (root == NULL) return newNode(k); // Bring the closest leaf node to root root = splay(root, k); // If key is already present, then return if (root->key == k) return root; // Otherwise allocate memory for new node node *newnode = newNode(k); // If root's key is greater, make // root as right child of newnode // and copy the left child of root to newnode if (root->key > k) { newnode->right = root; newnode->left = root->left; root->left = NULL; } // If root's key is smaller, make // root as left child of newnode // and copy the right child of root to newnode else { newnode->left = root; newnode->right = root->right; root->right = NULL; } return newnode; // newnode becomes new root } // 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 = insert(root, 25); cout<< "Preorder traversal of the modified Splay tree is " ; preOrder(root); return 0; } // This code is contributed by rathbhupendra |
C
// This code is adopted from http://algs4.cs.princeton.edu/33balanced/SplayBST.java.html #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; // Zig-Zag (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); } } // Function to insert a new key k in splay tree with given root struct node *insert( struct node *root, int k) { // Simple Case: If tree is empty if (root == NULL) return newNode(k); // Bring the closest leaf node to root root = splay(root, k); // If key is already present, then return if (root->key == k) return root; // Otherwise allocate memory for new node struct node *newnode = newNode(k); // If root's key is greater, make root as right child // of newnode and copy the left child of root to newnode if (root->key > k) { newnode->right = root; newnode->left = root->left; root->left = NULL; } // If root's key is smaller, make root as left child // of newnode and copy the right child of root to newnode else { newnode->left = root; newnode->right = root->right; root->right = NULL; } return newnode; // newnode becomes new root } // 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 = insert(root, 25); printf ( "Preorder traversal of the modified Splay tree is " ); preOrder(root); return 0; } |
JAVA
import java.util.*; 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; // Zig-Zag (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); } } // Function to insert a new key k // in splay tree with given root static node insert(node root, int k) { // Simple Case: If tree is empty if (root == null ) return newNode(k); // Bring the closest leaf node to root root = splay(root, k); // If key is already present, then return if (root.key == k) return root; // Otherwise allocate memory for new node node newnode = newNode(k); // If root's key is greater, make // root as right child of newnode // and copy the left child of root to newnode if (root.key > k) { newnode.right = root; newnode.left = root.left; root.left = null ; } // If root's key is smaller, make // root as left child of newnode // and copy the right child of root to newnode else { newnode.left = root; newnode.right = root.right; root.right = null ; } return newnode; // newnode becomes new root } // 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 = insert(root, 25 ); System.out.print( "Preorder traversal of the modified Splay tree is " ); preOrder(root); } } // This code is contributed by Rajput-Ji |
C#
using System; public class node { public int key; public node left, right; } public class GFG{ /* 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; // Zig-Zag (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); } } // Function to insert a new key k // in splay tree with given root static node insert(node root, int k) { // Simple Case: If tree is empty if (root == null ) return newNode(k); // Bring the closest leaf node to root root = splay(root, k); // If key is already present, then return if (root.key == k) return root; // Otherwise allocate memory for new node node newnode = newNode(k); // If root's key is greater, make // root as right child of newnode // and copy the left child of root to newnode if (root.key > k) { newnode.right = root; newnode.left = root.left; root.left = null ; } // If root's key is smaller, make // root as left child of newnode // and copy the right child of root to newnode else { newnode.left = root; newnode.right = root.right; root.right = null ; } return newnode; // newnode becomes new root } // 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*/ static public void 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 = insert(root, 25); Console.Write( "Preorder traversal of the modified Splay tree is " ); preOrder(root); } } // This code is contributed by patel2127. |
Javascript
<script> // An AVL tree node class Node { constructor(val) { this .key = val; this .left = null ; this .right = null ; } } /* Helper function that allocates a new node with the given key and null left and right pointers. */ function newNode(key) { var 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. function rightRotate( x) { var 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) { var 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; // Zig-Zag (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); } } // Function to insert a new key k // in splay tree with given root function insert( root , k) { // Simple Case: If tree is empty if (root == null ) return newNode(k); // Bring the closest leaf node to root root = splay(root, k); // If key is already present, then return if (root.key == k) return root; // Otherwise allocate memory for new node var newnode = newNode(k); // If root's key is greater, make // root as right child of newnode // and copy the left child of root to newnode if (root.key > k) { newnode.right = root; newnode.left = root.left; root.left = null ; } // If root's key is smaller, make // root as left child of newnode // and copy the right child of root to newnode else { newnode.left = root; newnode.right = root.right; root.right = null ; } return newnode; // newnode becomes new root } // 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 */ var 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 = insert(root, 25); document.write( "Preorder traversal of the modified Splay tree is <br/>" ); preOrder(root); // This code contributed by umadevi9616 </script> |
输出：
Preorder traversal of the modified Splay tree is25 20 50 30 40 100 200
本文由 阿比拉蒂 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
