Привет, хабровчане. В преддверии старта курса «Алгоритмы и структуры данных» приглашаем будущих студентов и всех желающих на открытый урок по теме «Заповедники двоичных деревьев поиска».
Также делимся традиционным полезным переводом.
Перед прочтением этой статьи настоятельно рекомендуется ознакомиться с первой частью: 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Узнать подробнее о курсе «Алгоритмы и структуры данных».
Зарегистрироваться на открытый урок «Заповедники двоичных деревьев поиска».