Привет, Хабр! Будущих студентов курса "Алгоритмы и структуры данных" приглашаем на открытый вебинар по теме "Заповедники двоичных деревьев поиска."
А сейчас делимся с вами традиционным переводом полезного материала.
Наихудшая временная сложность таких операций, как поиск, удаление и вставка, для двоичного дерева поиска (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);
}
}
// Код любезно предоставлен 29AjayKumarC#
// Реализация подхода, приведенного выше, на 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.
Кстати, о "красивой упаковке" онлайн-сертификатов мы рассказываем в этой статье.
