Привет, хабровчане. В преддверии старта курса «Алгоритмы и структуры данных» приглашаем будущих студентов и всех желающих на открытый урок по теме «Заповедники двоичных деревьев поиска».

Также делимся традиционным полезным переводом.


Перед прочтением этой статьи настоятельно рекомендуется ознакомиться с первой частью: Splay-дерево. Поиск

Как упоминалось в предыдущей статье, Splay-дерево — это самобалансирующаяся структура данных, в которой последний ключ, к которому осуществлялся доступ, всегда помещается в корень. Операция вставки аналогична вставке в бинарное дерево поиска с несколькими дополнительными шагами, цель которых убедиться, что вновь вставленный ключ становится новым корнем.

Ниже приведены различные случаи при вставке ключа k в Splay-дерево.

1) Корень равен NULL: мы просто создаем новый узел и возвращаем его как корневой.

2) Выполняем операцию Splay над заданный ключом k. Если k уже присутствует, он становится новым корнем. Если он отсутствует, то новым корневым узлом становится последний узел-лист, к которому был осуществлен доступ.

3) Если новый корневой ключ такой же, как k, ничего не делаем, поскольку k уже существует.

4) В противном случае выделяем память для нового узла и сравниваем корневой ключ с k.

4.a) Если k меньше корневого ключа, делаем корень правым дочерним элементом нового узла, копируем левый дочерний элемент корня в качестве левого дочернего элемента нового узла и делаем левый дочерний элемент корня равным NULL.

4.b) Если k больше корневого ключа, делаем корень левым дочерним элементом нового узла, копируем правый дочерний элемент корня в качестве правого дочернего элемента нового узла и делаем правый дочерний элемента корня равным NULL.

5) Возвращаем новый узел в качестве нового корня дерева.

Пример:


          100                  [20]                             25     
          /  \                   \                             /          50   200                  50                          20   50 
       /          insert(25)     /  \        insert(25)           /  \  
      40          ======>      30   100      ========>           30  100    
     /          1. Splay(25)    \     \      2. insert 25         \        30                          40    200                         40   200   
   /                                                          
 [20] 

С++

#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) 
        { 
            // Сначала рекурсивно поднимаем
             // ключ в качестве кореня 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); 
    } 
} 
  
// Функция для вставки нового ключа k в splay-дерево с заданным корнем
node *insert(node *root, int k) 
{ 
    // Простой случай: если дерево пусто
    if (root == NULL) return newNode(k); 
  
    // Делаем ближайший узел-лист корнем 
    root = splay(root, k); 
  
    // Если ключ уже существует, то возвращаем его
    if (root->key == k) return root; 
  
    // В противном случае выделяем память под новый узел
    node *newnode = newNode(k); 
  
    // Если корневой ключ больше, делаем корень правым дочерним элементом нового узла, копируем левый дочерний элемент корня в качестве левого дочернего элемента нового узла
    if (root->key > k) 
    { 
        newnode->right = root; 
        newnode->left = root->left; 
        root->left = NULL; 
    } 
  
    // Если корневой ключ меньше, делаем корень левым дочерним элементом нового узла, копируем правый дочерний элемент корня в качестве правого дочернего элемента нового узла
    else
    { 
        newnode->left = root; 
        newnode->right = root->right; 
        root->right = NULL; 
    } 
  
    return newnode; // новый узел становится новым корнем
} 
  
// Служебная функция для вывода 
// обхода в дерева ширину. 
// Функция также выводит высоту каждого узла
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 = insert(root, 25); 
    cout<<"Preorder traversal of the modified Splay tree is \n"; 
    preOrder(root); 
    return 0; 
} 
  
// Этот код любезно предоставлен rathbhupendra

C

// Код позаимствован c http://algs4.cs.princeton.edu/33balanced/SplayBST.java.html
#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
            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);
    }
}
  
// Функция для вставки нового ключа k в splay-дерево с заданным корнем
struct node *insert(struct node *root, int k)
{
    // Простой случай: если дерево пусто
    if (root == NULL) return newNode(k);
  
    // Делаем ближайший узел-лист корнем
    root = splay(root, k);
  
    // Если ключ уже существует, то возвращаем его
    if (root->key == k) return root;
  
    // В противном случае выделяем память под новый узел
    struct node *newnode  = newNode(k);
  
    // Если корневой ключ больше, делаем корень правым дочерним элементом нового узла, копируем левый дочерний элемент корня в качестве левого дочернего элемента нового узла
    if (root->key > k)
    {
        newnode->right = root;
        newnode->left = root->left;
        root->left = NULL;
    }
  
    // Если корневой ключ меньше, делаем корень левым дочерним элементом нового узла, копируем правый дочерний элемент корня в качестве правого дочернего элемента нового узла
    else
    {
        newnode->left = root;
        newnode->right = root->right;
        root->right = NULL;
    }
  
    return newnode; // новый узел становится новым корнем
}
  
// Служебная функция для вывода 
// обхода в дерева ширину. 
// Функция также выводит высоту каждого узла
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 = insert(root, 25);
    printf("Preorder traversal of the modified Splay tree is \n");
    preOrder(root);
    return 0;
}

Вывод:

Preorder traversal of the modified Splay tree is

25 20 50 30 40 100 200


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

Зарегистрироваться на открытый урок «Заповедники двоичных деревьев поиска».