Привет, хабровчане. В преддверии старта курса «Алгоритмы и структуры данных» приглашаем будущих студентов и всех желающих на открытый урок по теме «Заповедники двоичных деревьев поиска».
Также делимся традиционным полезным переводом.
Перед прочтением этой статьи настоятельно рекомендуется ознакомиться с первой частью: 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 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Узнать подробнее о курсе «Алгоритмы и структуры данных».
Зарегистрироваться на открытый урок «Заповедники двоичных деревьев поиска».
VK объявляет о приобретении 40% компании Intickets.ru (Интикетс). Это облачный сервис для контроля и управления продажей билетов на мероприятия. Сумма…
OpenAI готовится запустить собственную поисковую систему на базе ChatGPT. Информацию об этом публикуют западные издания. Ожидается, что новый поисковик может…
Центр управления связью общего пользования (ЦМУ ССОП) Роскомнадзора рекомендовал компаниям из реестра провайдеров ограничить доступ поисковых ботов к информации на российских сайтах.…
Apple возобновила переговоры с OpenAI о возможности внедрения ИИ-технологий в iOS 18, на основе данной операционной системы будут работать новые…
Конкурсный управляющий российской «дочки» Google подготовил 23 иска к участникам рекламного рынка. Общая сумма исков составляет 16 млрд рублей –…
Google завершил обновление основного алгоритма March 2024 Core Update. Раскатка обновлений была завершена 19 апреля, но сообщил об этом поисковик…