伸展树

Table of content

伸展树的基本操作
插入操作
删除操作
搜索操作

伸展树是二叉搜索树的修改版本，因为它包含了所有 BST 的操作，如插入、删除和搜索，以及另一个扩展操作，称为伸展。

例如，假设要将值“A”插入树中。如果树为空，则将“A”添加到树的根节点并退出；但如果树不为空，则使用二叉搜索插入操作插入元素，然后对新节点执行伸展操作。

类似地，在伸展树中搜索元素后，包含该元素的节点也必须进行伸展。

但是我们如何执行伸展呢？简单来说，伸展就是将操作节点移到根节点的过程。它有六种类型的旋转。

Zig 旋转
Zag 旋转
Zig-Zig 旋转
Zag-Zag 旋转
Zig-Zag 旋转
Zag-Zig 旋转

Zig 旋转

当操作节点是根节点或根节点的左子节点时，执行 Zig 旋转。节点向右旋转。

移位后，树将如下所示：

Zag 旋转

当操作节点是根节点或根节点的右子节点时，也执行 Zag 旋转。节点向左旋转。

移位后，操作节点成为根节点：

Zig-Zig 旋转

当操作节点同时具有父节点和祖父母节点时，执行 Zig-Zig 旋转。节点向右旋转两次。

第一次旋转将树向右移动一个位置：

第二次右旋转将再次将节点移动一个位置。移位后的最终树将如下所示：

Zag-Zag 旋转

当操作节点同时具有父节点和祖父母节点时，也执行 Zag-Zag 旋转。节点向左旋转两次。

第一次旋转后，树将如下所示：

然后，第二次旋转后的最终树如下所示。但是，操作节点仍然不是根节点，因此伸展被认为是不完整的。因此，在这种情况下，再次应用其他合适的旋转，直到节点成为根节点。

Zig-Zag 旋转

Zig-Zag 旋转在操作节点同时具有父节点和祖父母节点时执行。但不同之处在于祖父母节点、父节点和子节点的格式为 LRL。节点先向右旋转，然后向左旋转。

第一次旋转后，树为：

第二次旋转后的最终树：

Zag-Zig 旋转

Zag-Zig 旋转也在操作节点同时具有父节点和祖父母节点时执行。但不同之处在于祖父母节点、父节点和子节点的格式为 RLR。节点先向左旋转，然后向右旋转。

执行第一次旋转，得到如下树：

第二次旋转后，最终树如下所示。但是，操作节点还不是根节点，因此需要再执行一次旋转才能使该节点成为根节点。

伸展树的基本操作

伸展树包含与二叉搜索树提供的相同的基本操作：插入、删除和搜索。但是，在每次操作之后，还有一个额外的操作使它们与二叉搜索树操作不同：伸展。我们已经了解了伸展，所以让我们了解其他操作的过程。

插入操作

伸展树中的插入操作与二叉搜索树中的插入操作执行方式完全相同。伸展树中执行插入操作的过程如下：

检查树是否为空；如果是，则添加新节点并退出

如果树不为空，则使用二叉搜索插入将新节点添加到现有树中。

然后，选择合适的伸展操作并将其应用于新添加的节点。

对新节点应用 Zag（左）旋转

示例

以下是各种编程语言中此操作的实现：

C C++ Java Python

#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: \n");
   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: \n");
   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

#Python Code for Insertion Operation of Splay Trees
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

删除操作

伸展树中的删除操作执行如下：

对要删除的节点应用伸展操作。
一旦节点成为根节点，就删除该节点。
现在，树被分成两棵树，左子树和右子树；它们的第一个节点分别是根节点：例如 root_left 和 root_right。

如果 root_left 为 NULL 值，则 root_right 将成为树的根节点。反之亦然。
但是，如果 root_left 和 root_right 均不为 NULL 值，则从左子树中选择最大值，并将其作为新根节点，连接子树。

示例

以下是各种编程语言中伸展树删除操作的实现：

C C++ Java Python

#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 \n");
   printTree(root);
   root = deletenode(root, 40);
   printf("\nThe Splay tree after deletion is \n");
   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 \n");
   printTree(root);
   root = deletenode(root, 40);
   printf("\nThe Splay tree after deletion is \n");
   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("\nThe 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("\nThe Splay tree after deletion is:")
printTree(root)

输出

The Splay tree is:
15 34 40 
The Splay tree after deletion is:
15 34

搜索操作

伸展树中的搜索操作遵循二叉搜索树操作的相同过程。但是，在搜索完成并找到元素后，将在搜索到的节点上应用伸展操作。如果未找到元素，则会提示搜索失败。

示例

以下是各种编程语言中此操作的实现：

C C++ Java Python

#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 \n");
   printTree(root);
   int ele = 14;
   printf("\nElement to be searched: %d", ele);
   root = search(root, ele);
   printf("\nModified 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 \n";
   printTree(root);
   int ele = 40;
   cout << "\nThe element to be searched: " << ele;
   root = search(root, ele);
   cout << "\nModified 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("\nElement to be searched: " + ele);
      root = search(root, ele);
      System.out.print("\nModified 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("\nElement 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

打印页面