Как стать автором
Обновить
828.09
OTUS
Цифровые навыки от ведущих экспертов

Splay-дерево. Поиск

Время на прочтение 13 мин
Количество просмотров 9.1K
Автор оригинала: www.geeksforgeeks.org

Привет, Хабр! Будущих студентов курса "Алгоритмы и структуры данных" приглашаем на открытый вебинар по теме "Заповедники двоичных деревьев поиска."

А сейчас делимся с вами традиционным переводом полезного материала.


Наихудшая временная сложность таких операций, как поиск, удаление и вставка, для двоичного дерева поиска (Binary Search Tree) составляет O(n). Наихудший случай случай возникает, когда дерево несбалансировано. Мы можем улучшить наихудший результат временной сложности до O(log n) с помощью красно-черных и АВЛ-деревьев.

Можем ли мы добиться на практике лучшего результата, чем тот, что нам дают красно-черные или АВЛ-деревья?

Подобно красно-черным и АВЛ-деревьям, Splay-дерево (или косое дерево) также является самобалансирующимся бинарным деревом поиска. Основная идея splay-дерева состоит в том, чтобы помещать элемент, к которому недавно осуществлялся доступ, в корень дерева, что делает этот элемент, доступным за время порядка O(1) при повторном доступе. Вся суть заключается в том, чтобы использовать концепцию локальности ссылок (в среднестатистическом приложении 80% обращений приходятся на 20% элементов). Представьте себе ситуацию, когда у нас есть миллионы или даже миллиарды ключей, и лишь к некоторым из них обращаются регулярно, что весьма вероятно для многих типичных приложениях.

Все операции со splay-деревом выполняются в среднем за время порядка O(log n), где n - количество элементов в дереве. Любая отдельная операция в худшем случае может занять время порядка Тэта(n).

Операция поиска 

Операция поиска в splay-дереве представляет собой стандартный алгоритм поиска в бинарном дереве, после которого дерево выворачивается (искомый узел перемещается в корень — операция splay). Если поиск завершился успехом, то найденный узел поднимается наверх и становится новым корнем. В противном случае корнем становится последний узел, к которому был осуществлен доступ до достижения NULL.

В результате осуществления доступа к узлу возможны следующие случаи:

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

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

T1, T2 и T3 — поддеревья дерева с корнем y (слева) или x (справа)

               y                                       x
              / \      Zig (Правый разворот)          /  \
              x   T3   – - – - – - – - - ->          T1   y 
             / \       < - - - - - - - - -               / \
            T1  T2     Zag (Левый разворот)            T2   T3

3. У узла есть и родитель, и прародитель. Возможны следующие варианты:

а) Zig-Zig и Zag-Zag. Узел является левым потомком родительского элемента, и родитель также является левым потомком прародителя (два разворота вправо) ИЛИ узел является правым потомком своего родительского элемента, и родитель также является правым потомком своего прародитель (два разворота влево).

Zig-Zig (Левый-левый случай):
       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 (Правый-правый случай):
  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

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

Zag-Zig (Левый-правый случай):
       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 (Правый-левый случай):
  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

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

Реализации:

C++

#include <bits/stdc++.h>
using namespace std;
  
// Узел АВЛ-дерева 
class node 
{ 
    public:
    int key; 
    node *left, *right; 
}; 
  
/* Вспомогательная функция, которая выделяет 
новый узел с заданным key и left и right, указывающими в NULL. */
node* newNode(int key) 
{ 
    node* Node = new node();
    Node->key = key; 
    Node->left = Node->right = NULL; 
    return (Node); 
} 
  
// Служебная функция для разворота поддерева с корнем y вправо.
// Смотрите диаграмму, приведенную выше.
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; 
} 
// Эта функция поднимет ключ
// в корень, если он присутствует в дереве. 
// Если такой ключ отсутствует в дереве, она
// поднимет в корень самый последний элемент,
// к которому был осуществлен доступ.
// Эта функция изменяет дерево
// и возвращает новый корень (root). 
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; 
  
        // Zig-Zig (Левый-левый) 
        if (root->left->key > key) 
        { 
            // Сначала рекурсивно поднимем
            // ключ как корень left-left
            root->left->left = splay(root->left->left, key); 
  
            // Первый разворот для root, 
            // второй разворот выполняется после else
            root = rightRotate(root); 
        } 
        else if (root->left->key < key) // Zig-Zag (Левый-правый) 
        { 
            // Сначала рекурсивно поднимаем
            // ключ как корень left-right
            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; 
  
        // Zag-Zig (Правый-левый) 
        if (root->right->key > key) 
        { 
            // Поднять ключ как корень right-left 
            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)// Zag-Zag (Правый-правый) 
        { 
            // Поднимаем ключ как корень 
            // right-right и выполняем первый разворот
            root->right->right = splay(root->right->right, key); 
            root = leftRotate(root); 
        } 
  
        // Выполняем второй разворот для root
        return (root->right == NULL)? root: leftRotate(root); 
    } 
} 
  
// Функция поиска для splay-дерева. 
// Обратите внимание, что эта функция возвращает 
// новый корень splay-дерева. Если ключ 
// присутствует в дереве, он перемещается в корень.
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

C

 
// Код позаимствован c http://goo.gl/SDH9hH
#include<stdio.h>
#include<stdlib.h>
  
// Узел АВЛ-дерева 
struct node
{
    int key;
    struct node *left, *right;
};
  
/* Вспомогательная функция, которая создает 
новый узел с заданным key и 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);
}
  
// Служебная функция для разворота поддерева с корнем y вправо.
// Смотрите диаграмму, приведенную выше.
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)
{
    // Базовые случаи: корень равен NULL или
    // ключ находится в корне
    if (root == NULL || root->key == key)
        return root;
  
    // Ключ лежит в левом поддереве
    if (root->key > key)
    {
        // Ключа нет в дереве, мы закончили
        if (root->left == NULL) return root;
  
        // Zig-Zig (Левый-левый)
        if (root->left->key > key)
        {
            // Сначала рекурсивно поднимем
            // ключ как корень left-left
            root->left->left = splay(root->left->left, key);
  
            // Первый разворот для корня, 
            // второй разворот выполняется после else
            root = rightRotate(root);
        }
        else if (root->left->key < key) // Zig-Zag (Left Right)
        {
            // Сначала рекурсивно поднимаем
            // ключ как корень left-right
            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;
  
        // Zag-Zig (Правый-левый)
        if (root->right->key > key)
        {
            //Поднимаем ключ вверх в качестве корня right-left
            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)// Zag-Zag (Правый-правый)
        {
            // Поднимаем ключ как корень 
            // right-right и выполняем первый разворот
            root->right->right = splay(root->right->right, key);
            root = leftRotate(root);
        }
  
        //Выполняем второй разворот для корня
        return (root->right == NULL)? root: leftRotate(root);
    }
}
  
// Функция поиска для splay-дерева. 
// Обратите внимание, что эта функция возвращает 
// новый корень splay-дерева. Если ключ 
// присутствует в дереве, он перемещается в корень.
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

// Java implementation for above approach
// Реализация подхода, приведенного выше, на Java
class GFG
{
  
// Узел АВЛ-дерева 
static class node 
{ 
  
    int key; 
    node left, right; 
}; 
  
/ * Вспомогательная функция, которая выделяет 
новый узел с заданным key и left и right, указывающими в NULL. * /
static node newNode(int key) 
{ 
    node Node = new node();
    Node.key = key; 
    Node.left = Node.right = null; 
    return (Node); 
} 
  
// Служебная функция для разворота поддерева с корнем y вправо.
// Смотрите диаграмму, приведенную выше.
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; 
} 
  
// Эта функция поднимет ключ
// в корень, если он присутствует в дереве. 
// Если такой ключ отсутствует в дереве, она
// поднимет в корень самый последний элемент,
// к которому был осуществлен доступ.
// Эта функция изменяет дерево
// и возвращает новый корень (root).
static 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; 
  
        // Zig-Zig (Левый-левый) 
        if (root.left.key > key) 
        { 
            // Сначала рекурсивно поднимем
            // ключ как корень left-left 
            root.left.left = splay(root.left.left, key); 
  
            // Первый разворот для root, 
            // второй разворот выполняется после else
            root = rightRotate(root); 
        } 
        else if (root.left.key < key) // Zig-Zag (Left Right) 
        { 
            // Сначала рекурсивно поднимаем
            // ключ как корень left-right 
            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; 
  
        // Zag-Zig (Правый-левый) 
        if (root.right.key > key) 
        { 
            //Поднять ключ как корень right-left
            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)// Zag-Zag (Правый-правый) 
        { 
            // Поднимаем ключ как корень 
            // right-right и выполняем первый разворот
            root.right.right = splay(root.right.right, key); 
            root = leftRotate(root); 
        } 
  
        //Выполняем второй разворот для root 
        return (root.right == null) ? 
                               root : leftRotate(root); 
    } 
} 
  
// Функция поиска для splay-дерева. 
// Обратите внимание, что эта функция возвращает 
// новый корень splay-дерева. Если ключ 
// присутствует в дереве, он перемещается в корень.
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
{
  
// Узел АВЛ-дерева 
public class node 
{ 
  
    public int key; 
    public node left, right; 
}; 
  
/* Вспомогательная функция, которая выделяет 
новый узел с заданным key и left и right, указывающими в NULL. */
static node newNode(int key) 
{ 
    node Node = new node();
    Node.key = key; 
    Node.left = Node.right = null; 
    return (Node); 
} 
  
// Служебная функция для разворота поддерева с корнем y вправо.
// Смотрите диаграмму, приведенную выше.
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; 
} 
  
// Эта функция поднимет ключ
// в корень, если он присутствует в дереве. 
// Если такой ключ отсутствует в дереве, она
// поднимет в корень самый последний элемент,
// к которому был осуществлен доступ.
// Эта функция изменяет дерево
// и возвращает новый корень (root).
static 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; 
  
        // Zig-Zig (Левый-левый) 
        if (root.left.key > key) 
        { 
            // Сначала рекурсивно поднимем
            // ключ как корень left-left
            root.left.left = splay(root.left.left, key); 
  
            // Первый разворот для root, 
            // второй разворот выполняется после else 
            root = rightRotate(root); 
        } 
        else if (root.left.key < key) // Zig-Zag (Левый-правый) 
        { 
            // Сначала рекурсивно поднимаем
            // ключ как корень left-right
  
            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; 
  
        // Zag-Zig (Правый-левый) 
        if (root.right.key > key) 
        { 
            //Поднять ключ как корень right-left
            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)// Zag-Zag (Правый-правый) 
        { 
            // Поднимаем ключ как корень 
            // right-right и выполняем первый разворот
            root.right.right = splay(root.right.right, key); 
            root = leftRotate(root); 
        } 
  
        // Выполняем второй разворот для root
        return (root.right == null) ? 
                               root : leftRotate(root); 
    } 
} 
  
// Функция поиска для splay-дерева. 
// Обратите внимание, что эта функция возвращает 
// новый корень splay-дерева. Если ключ 
// присутствует в дереве, он перемещается в корень.
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.Splay

Выходные данные:

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

Резюме

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

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

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

4) В отличие от АВЛ-дерева, splay-дерево может изменяться даже при выполнении операций чтения, таких как поиск.

Применение Splay-деревьев

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

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

Смотрите также Splay Tree | Set 2 (Insert).

Ссылки:

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


Узнать подробнее о курсе "Алгоритмы и структуры данных".

Записаться на открытый вебинар по теме "Заповедники двоичных деревьев поиска."

Реклама которая может быть полезна

Прямо сейчас в OTUS действуют максимальные новогодние скидки на все курсы. Ознакомиться с полным списком курсов вы можете по ссылке ниже. Также у всех желающих есть уникальная возможность отправить адресату подарочный сертификат на обучение в OTUS.

Кстати, о "красивой упаковке" онлайн-сертификатов мы рассказываем в этой статье.

ЗАБРАТЬ СКИДКУ

Теги:
Хабы:
+9
Комментарии 2
Комментарии Комментарии 2

Публикации

Информация

Сайт
otus.ru
Дата регистрации
Дата основания
Численность
101–200 человек
Местоположение
Россия
Представитель
OTUS