伸展樹

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

列印頁面