伸展树
伸展树是二叉搜索树的改良版本，因为它包含二叉搜索树的所有操作，例如插入、删除和查找，此外还包含另一个扩展操作，称为伸展。
例如，假设将值"A"插入到树中。如果树为空，则将"A"添加到树的根节点并退出；如果树不为空，则使用二分查找插入操作插入元素，然后对新节点执行展开操作。
同样，在展开树中搜索元素后，也必须展开包含该元素的节点。
但是如何执行展开操作呢？ 简单来说，展开操作就是将一个可操作节点移动到根节点的过程。它有六种旋转类型。
之字形旋转
Zag 旋转
之字形旋转
Zig-Zig 旋转
Zag-Zig 旋转
Zag-Zig 旋转
之字形旋转
当操作节点是根节点或根节点的左子节点时，执行之字形旋转。节点向右旋转。
平移后，树形结构将呈现为 −
Zag 旋转
当操作节点是根节点或根节点的右子节点时，也会执行 Zag 旋转。节点向左旋转。
移动 − 后，操作节点变为根节点。
Zig-Zig 旋转
当操作节点同时具有父节点和祖父节点时，将执行 Zig-Zig 旋转。节点向右旋转两位。
第一次旋转将使树向右移动一位 (−)
第二次向右旋转将再次使节点移动一位。移动后的最终树将如下所示 (−)
Zag-Zag 旋转
当操作节点同时具有父节点和祖父节点时，也会执行 Zag-Zag 旋转。节点向左旋转两位。
第一次旋转后，树形结构如下：
第二次旋转后的最终树形结构如下。然而，操作节点仍然不是根节点，因此展开被认为是不完整的。因此，在这种情况下，需要再次应用其他合适的旋转，直到节点成为根节点。
之字形旋转
当操作节点同时具有父节点和祖父节点时，会执行之字形旋转。但不同之处在于，祖父节点、父节点和子节点均为 LRL 格式。节点首先向右旋转，然后向左旋转。
第一次旋转后，树 −
第二次旋转 − 后的最终树
Zag-Zig 旋转
当操作节点同时具有父节点和祖父节点时，也会执行 Zag-Zig 旋转。但不同之处在于，祖父节点、父节点和子节点均采用 RLR 格式。节点首先向左旋转，然后向右旋转。
第一次旋转后，得到的树为 −
第二次旋转后，最终得到的树如下所示。但是，操作节点还不是根节点，因此需要再进行一次旋转才能使其成为根节点。
伸展树的基本操作
伸展树包含二叉搜索树提供的基本操作：插入、删除和查找。但是，每个操作之后都有一个与二叉搜索树操作不同的附加操作：伸展。我们已经学习了伸展操作，现在让我们了解其他操作的流程。
插入操作
伸展树中的插入操作与二叉搜索树中的插入操作完全相同。在伸展树中执行插入操作的步骤如下 −
检查树是否为空；如果是，则添加新节点并退出。
如果树不为空，则使用二分查找插入将新节点添加到现有树中。
然后，选择合适的展开方式并将其应用于新添加的节点。
对新节点应用左（左）旋转节点
示例
以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *leftChild, *rightChild;
};
struct node* newNode(int data){
struct node* Node = (struct node*)malloc(sizeof(struct node));
Node->data = data;
Node->leftChild = Node->rightChild = NULL;
return (Node);
}
struct node* rightRotate(struct node *x){
struct node *y = x->leftChild;
x->leftChild = y->rightChild;
y->rightChild = x;
return y;
}
struct node* leftRotate(struct node *x){
struct node *y = x->rightChild;
x->rightChild = y->leftChild;
y->leftChild = x;
return y;
}
struct node* splay(struct node *root, int data){
if (root == NULL || root->data == data)
return root;
if (root->data > data) {
if (root->leftChild == NULL) return root;
if (root->leftChild->data > data) {
root->leftChild->leftChild = splay(root->leftChild->leftChild, data);
root = rightRotate(root);
} else if (root->leftChild->data < data) {
root->leftChild->rightChild = splay(root->leftChild->rightChild, data);
if (root->leftChild->rightChild != NULL)
root->leftChild = leftRotate(root->leftChild);
}
return (root->leftChild == NULL)? root: rightRotate(root);
} else {
if (root->rightChild == NULL) return root;
if (root->rightChild->data > data) {
root->rightChild->leftChild = splay(root->rightChild->leftChild, data);
if (root->rightChild->leftChild != NULL)
root->rightChild = rightRotate(root->rightChild);
} else if (root->rightChild->data < data) {
root->rightChild->rightChild = splay(root->rightChild->rightChild, data);
root = leftRotate(root);
}
return (root->rightChild == NULL)? root: leftRotate(root);
}
}
struct node* insert(struct node *root, int k){
if (root == NULL) return newNode(k);
root = splay(root, k);
if (root->data == k) return root;
struct node *newnode = newNode(k);
if (root->data > k) {
newnode->rightChild = root;
newnode->leftChild = root->leftChild;
root->leftChild = NULL;
} else {
newnode->leftChild = root;
newnode->rightChild = root->rightChild;
root->rightChild = NULL;
}
return newnode;
}
void printTree(struct node *root){
if (root == NULL)
return;
if (root != NULL) {
printTree(root->leftChild);
printf("%d ", root->data);
printTree(root->rightChild);
}
}
int main(){
struct node* root = newNode(34);
root->leftChild = newNode(15);
root->rightChild = newNode(40);
root->leftChild->leftChild = newNode(12);
root->leftChild->leftChild->rightChild = newNode(14);
root->rightChild->rightChild = newNode(59);
printf("The Splay tree is:
");
printTree(root);
return 0;
}
输出
The Splay tree is: 12 14 15 34 40 59
#include <iostream>
struct node {
int data;
struct node *leftChild, *rightChild;
};
struct node* newNode(int data){
struct node* Node = (struct node*)malloc(sizeof(struct node));
Node->data = data;
Node->leftChild = Node->rightChild = NULL;
return (Node);
}
struct node* rightRotate(struct node *x){
struct node *y = x->leftChild;
x->leftChild = y->rightChild;
y->rightChild = x;
return y;
}
struct node* leftRotate(struct node *x){
struct node *y = x->rightChild;
x->rightChild = y->leftChild;
y->leftChild = x;
return y;
}
struct node* splay(struct node *root, int data){
if (root == NULL || root->data == data)
return root;
if (root->data > data) {
if (root->leftChild == NULL) return root;
if (root->leftChild->data > data) {
root->leftChild->leftChild = splay(root->leftChild->leftChild, data);
root = rightRotate(root);
} else if (root->leftChild->data < data) {
root->leftChild->rightChild = splay(root->leftChild->rightChild, data);
if (root->leftChild->rightChild != NULL)
root->leftChild = leftRotate(root->leftChild);
}
return (root->leftChild == NULL)? root: rightRotate(root);
} else {
if (root->rightChild == NULL) return root;
if (root->rightChild->data > data) {
root->rightChild->leftChild = splay(root->rightChild->leftChild, data);
if (root->rightChild->leftChild != NULL)
root->rightChild = rightRotate(root->rightChild);
} else if (root->rightChild->data < data) {
root->rightChild->rightChild = splay(root->rightChild->rightChild, data);
root = leftRotate(root);
}
return (root->rightChild == NULL)? root: leftRotate(root);
}
}
struct node* insert(struct node *root, int k){
if (root == NULL) return newNode(k);
root = splay(root, k);
if (root->data == k) return root;
struct node *newnode = newNode(k);
if (root->data > k) {
newnode->rightChild = root;
newnode->leftChild = root->leftChild;
root->leftChild = NULL;
} else {
newnode->leftChild = root;
newnode->rightChild = root->rightChild;
root->rightChild = NULL;
}
return newnode;
}
void printTree(struct node *root){
if (root == NULL)
return;
if (root != NULL) {
printTree(root->leftChild);
printf("%d ", root->data);
printTree(root->rightChild);
}
}
int main(){
struct node* root = newNode(34);
root->leftChild = newNode(15);
root->rightChild = newNode(40);
root->leftChild->leftChild = newNode(12);
root->leftChild->leftChild->rightChild = newNode(14);
root->rightChild->rightChild = newNode(59);
printf("The Splay tree is:
");
printTree(root);
return 0;
}
输出
The Splay tree is: 12 14 15 34 40 59
import java.io.*;
public class SplayTree {
static class node {
int data;
node leftChild, rightChild;
};
static node newNode(int data) {
node Node = new node();
Node.data = data;
Node.leftChild = Node.rightChild = null;
return (Node);
}
static node rightRotate(node x) {
node y = x.leftChild;
x.leftChild = y.rightChild;
y.rightChild = x;
return y;
}
static node leftRotate(node x) {
node y = x.rightChild;
x.rightChild = y.leftChild;
y.leftChild = x;
return y;
}
static node splay(node root, int data) {
if (root == null || root.data == data)
return root;
if (root.data > data) {
if (root.leftChild == null) return root;
if (root.leftChild.data > data) {
root.leftChild.leftChild = splay(root.leftChild.leftChild, data);
root = rightRotate(root);
} else if (root.leftChild.data < data) {
root.leftChild.rightChild = splay(root.leftChild.rightChild, data);
if (root.leftChild.rightChild != null)
root.leftChild = leftRotate(root.leftChild);
}
return (root.leftChild == null)? root: rightRotate(root);
} else {
if (root.rightChild == null) return root;
if (root.rightChild.data > data) {
root.rightChild.leftChild = splay(root.rightChild.leftChild, data);
if (root.rightChild.leftChild != null)
root.rightChild = rightRotate(root.rightChild);
} else if (root.rightChild.data < data) {
root.rightChild.rightChild = splay(root.rightChild.rightChild, data);
root = leftRotate(root);
}
return (root.rightChild == null)? root: leftRotate(root);
}
}
static node insert(node root, int k) {
if (root == null) return newNode(k);
root = splay(root, k);
if (root.data == k) return root;
node newnode = newNode(k);
if (root.data > k) {
newnode.rightChild = root;
newnode.leftChild = root.leftChild;
root.leftChild = null;
} else {
newnode.leftChild = root;
newnode.rightChild = root.rightChild;
root.rightChild = null;
}
return newnode;
}
static void printTree(node root) {
if (root == null)
return;
if (root != null) {
printTree(root.leftChild);
System.out.print(root.data + " ");
printTree(root.rightChild);
}
}
public static void main(String args[]) {
node root = newNode(34);
root.leftChild = newNode(15);
root.rightChild = newNode(40);
root.leftChild.leftChild = newNode(12);
root.leftChild.leftChild.rightChild = newNode(14);
root.rightChild.rightChild = newNode(59);
System.out.println("The Splay tree is: ");
printTree(root);
}
}
输出
The Splay tree is: 12 14 15 34 40 59
#Splay 树插入操作的 Python 代码
class Node:
def __init__(self, data):
self.data = data
self.leftChild = None
self.rightChild = None
def newNode(data):
return Node(data)
def rightRotate(x):
y = x.leftChild
x.leftChild = y.rightChild
y.rightChild = x
return y
def leftRotate(x):
y = x.rightChild
x.rightChild = y.leftChild
y.leftChild = x
return y
def splay(root, data):
if root is None or root.data == data:
return root
if root.data > data:
if root.leftChild is None:
return root
if root.leftChild.data > data:
root.leftChild.leftChild = splay(root.leftChild.leftChild, data)
root = rightRotate(root)
elif root.leftChild.data < data:
root.leftChild.rightChild = splay(root.leftChild.rightChild, data)
if root.leftChild.rightChild is not None:
root.leftChild = leftRotate(root.leftChild)
return root if root.leftChild is None else rightRotate(root)
else:
if root.rightChild is None:
return root
if root.rightChild.data > data:
root.rightChild.leftChild = splay(root.rightChild.leftChild, data)
if root.rightChild.leftChild is not None:
root.rightChild = rightRotate(root.rightChild)
elif root.rightChild.data < data:
root.rightChild.rightChild = splay(root.rightChild.rightChild, data)
root = leftRotate(root)
return root if root.rightChild is None else leftRotate(root)
def insert(root, k):
if root is None:
return newNode(k)
root = splay(root, k)
if root.data == k:
return root
newnode = newNode(k)
if root.data > k:
newnode.rightChild = root
newnode.leftChild = root.leftChild
root.leftChild = None
else:
newnode.leftChild = root
newnode.rightChild = root.rightChild
root.rightChild = None
return newnode
def printTree(root):
if root is None:
return
if root is not None:
printTree(root.leftChild)
print(root.data, end=" ")
printTree(root.rightChild)
if __name__ == "__main__":
root = newNode(34)
root.leftChild = newNode(15)
root.rightChild = newNode(40)
root.leftChild.leftChild = newNode(12)
root.leftChild.leftChild.rightChild = newNode(14)
root.rightChild.rightChild = newNode(59)
print("The Splay tree is: ")
printTree(root)
输出
The Splay tree is: 12 14 15 34 40 59
删除操作
Splay 树中的删除操作如下 −
对要删除的节点应用 Splaying 操作。
一旦该节点成为根节点，就删除该节点。
现在，树被分成两棵树，左子树和右子树；它们各自的第一个节点作为根节点：假设 root_left 和 root_right。
如果 root_left 为 NULL 值，则 root_right 将成为树的根节点。反之亦然。
但如果 root_left 和 root_right 都不为 NULL，则从左子树中选择最大值，并通过连接子树使其成为新的根。
示例
以下是各种编程语言中 Splay Tree 删除操作的实现 −
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *leftChild, *rightChild;
};
struct node* newNode(int data){
struct node* Node = (struct node*)malloc(sizeof(struct node));
Node->data = data;
Node->leftChild = Node->rightChild = NULL;
return (Node);
}
struct node* rightRotate(struct node *x){
struct node *y = x->leftChild;
x->leftChild = y->rightChild;
y->rightChild = x;
return y;
}
struct node* leftRotate(struct node *x){
struct node *y = x->rightChild;
x->rightChild = y->leftChild;
y->leftChild = x;
return y;
}
struct node* splay(struct node *root, int data){
if (root == NULL || root->data == data)
return root;
if (root->data > data) {
if (root->leftChild == NULL) return root;
if (root->leftChild->data > data) {
root->leftChild->leftChild = splay(root->leftChild->leftChild, data);
root = rightRotate(root);
} else if (root->leftChild->data < data) {
root->leftChild->rightChild = splay(root->leftChild->rightChild, data);
if (root->leftChild->rightChild != NULL)
root->leftChild = leftRotate(root->leftChild);
}
return (root->leftChild == NULL)? root: rightRotate(root);
} else {
if (root->rightChild == NULL) return root;
if (root->rightChild->data > data) {
root->rightChild->leftChild = splay(root->rightChild->leftChild, data);
if (root->rightChild->leftChild != NULL)
root->rightChild = rightRotate(root->rightChild);
} else if (root->rightChild->data < data) {
root->rightChild->rightChild = splay(root->rightChild->rightChild, data);
root = leftRotate(root);
}
return (root->rightChild == NULL)? root: leftRotate(root);
}
}
struct node* insert(struct node *root, int k){
if (root == NULL) return newNode(k);
root = splay(root, k);
if (root->data == k) return root;
struct node *newnode = newNode(k);
if (root->data > k) {
newnode->rightChild = root;
newnode->leftChild = root->leftChild;
root->leftChild = NULL;
} else {
newnode->leftChild = root;
newnode->rightChild = root->rightChild;
root->rightChild = NULL;
}
return newnode;
}
struct node* deletenode(struct node* root, int data){
struct node* temp;
if (root == NULL)
return NULL;
root = splay(root, data);
if (data != root->data)
return root;
if (!root->leftChild) {
temp = root;
root = root->rightChild;
} else {
temp = root;
root = splay(root->leftChild, data);
root->rightChild = temp->rightChild;
}
free(temp);
return root;
}
void printTree(struct node *root){
if (root == NULL)
return;
if (root != NULL) {
printTree(root->leftChild);
printf("%d ", root->data);
printTree(root->rightChild);
}
}
int main(){
struct node* root = newNode(34);
root->leftChild = newNode(15);
root->rightChild = newNode(40);
printf("The Splay tree is
");
printTree(root);
root = deletenode(root, 40);
printf("
The Splay tree after deletion is
");
printTree(root);
return 0;
}
输出
The Splay tree is 15 34 40 The Splay tree after deletion is 15 34
#include <iostream>
struct node {
int data;
struct node *leftChild, *rightChild;
};
struct node* newNode(int data){
struct node* Node = (struct node*)malloc(sizeof(struct node));
Node->data = data;
Node->leftChild = Node->rightChild = NULL;
return (Node);
}
struct node* rightRotate(struct node *x){
struct node *y = x->leftChild;
x->leftChild = y->rightChild;
y->rightChild = x;
return y;
}
struct node* leftRotate(struct node *x){
struct node *y = x->rightChild;
x->rightChild = y->leftChild;
y->leftChild = x;
return y;
}
struct node* splay(struct node *root, int data){
if (root == NULL || root->data == data)
return root;
if (root->data > data) {
if (root->leftChild == NULL) return root;
if (root->leftChild->data > data) {
root->leftChild->leftChild = splay(root->leftChild->leftChild, data);
root = rightRotate(root);
} else if (root->leftChild->data < data) {
root->leftChild->rightChild = splay(root->leftChild->rightChild, data);
if (root->leftChild->rightChild != NULL)
root->leftChild = leftRotate(root->leftChild);
}
return (root->leftChild == NULL)? root: rightRotate(root);
} else {
if (root->rightChild == NULL) return root;
if (root->rightChild->data > data) {
root->rightChild->leftChild = splay(root->rightChild->leftChild, data);
if (root->rightChild->leftChild != NULL)
root->rightChild = rightRotate(root->rightChild);
} else if (root->rightChild->data < data) {
root->rightChild->rightChild = splay(root->rightChild->rightChild, data);
root = leftRotate(root);
}
return (root->rightChild == NULL)? root: leftRotate(root);
}
}
struct node* insert(struct node *root, int k){
if (root == NULL) return newNode(k);
root = splay(root, k);
if (root->data == k) return root;
struct node *newnode = newNode(k);
if (root->data > k) {
newnode->rightChild = root;
newnode->leftChild = root->leftChild;
root->leftChild = NULL;
} else {
newnode->leftChild = root;
newnode->rightChild = root->rightChild;
root->rightChild = NULL;
}
return newnode;
}
struct node* deletenode(struct node* root, int data){
struct node* temp;
if (root == NULL)
return NULL;
root = splay(root, data);
if (data != root->data)
return root;
if (!root->leftChild) {
temp = root;
root = root->rightChild;
} else {
temp = root;
root = splay(root->leftChild, data);
root->rightChild = temp->rightChild;
}
free(temp);
return root;
}
void printTree(struct node *root){
if (root == NULL)
return;
if (root != NULL) {
printTree(root->leftChild);
printf("%d ", root->data);
printTree(root->rightChild);
}
}
int main(){
struct node* root = newNode(34);
root->leftChild = newNode(15);
root->rightChild = newNode(40);
printf("The Splay tree is
");
printTree(root);
root = deletenode(root, 40);
printf("
The Splay tree after deletion is
");
printTree(root);
return 0;
}
输出
The Splay tree is 15 34 40 The Splay tree after deletion is 15 34
import java.io.*;
public class SplayTree {
static class node {
int data;
node leftChild, rightChild;
};
static node newNode(int data) {
node Node = new node();
Node.data = data;
Node.leftChild = Node.rightChild = null;
return (Node);
}
static node rightRotate(node x) {
node y = x.leftChild;
x.leftChild = y.rightChild;
y.rightChild = x;
return y;
}
static node leftRotate(node x) {
node y = x.rightChild;
x.rightChild = y.leftChild;
y.leftChild = x;
return y;
}
static node splay(node root, int data) {
if (root == null || root.data == data)
return root;
if (root.data > data) {
if (root.leftChild == null) return root;
if (root.leftChild.data > data) {
root.leftChild.leftChild = splay(root.leftChild.leftChild, data);
root = rightRotate(root);
} else if (root.leftChild.data < data) {
root.leftChild.rightChild = splay(root.leftChild.rightChild, data);
if (root.leftChild.rightChild != null)
root.leftChild = leftRotate(root.leftChild);
}
return (root.leftChild == null)? root: rightRotate(root);
} else {
if (root.rightChild == null) return root;
if (root.rightChild.data > data) {
root.rightChild.leftChild = splay(root.rightChild.leftChild, data);
if (root.rightChild.leftChild != null)
root.rightChild = rightRotate(root.rightChild);
} else if (root.rightChild.data < data) {
root.rightChild.rightChild = splay(root.rightChild.rightChild, data);
root = leftRotate(root);
}
return (root.rightChild == null)? root: leftRotate(root);
}
}
static node insert(node root, int k) {
if (root == null) return newNode(k);
root = splay(root, k);
if (root.data == k) return root;
node newnode = newNode(k);
if (root.data > k) {
newnode.rightChild = root;
newnode.leftChild = root.leftChild;
root.leftChild = null;
} else {
newnode.leftChild = root;
newnode.rightChild = root.rightChild;
root.rightChild = null;
}
return newnode;
}
static node deletenode(node root, int data) {
node temp;
if (root == null)
return null;
root = splay(root, data);
if (data != root.data)
return root;
if (root.leftChild == null) {
temp = root;
root = root.rightChild;
} else {
temp = root;
root = splay(root.leftChild, data);
root.rightChild = temp.rightChild;
}
return root;
}
static void printTree(node root) {
if (root == null)
return;
if (root != null) {
printTree(root.leftChild);
System.out.print(root.data + " ");
printTree(root.rightChild);
}
}
public static void main(String args[]) {
node root = newNode(34);
root.leftChild = newNode(15);
root.rightChild = newNode(40);
System.out.println("The Splay tree is: ");
printTree(root);
root = deletenode(root, 40);
System.out.println("
The Splay tree after deletion is: ");
printTree(root);
}
}
输出
The Splay tree is: 15 34 40 The Splay tree after deletion is: 15 34
#Python Code for Deletion operation of Splay Trees
class Node:
def __init__(self, data):
self.data = data
self.leftChild = None
self.rightChild = None
def newNode(data):
node = Node(data)
return node
def rightRotate(x):
y = x.leftChild
x.leftChild = y.rightChild
y.rightChild = x
return y
def leftRotate(x):
y = x.rightChild
x.rightChild = y.leftChild
y.leftChild = x
return y
def splay(root, data):
if root is None or root.data == data:
return root
if root.data > data:
if root.leftChild is None:
return root
if root.leftChild.data > data:
root.leftChild.leftChild = splay(root.leftChild.leftChild, data)
root = rightRotate(root)
elif root.leftChild.data < data:
root.leftChild.rightChild = splay(root.leftChild.rightChild, data)
if root.leftChild.rightChild is not None:
root.leftChild = leftRotate(root.leftChild)
return root if root.leftChild is None else rightRotate(root)
else:
if root.rightChild is None:
return root
if root.rightChild.data > data:
root.rightChild.leftChild = splay(root.rightChild.leftChild, data)
if root.rightChild.leftChild is not None:
root.rightChild = rightRotate(root.rightChild)
elif root.rightChild.data < data:
root.rightChild.rightChild = splay(root.rightChild.rightChild, data)
root = leftRotate(root)
return root if root.rightChild is None else leftRotate(root)
def insert(root, k):
if root is None:
return newNode(k)
root = splay(root, k)
if root.data == k:
return root
newnode = newNode(k)
if root.data > k:
newnode.rightChild = root
newnode.leftChild = root.leftChild
root.leftChild = None
else:
newnode.leftChild = root
newnode.rightChild = root.rightChild
root.rightChild = None
return newnode
def deletenode(root, data):
temp = None
if root is None:
return None
root = splay(root, data)
if data != root.data:
return root
if root.leftChild is None:
temp = root
root = root.rightChild
else:
temp = root
root = splay(root.leftChild, data)
root.rightChild = temp.rightChild
del temp
return root
def printTree(root):
if root is None:
return
if root is not None:
printTree(root.leftChild)
print(root.data, end=" ")
printTree(root.rightChild)
root = newNode(34)
root.leftChild = newNode(15)
root.rightChild = newNode(40)
print("The Splay tree is:")
printTree(root)
root = deletenode(root, 40)
print("
The Splay tree after deletion is:")
printTree(root)
输出
The Splay tree is: 15 34 40 The Splay tree after deletion is: 15 34
搜索操作
Splay 树中的搜索操作与二叉搜索树的操作流程相同。但是，搜索完成后，如果找到元素，则会对搜索到的节点进行 Splaying。如果未找到元素，则提示搜索失败。
示例
以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *leftChild, *rightChild;
};
struct node* newNode(int data){
struct node* Node = (struct node*)malloc(sizeof(struct node));
Node->data = data;
Node->leftChild = Node->rightChild = NULL;
return (Node);
}
struct node* rightRotate(struct node *x){
struct node *y = x->leftChild;
x->leftChild = y->rightChild;
y->rightChild = x;
return y;
}
struct node* leftRotate(struct node *x){
struct node *y = x->rightChild;
x->rightChild = y->leftChild;
y->leftChild = x;
return y;
}
struct node* splay(struct node *root, int data){
if (root == NULL || root->data == data)
return root;
if (root->data > data) {
if (root->leftChild == NULL) return root;
if (root->leftChild->data > data) {
root->leftChild->leftChild = splay(root->leftChild->leftChild, data);
root = rightRotate(root);
} else if (root->leftChild->data < data) {
root->leftChild->rightChild = splay(root->leftChild->rightChild, data);
if (root->leftChild->rightChild != NULL)
root->leftChild = leftRotate(root->leftChild);
}
return (root->leftChild == NULL)? root: rightRotate(root);
} else {
if (root->rightChild == NULL) return root;
if (root->rightChild->data > data) {
root->rightChild->leftChild = splay(root->rightChild->leftChild, data);
if (root->rightChild->leftChild != NULL)
root->rightChild = rightRotate(root->rightChild);
} else if (root->rightChild->data < data) {
root->rightChild->rightChild = splay(root->rightChild->rightChild, data);
root = leftRotate(root);
}
return (root->rightChild == NULL)? root: leftRotate(root);
}
}
struct node* insert(struct node *root, int k){
if (root == NULL) return newNode(k);
root = splay(root, k);
if (root->data == k) return root;
struct node *newnode = newNode(k);
if (root->data > k) {
newnode->rightChild = root;
newnode->leftChild = root->leftChild;
root->leftChild = NULL;
} else {
newnode->leftChild = root;
newnode->rightChild = root->rightChild;
root->rightChild = NULL;
}
return newnode;
}
struct node* search(struct node* root, int data){
return splay(root, data);
}
void printTree(struct node *root){
if (root == NULL)
return;
if (root != NULL) {
printTree(root->leftChild);
printf("%d ", root->data);
printTree(root->rightChild);
}
}
void preOrder(struct node *root)
{
if (root != NULL)
{
printf("%d ", root->data);
preOrder(root->leftChild);
preOrder(root->rightChild);
}
}
int main(){
struct node* root = newNode(34);
root->leftChild = newNode(15);
root->rightChild = newNode(40);
root->leftChild->leftChild = newNode(12);
root->leftChild->leftChild->rightChild = newNode(14);
root->rightChild->rightChild = newNode(59);
printf("The Splay tree is
");
printTree(root);
int ele = 14;
printf("
Element to be searched: %d", ele);
root = search(root, ele);
printf("
Modified preorder traversal if element is found: ");
preOrder(root);
}
输出
The Splay tree is 12 14 15 34 40 59 Element to be searched: 14 Modified preorder traversal if element is found: 14 12 15 34 40 59
#include <bits/stdc++.h>
using namespace std;
class node{
public:
int data;
node *leftChild, *rightChild;
};
node* newNode(int data){
node* Node = new node();
Node->data = data;
Node->leftChild = Node->rightChild = NULL;
return (Node);
}
node *rightRotate(node *x){
node *y = x->leftChild;
x->leftChild = y->rightChild;
y->rightChild = x;
return y;
}
node *leftRotate(node *x){
node *y = x->rightChild;
x->rightChild = y->leftChild;
y->leftChild = x;
return y;
}
node *splay(node *root, int data){
if (root == NULL || root->data == data)
return root;
if (root->data > data) {
if (root->leftChild == NULL) return root;
if (root->leftChild->data > data) {
root->leftChild->leftChild = splay(root->leftChild->leftChild, data);
root = rightRotate(root);
} else if (root->leftChild->data < data) {
root->leftChild->rightChild = splay(root->leftChild->rightChild, data);
if (root->leftChild->rightChild != NULL)
root->leftChild = leftRotate(root->leftChild);
}
return (root->leftChild == NULL)? root: rightRotate(root);
} else {
if (root->rightChild == NULL) return root;
if (root->rightChild->data > data) {
root->rightChild->leftChild = splay(root->rightChild->leftChild, data);
if (root->rightChild->leftChild != NULL)
root->rightChild = rightRotate(root->rightChild);
} else if (root->rightChild->data < data) {
root->rightChild->rightChild = splay(root->rightChild->rightChild, data);
root = leftRotate(root);
}
return (root->rightChild == NULL)? root: leftRotate(root);
}
}
node* insert(node *root, int k)
{
if (root == NULL) return newNode(k);
root = splay(root, k);
if (root->data == k) return root;
node *newnode = newNode(k);
if (root->data > k) {
newnode->rightChild = root;
newnode->leftChild = root->leftChild;
root->leftChild = NULL;
} else {
newnode->leftChild = root;
newnode->rightChild = root->rightChild;
root->rightChild = NULL;
}
return newnode;
}
node* search(struct node* root, int data){
return splay(root, data);
}
void printTree(node *root){
if (root == NULL)
return;
if (root != NULL) {
printTree(root->leftChild);
cout << root->data << " ";
printTree(root->rightChild);
}
}
void preOrder(struct node *root)
{
if (root != NULL)
{
cout << root->data << " ";
preOrder(root->leftChild);
preOrder(root->rightChild);
}
}
int main(){
node* root = newNode(34);
root->leftChild = newNode(15);
root->rightChild = newNode(40);
root->leftChild->leftChild = newNode(12);
root->leftChild->leftChild->rightChild = newNode(14);
root->rightChild->rightChild = newNode(59);
cout << "The Splay tree is
";
printTree(root);
int ele = 40;
cout << "
The element to be searched: " << ele;
root = search(root, ele);
cout << "
Modified preorder traversal if element is found: ";
preOrder(root);
}
输出
The Splay tree is 12 14 15 34 40 59 The element to be searched: 40 Modified preorder traversal if element is found: 40 34 15 12 14 59
import java.io.*;
public class SplayTree {
static class node {
int data;
node leftChild, rightChild;
};
static node newNode(int data) {
node Node = new node();
Node.data = data;
Node.leftChild = Node.rightChild = null;
return (Node);
}
static node rightRotate(node x) {
node y = x.leftChild;
x.leftChild = y.rightChild;
y.rightChild = x;
return y;
}
static node leftRotate(node x) {
node y = x.rightChild;
x.rightChild = y.leftChild;
y.leftChild = x;
return y;
}
static node splay(node root, int data) {
if (root == null || root.data == data)
return root;
if (root.data > data) {
if (root.leftChild == null) return root;
if (root.leftChild.data > data) {
root.leftChild.leftChild = splay(root.leftChild.leftChild, data);
root = rightRotate(root);
} else if (root.leftChild.data < data) {
root.leftChild.rightChild = splay(root.leftChild.rightChild, data);
if (root.leftChild.rightChild != null)
root.leftChild = leftRotate(root.leftChild);
}
return (root.leftChild == null)? root: rightRotate(root);
} else {
if (root.rightChild == null) return root;
if (root.rightChild.data > data) {
root.rightChild.leftChild = splay(root.rightChild.leftChild, data);
if (root.rightChild.leftChild != null)
root.rightChild = rightRotate(root.rightChild);
} else if (root.rightChild.data < data) {
root.rightChild.rightChild = splay(root.rightChild.rightChild, data);
root = leftRotate(root);
}
return (root.rightChild == null)? root: leftRotate(root);
}
}
static node insert(node root, int k) {
if (root == null) return newNode(k);
root = splay(root, k);
if (root.data == k) return root;
node newnode = newNode(k);
if (root.data > k) {
newnode.rightChild = root;
newnode.leftChild = root.leftChild;
root.leftChild = null;
} else {
newnode.leftChild = root;
newnode.rightChild = root.rightChild;
root.rightChild = null;
}
return newnode;
}
static node search(node root, int key){
return splay(root, key);
}
static void printTree(node root) {
if (root == null)
return;
if (root != null) {
printTree(root.leftChild);
System.out.print(root.data + " ");
printTree(root.rightChild);
}
}
static void preOrder(node root) {
if (root != null) {
System.out.print(root.data + " ");
preOrder(root.leftChild);
preOrder(root.rightChild);
}
}
public static void main(String args[]) {
node root = newNode(34);
root.leftChild = newNode(15);
root.rightChild = newNode(40);
root.leftChild.leftChild = newNode(12);
root.leftChild.leftChild.rightChild = newNode(14);
root.rightChild.rightChild = newNode(59);
System.out.println("The Splay tree is: ");
printTree(root);
int ele = 34;
System.out.print("
Element to be searched: " + ele);
root = search(root, ele);
System.out.print("
Modified preorder traversal if element is found: ");
preOrder(root);
}
}
输出
The Splay tree is: 12 14 15 34 40 59 Element to be searched: 34 Modified preorder traversal if element is found: 34 15 12 14 40 59
#Python Code for Search Operation of splay Trees
class Node:
def __init__(self, data):
self.data = data
self.leftChild = None
self.rightChild = None
def newNode(data):
newNode = Node(data)
newNode.leftChild = newNode.rightChild = None
return newNode
def rightRotate(x):
y = x.leftChild
x.leftChild = y.rightChild
y.rightChild = x
return y
def leftRotate(x):
y = x.rightChild
x.rightChild = y.leftChild
y.leftChild = x
return y
def splay(root, data):
if root is None or root.data == data:
return root
if root.data > data:
if root.leftChild is None:
return root
if root.leftChild.data > data:
root.leftChild.leftChild = splay(root.leftChild.leftChild, data)
root = rightRotate(root)
elif root.leftChild.data < data:
root.leftChild.rightChild = splay(root.leftChild.rightChild, data)
if root.leftChild.rightChild is not None:
root.leftChild = leftRotate(root.leftChild)
return root if root.leftChild is None else rightRotate(root)
else:
if root.rightChild is None:
return root
if root.rightChild.data > data:
root.rightChild.leftChild = splay(root.rightChild.leftChild, data)
if root.rightChild.leftChild is not None:
root.rightChild = rightRotate(root.rightChild)
elif root.rightChild.data < data:
root.rightChild.rightChild = splay(root.rightChild.rightChild, data)
root = leftRotate(root)
return root if root.rightChild is None else leftRotate(root)
def insert(root, k):
if root is None:
return newNode(k)
root = splay(root, k)
if root.data == k:
return root
newnode = newNode(k)
if root.data > k:
newnode.rightChild = root
newnode.leftChild = root.leftChild
root.leftChild = None
else:
newnode.leftChild = root
newnode.rightChild = root.rightChild
root.rightChild = None
return newnode
def search(root, data):
return splay(root, data)
def printTree(root):
if root is None:
return
if root is not None:
printTree(root.leftChild)
print(root.data, end=" ")
printTree(root.rightChild)
def preOrder(root):
if root != None:
print(root.data, end = " ")
preOrder(root.leftChild)
preOrder(root.rightChild)
root = newNode(34)
root.leftChild = newNode(15)
root.rightChild = newNode(40)
root.leftChild.leftChild = newNode(12)
root.leftChild.leftChild.rightChild = newNode(14)
root.rightChild.rightChild = newNode(59)
print("The Splay tree is")
printTree(root)
ele = 59
print("
Element to be searched ",ele)
root = search(root, ele)
print("Modified preorder traversal if element is found: ")
preOrder(root)
输出
The Splay tree is 12 14 15 34 40 59 Element to be searched 59 Modified preorder traversal if element is found: 59 40 34 15 12 14
