Рубрики

Splay Tree | Комплект 1 (Поиск)

Наихудшая временная сложность операций дерева двоичного поиска (BST), таких как поиск, удаление, вставка, составляет O (n). Худший случай возникает, когда дерево перекошено. Мы можем получить наихудшую временную сложность как O (Logn) с AVL и красно-черными деревьями.

Можем ли мы добиться большего успеха, чем AVL или красно-черные деревья в практических ситуациях?
Как и AVL и красно-черные деревья, Splay Tree также является самобалансирующимся BST . Основная идея Splay Tree состоит в том, чтобы перенести недавно доступный элемент в корень дерева, что делает недавно найденный элемент доступным за O (1) раз при повторном доступе. Идея состоит в том, чтобы использовать локальность ссылок (в типичном приложении 80% доступа составляют 20% элементов). Представьте себе ситуацию, когда у нас есть миллионы или миллиарды ключей, и к ним часто обращаются лишь немногие, что весьма вероятно во многих практических приложениях.

Все операции с Splay Tree выполняются в среднем за O (log n), где n — количество записей в дереве. В худшем случае любая отдельная операция может занять время Theta (n).

Операция поиска
Операция поиска в дереве Splay выполняет стандартный поиск BST, в дополнение к поиску, она также выполняет отображение (перемещение узла в корень). Если поиск успешен, то найденный узел отображается и становится новым корнем. Иначе, последний узел, к которому был получен доступ до достижения значения NULL, отображается и становится новым корнем.

Существуют следующие случаи доступа к узлу.

1) Node is root. Мы просто возвращаем root, больше ничего не делаем, так как доступный узел уже root.

2) Zig: узел является дочерним по отношению к корню (узел не имеет прародителя). Узел является либо левым потомком root (мы делаем правое вращение), либо узел является правым потомком своего родителя (мы делаем левый поворот).
T1, T2 и T3 являются поддеревьями дерева с корнем y (слева) или x (справа)

                y                                     x
               / \     Zig (Right Rotation)          /  \
              x   T3   – - – - – - – - - ->         T1   y 
             / \       < - - - - - - - - -              / \
            T1  T2     Zag (Left Rotation)            T2   T3

3) У узла есть и родитель, и дедушка . Могут быть следующие случаи.
…… .. 3.a) Узел Zig-Zig и Zag-Zag является левым потомком родителя, а родитель также остается дочерним элементом родителя (два правых поворота), ИЛИ узел является правым дочерним элементом своего родителя, а родитель также является правым дочерним элементом прародитель (два левых поворота).

Zig-Zig (Left Left Case):
       G                        P                           X       
      / \                     /   \                        / \      
     P  T4   rightRotate(G)  X     G     rightRotate(P)  T1   P     
    / \      ============>  / \   / \    ============>       / \    
   X  T3                   T1 T2 T3 T4                      T2  G
  / \                                                          / \ 
 T1 T2                                                        T3  T4 

Zag-Zag (Right Right Case):
  G                          P                           X       
 /  \                      /   \                        / \      
T1   P     leftRotate(G)  G     X     leftRotate(P)    P   T4
    / \    ============> / \   / \    ============>   / \   
   T2   X               T1 T2 T3 T4                  G   T3
       / \                                          / \ 
      T3 T4                                        T1  T2

…… .. 3.b) Zig-Zag и Zag-Zig Node — левый дочерний элемент родителя, а родительский — правый дочерний элемент родительского элемента (Поворот влево, затем правое вращение) ИЛИ узел является правым дочерним элементом своего родителя, а родительский дочерний элемент — левый. прародителя (правое вращение с последующим левым вращением).

Zag-Zig (Left Right Case):
       G                        G                            X       
      / \                     /   \                        /   \      
     P   T4  leftRotate(P)   X     T4    rightRotate(G)   P     G     
   /  \      ============>  / \          ============>   / \   /  \    
  T1   X                   P  T3                       T1  T2 T3  T4 
      / \                 / \                                       
    T2  T3              T1   T2                                     

Zig-Zag (Right Left Case):
  G                          G                           X       
 /  \                      /  \                        /   \      
T1   P    rightRotate(P)  T1   X     leftRotate(P)    G     P
    / \   =============>      / \    ============>   / \   / \   
   X  T4                    T2   P                 T1  T2 T3  T4
  / \                           / \                
 T2  T3                        T3  T4  

Пример:

 
         100                      100                       [20]
         /  \                    /   \                        \ 
       50   200                50    200                      50
      /          search(20)    /          search(20)         /  \  
     40          ======>     [20]         ========>         30   100
    /            1. Zig-Zig    \          2. Zig-Zig         \     \
   30               at 40       30            at 100         40    200  
  /                               \     
[20]                              40

Важно отметить, что операция поиска или воспроизведения не только возвращает искомый ключ в корневой каталог, но и уравновешивает BST. Например, в приведенном выше случае высота BST уменьшается на 1.

Реализация:

C ++

#include <bits/stdc++.h>

using namespace std;

  
// Узел дерева AVL

class node 

    public:

    int key; 

    node *left, *right; 

}; 

  
/ * Вспомогательная функция, которая выделяет
новый узел с данным ключом и

    NULL левый и правый указатели. * /

node* newNode(int key) 

    node* Node = new node();

    Node->key = key; 

    Node->left = Node->right = NULL; 

    return (Node); 

  
// Функция полезности справа
// вращаем поддерево с корнем у
// Смотрите диаграмму, приведенную выше.
node *rightRotate(node *x) 

    node *y = x->left; 

    x->left = y->right; 

    y->right = x; 

    return y; 

  
// Служебная функция слева
// вращаем поддерево с корнем x
// Смотрите диаграмму, приведенную выше.
node *leftRotate(node *x) 

    node *y = x->right; 

    x->right = y->left; 

    y->left = x; 

    return y; 

  
// Эта функция возвращает ключ в
// корень, если ключ присутствует в дереве.
// Если ключа нет, то это
// возвращает последний доступный элемент в
// корень. Эта функция изменяет
// дерево и возвращает новый корень

node *splay(node *root, int key) 

    // Базовые случаи: root равен NULL или

    // ключ присутствует в корне

    if (root == NULL || root->key == key) 

        return root; 

  

    // Ключ лежит в левом поддереве

    if (root->key > key) 

    

        // Ключ не в дереве, мы сделали

        if (root->left == NULL) return root; 

  

        // Зиг-Зиг (Слева Слева)

        if (root->left->key > key) 

        

            // Сначала рекурсивно вывести

            // ключ как корень слева-слева

            root->left->left = splay(root->left->left, key); 

  

            // сделать первый поворот для корня,

            // второй поворот выполняется после

            root = rightRotate(root); 

        

        else if (root->left->key < key) // зигзаг (слева направо)

        

            // Сначала рекурсивно вывести

            // ключ как корень слева направо

            root->left->right = splay(root->left->right, key); 

  

            // сделать первый поворот для корня-> влево

            if (root->left->right != NULL) 

                root->left = leftRotate(root->left); 

        

  

        // сделать второй поворот для корня

        return (root->left == NULL)? root: rightRotate(root); 

    

    else // Ключ лежит в правом поддереве

    

        // Ключ не в дереве, мы сделали

        if (root->right == NULL) return root; 

  

        // Заг-Зиг (справа налево)

        if (root->right->key > key) 

        

            // Вывести ключ как корень справа налево

            root->right->left = splay(root->right->left, key); 

  

            // Делаем первый поворот для root-> right

            if (root->right->left != NULL) 

                root->right = rightRotate(root->right); 

        

        else if (root->right->key < key)// Заг-Заг (справа направо)

        

            // Получить ключ от корня

            // вправо-вправо и делаем первый поворот

            root->right->right = splay(root->right->right, key); 

            root = leftRotate(root); 

        

  

        // сделать второй поворот для корня

        return (root->right == NULL)? root: leftRotate(root); 

    

  
// Функция поиска для Splay Tree.
// Обратите внимание, что эта функция возвращает
// новый корень Splay Tree. Если ключ
// присутствует в дереве, затем перемещается в корень.

node *search(node *root, int key) 

    return splay(root, key); 

  
// Утилита для печати
// предзаказ обхода дерева.
// Функция также печатает высоту каждого узла

void preOrder(node *root) 

    if (root != NULL) 

    

        cout<<root->key<<" "

        preOrder(root->left); 

        preOrder(root->right); 

    

  
/ * Код водителя * /

int main() 

    node *root = newNode(100); 

    root->left = newNode(50); 

    root->right = newNode(200); 

    root->left->left = newNode(40); 

    root->left->left->left = newNode(30); 

    root->left->left->left->left = newNode(20); 

  

    root = search(root, 20); 

    cout << "Preorder traversal of the modified Splay tree is \n"

    preOrder(root); 

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

// Код взят из http://goo.gl/SDH9hH
#include<stdio.h>
#include<stdlib.h>

  
// Узел дерева AVL

struct node

{

    int key;

    struct node *left, *right;

};

  
/ * Вспомогательная функция, которая выделяет новый узел с данным ключом и

    NULL левый и правый указатели. * /

struct node* newNode(int key)

{

    struct node* node = (struct node*)malloc(sizeof(struct node));

    node->key   = key;

    node->left  = node->right  = NULL;

    return (node);

}

  
// Полезная функция для правого поворота поддерева с корнем у
// Смотрите диаграмму, приведенную выше.

struct node *rightRotate(struct node *x)

{

    struct node *y = x->left;

    x->left = y->right;

    y->right = x;

    return y;

}

  
// Вспомогательная функция левого поворота поддерева с корнем x
// Смотрите диаграмму, приведенную выше.

struct node *leftRotate(struct node *x)

{

    struct node *y = x->right;

    x->right = y->left;

    y->left = x;

    return y;

}

  
// Эта функция возвращает ключ в корень, если ключ присутствует в дереве.
// Если ключ отсутствует, то он возвращает последний доступный элемент в
// корень. Эта функция модифицирует дерево и возвращает новый корень

struct node *splay(struct node *root, int key)

{

    // Базовые случаи: root равен NULL или ключ присутствует в root

    if (root == NULL || root->key == key)

        return root;

  

    // Ключ лежит в левом поддереве

    if (root->key > key)

    {

        // Ключ не в дереве, мы сделали

        if (root->left == NULL) return root;

  

        // Зиг-Зиг (Слева Слева)

        if (root->left->key > key)

        {

            // Сначала рекурсивно приводим ключ как корень слева направо

            root->left->left = splay(root->left->left, key);

  

            // Делаем первый поворот для корня, второй поворот выполняется после else

            root = rightRotate(root);

        }

        else if (root->left->key < key) // зигзаг (слева направо)

        {

            // Сначала рекурсивно приводим ключ как корень слева направо

            root->left->right = splay(root->left->right, key);

  

            // сделать первый поворот для корня-> влево

            if (root->left->right != NULL)

                root->left = leftRotate(root->left);

        }

  

        // сделать второй поворот для корня

        return (root->left == NULL)? root: rightRotate(root);

    }

    else // Ключ лежит в правом поддереве

    {

        // Ключ не в дереве, мы сделали

        if (root->right == NULL) return root;

  

        // Заг-Зиг (справа налево)

        if (root->right->key > key)

        {

            // Вывести ключ как корень справа налево

            root->right->left = splay(root->right->left, key);

  

            // Делаем первый поворот для root-> right

            if (root->right->left != NULL)

                root->right = rightRotate(root->right);

        }

        else if (root->right->key < key)// Заг-Заг (справа направо)

        {

            // Привести ключ как корень вправо-вправо и сделать первый поворот

            root->right->right = splay(root->right->right, key);

            root = leftRotate(root);

        }

  

        // сделать второй поворот для корня

        return (root->right == NULL)? root: leftRotate(root);

    }

}

  
// Функция поиска для Splay Tree. Обратите внимание, что эта функция
// возвращает новый корень Splay Tree. Если ключ присутствует в дереве
// затем он перемещается в корень.

struct node *search(struct node *root, int key)

{

    return splay(root, key);

}

  
// Полезная функция для печати предзаказа обхода дерева.
// Функция также печатает высоту каждого узла

void preOrder(struct node *root)

{

    if (root != NULL)

    {

        printf("%d ", root->key);

        preOrder(root->left);

        preOrder(root->right);

    }

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

    struct node *root = newNode(100);

    root->left = newNode(50);

    root->right = newNode(200);

    root->left->left = newNode(40);

    root->left->left->left = newNode(30);

    root->left->left->left->left = newNode(20);

  

    root = search(root, 20);

    printf("Preorder traversal of the modified Splay tree is \n");

    preOrder(root);

    return 0;

}

Джава

// Java реализация для вышеуказанного подхода

class GFG

{

  
// Узел дерева AVL

static class node 

  

    int key; 

    node left, right; 

}; 

  
/ * Вспомогательная функция, которая выделяет
новый узел с данным ключом и

    нулевые левый и правый указатели. * /

static node newNode(int key) 

    node Node = new node();

    Node.key = key; 

    Node.left = Node.right = null

    return (Node); 

  
// Функция полезности справа
// вращаем поддерево с корнем у
// Смотрите диаграмму, приведенную выше.

static node rightRotate(node x) 

    node y = x.left; 

    x.left = y.right; 

    y.right = x; 

    return y; 

  
// Служебная функция слева
// вращаем поддерево с корнем x
// Смотрите диаграмму, приведенную выше.

static node leftRotate(node x) 

    node y = x.right; 

    x.right = y.left; 

    y.left = x; 

    return y; 

  
// Эта функция возвращает ключ в
// корень, если ключ присутствует в дереве.
// Если ключа нет, то это
// возвращает последний доступный элемент в
// корень. Эта функция изменяет
// дерево и возвращает новый корень

static node splay(node root, int key) 

    // Базовые случаи: корень нулевой или

    // ключ присутствует в корне

    if (root == null || root.key == key) 

        return root; 

  

    // Ключ лежит в левом поддереве

    if (root.key > key) 

    

        // Ключ не в дереве, мы сделали

        if (root.left == null) return root; 

  

        // Зиг-Зиг (Слева Слева)

        if (root.left.key > key) 

        

            // Сначала рекурсивно вывести

            // ключ как корень слева-слева

            root.left.left = splay(root.left.left, key); 

  

            // сделать первый поворот для корня,

            // второй поворот выполняется после

            root = rightRotate(root); 

        

        else if (root.left.key < key) // зигзаг (слева направо)

        

            // Сначала рекурсивно вывести

            // ключ как корень слева направо

            root.left.right = splay(root.left.right, key); 

  

            // Делаем первый поворот для root.left

            if (root.left.right != null

                root.left = leftRotate(root.left); 

        

  

        // сделать второй поворот для корня

        return (root.left == null) ? 

                              root : rightRotate(root); 

    

    else // Ключ лежит в правом поддереве

    

        // Ключ не в дереве, мы сделали

        if (root.right == null) return root; 

  

        // Заг-Зиг (справа налево)

        if (root.right.key > key) 

        

            // Вывести ключ как корень справа налево

            root.right.left = splay(root.right.left, key); 

  

            // Делаем первый поворот для root.right

            if (root.right.left != null

                root.right = rightRotate(root.right); 

        

        else if (root.right.key < key)// Заг-Заг (справа направо)

        

            // Получить ключ от корня

            // вправо-вправо и делаем первый поворот

            root.right.right = splay(root.right.right, key); 

            root = leftRotate(root); 

        

  

        // сделать второй поворот для корня

        return (root.right == null) ? 

                               root : leftRotate(root); 

    

  
// Функция поиска для Splay Tree.
// Обратите внимание, что эта функция возвращает
// новый корень Splay Tree. Если ключ
// присутствует в дереве, затем перемещается в корень.

static node search(node root, int key) 

    return splay(root, key); 

  
// Утилита для печати
// предзаказ обхода дерева.
// Функция также печатает высоту каждого узла

static void preOrder(node root) 

    if (root != null

    

        System.out.print(root.key + " "); 

        preOrder(root.left); 

        preOrder(root.right); 

    

  
// Код драйвера

public static void main(String[] args) 

    node root = newNode(100); 

    root.left = newNode(50); 

    root.right = newNode(200); 

    root.left.left = newNode(40); 

    root.left.left.left = newNode(30); 

    root.left.left.left.left = newNode(20); 

  

    root = search(root, 20); 

    System.out.print("Preorder traversal of the" +  

                     " modified Splay tree is \n"); 

    preOrder(root); 


  
// Этот код предоставлен 29AjayKumar

C #

// реализация C # для вышеуказанного подхода

using System;

  

class GFG

{

  
// Узел дерева AVL

public class node 

  

    public int key; 

    public node left, right; 

}; 

  
/ * Вспомогательная функция, которая выделяет
новый узел с данным ключом и
нулевые левый и правый указатели. * /

static node newNode(int key) 

    node Node = new node();

    Node.key = key; 

    Node.left = Node.right = null

    return (Node); 

  
// Функция полезности справа
// вращаем поддерево с корнем у
// Смотрите диаграмму, приведенную выше.

static node rightRotate(node x) 

    node y = x.left; 

    x.left = y.right; 

    y.right = x; 

    return y; 

  
// Служебная функция слева
// вращаем поддерево с корнем x
// Смотрите диаграмму, приведенную выше.

static node leftRotate(node x) 

    node y = x.right; 

    x.right = y.left; 

    y.left = x; 

    return y; 

  
// Эта функция возвращает ключ в
// корень, если ключ присутствует в дереве.
// Если ключа нет, то это
// возвращает последний доступный элемент в
// корень. Эта функция изменяет
// дерево и возвращает новый корень

static node splay(node root, int key) 

    // Базовые случаи: корень нулевой или

    // ключ присутствует в корне

    if (root == null || root.key == key) 

        return root; 

  

    // Ключ лежит в левом поддереве

    if (root.key > key) 

    

        // Ключ не в дереве, мы сделали

        if (root.left == null) return root; 

  

        // Зиг-Зиг (Слева Слева)

        if (root.left.key > key) 

        

            // Сначала рекурсивно вывести

            // ключ как корень слева-слева

            root.left.left = splay(root.left.left, key); 

  

            // сделать первый поворот для корня,

            // второй поворот выполняется после

            root = rightRotate(root); 

        

        else if (root.left.key < key) // зигзаг (слева направо)

        

            // Сначала рекурсивно вывести

            // ключ как корень слева направо

            root.left.right = splay(root.left.right, key); 

  

            // Делаем первый поворот для root.left

            if (root.left.right != null

                root.left = leftRotate(root.left); 

        

  

        // сделать второй поворот для корня

        return (root.left == null) ? 

                               root : rightRotate(root); 

    

    else // Ключ лежит в правом поддереве

    

        // Ключ не в дереве, мы сделали

        if (root.right == null) return root; 

  

        // Заг-Зиг (справа налево)

        if (root.right.key > key) 

        

            // Вывести ключ как корень справа налево

            root.right.left = splay(root.right.left, key); 

  

            // Делаем первый поворот для root.right

            if (root.right.left != null

                root.right = rightRotate(root.right); 

        

        else if (root.right.key < key)// Заг-Заг (справа направо)

        

            // Получить ключ от корня

            // вправо-вправо и делаем первый поворот

            root.right.right = splay(root.right.right, key); 

            root = leftRotate(root); 

        

  

        // сделать второй поворот для корня

        return (root.right == null) ? 

                               root : leftRotate(root); 

    

  
// Функция поиска для Splay Tree.
// Обратите внимание, что эта функция возвращает
// новый корень Splay Tree. Если ключ
// присутствует в дереве, затем перемещается в корень.

static node search(node root, int key) 

    return splay(root, key); 

  
// Утилита для печати
// предзаказ обхода дерева.
// Функция также печатает высоту каждого узла

static void preOrder(node root) 

    if (root != null

    

        Console.Write(root.key + " "); 

        preOrder(root.left); 

        preOrder(root.right); 

    

  
// Код драйвера

public static void Main(String[] args) 

    node root = newNode(100); 

    root.left = newNode(50); 

    root.right = newNode(200); 

    root.left.left = newNode(40); 

    root.left.left.left = newNode(30); 

    root.left.left.left.left = newNode(20); 

  

    root = search(root, 20); 

    Console.Write("Preorder traversal of the"

                  " modified Splay tree is \n"); 

    preOrder(root); 


  
// Этот код предоставлен 29AjayKumar


Выход:

Preorder traversal of the modified Splay tree is
20 50 30 40 100 200

Резюме
1) Splay-деревья имеют отличные свойства местности. Часто доступные предметы легко найти. Редкие предметы вне пути.

2) Все операции с Splay Tree занимают в среднем O (Logn) время. Может быть строго показано, что деревья сплайнов выполняются за среднее время O (log n) на одну операцию в любой последовательности операций (при условии, что мы начинаем с пустого дерева)

3) Splay-деревья проще по сравнению с AVL и красно-черными деревьями, так как в каждом узле дерева не требуется никаких дополнительных полей.

4) В отличие от AVL-дерева , Splay-дерево может меняться даже при операциях только для чтения, таких как поиск.

Приложения Splay Trees
Деревья сплайсов стали самой широко используемой базовой структурой данных, изобретенной за последние 30 лет, поскольку они являются самым быстрым типом сбалансированного дерева поиска для многих приложений.
Деревья Splay используются в Windows NT (в виртуальной памяти, сети и коде файловой системы), компиляторе gcc и библиотеке GNU C ++, редакторе строк sed, сетевых маршрутизаторах Fore Systems, самой популярной реализации Unix malloc, загружаемого ядра Linux модули и многое другое программное обеспечение (Источник: http://www.cs.berkeley.edu/~jrs/61b/lec/36 )

Смотрите Splay Tree | Установите 2 (Вставить) для вставки Splay Tree.

Ссылки:
http://www.cs.berkeley.edu/~jrs/61b/lec/36
http://www.cs.cornell.edu/courses/cs3110/2009fa/recitations/rec-splay.html
http://courses.cs.washington.edu/courses/cse326/01au/lectures/SplayTrees.ppt

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Splay Tree | Комплект 1 (Поиск)

0.00 (0%) 0 votes