Splay-деревья

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

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

Наихудшая временная сложность таких операций, как поиск, удаление и вставка, для двоичного дерева поиска (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 (справа)

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

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

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

Пример:

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

Реализации:

C++

#include <bits/stdc++.h> using namespace std; // An AVL tree node class node { public: int key; node *left, *right; }; /* Helper function that allocates a new node with the given key and NULL left and right pointers. */node* newNode(int key) { node* Node = new node(); Node->key = key; Node->left = Node->right = NULL; return (Node); } // A utility function to right // rotate subtree rooted with y // See the diagram given above. node *rightRotate(node *x) { node *y = x->left; x->left = y->right; y->right = x; return y; } // A utility function to left // rotate subtree rooted with x // See the diagram given above. node *leftRotate(node *x) { node *y = x->right; x->right = y->left; y->left = x; return y; } // This function brings the key at // root if key is present in tree. // If key is not present, then it // brings the last accessed item at // root. This function modifies the // tree and returns the new root node *splay(node *root, int key) { // Base cases: root is NULL or // key is present at root if (root == NULL || root->key == key) return root; // Key lies in left subtree if (root->key > key) { // Key is not in tree, we are done if (root->left == NULL) return root; // Zig-Zig (Left Left) if (root->left->key > key) { // First recursively bring the // key as root of left-left root->left->left = splay(root->left->left, key); // Do first rotation for root, // second rotation is done after else root = rightRotate(root); } else if (root->left->key < key) // Zig-Zag (Left Right) { // First recursively bring // the key as root of left-right root->left->right = splay(root->left->right, key); // Do first rotation for root->left if (root->left->right != NULL) root->left = leftRotate(root->left); } // Do second rotation for root return (root->left == NULL)? root: rightRotate(root); } else // Key lies in right subtree { // Key is not in tree, we are done if (root->right == NULL) return root; // Zag-Zig (Right Left) if (root->right->key > key) { // Bring the key as root of right-left root->right->left = splay(root->right->left, key); // Do first rotation for root->right if (root->right->left != NULL) root->right = rightRotate(root->right); } else if (root->right->key < key)// Zag-Zag (Right Right) { // Bring the key as root of // right-right and do first rotation root->right->right = splay(root->right->right, key); root = leftRotate(root); } // Do second rotation for root return (root->right == NULL)? root: leftRotate(root); } } // The search function for Splay tree. // Note that this function returns the // new root of Splay Tree. If key is // present in tree then, it is moved to root. node *search(node *root, int key) { return splay(root, key); } // A utility function to print // preorder traversal of the tree. // The function also prints height of every node void preOrder(node *root) { if (root != NULL) { cout<<root->key<<" "; preOrder(root->left); preOrder(root->right); } } /* Driver code*/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; } // This code is contributed by rathbhupendra 

C

// The code is adopted from http://goo.gl/SDH9hH #include<stdio.h> #include<stdlib.h> // An AVL tree node struct node { int key; struct node *left, *right; }; /* Helper function that allocates a new node with the given key and NULL left and right pointers. */struct node* newNode(int key) { struct node* node = (struct node*)malloc(sizeof(struct node)); node->key = key; node->left = node->right = NULL; return (node); } // A utility function to right rotate subtree rooted with y // See the diagram given above. struct node *rightRotate(struct node *x) { struct node *y = x->left; x->left = y->right; y->right = x; return y; } // A utility function to left rotate subtree rooted with x // See the diagram given above. struct node *leftRotate(struct node *x) { struct node *y = x->right; x->right = y->left; y->left = x; return y; } // This function brings the key at root if key is present in tree. // If key is not present, then it brings the last accessed item at // root. This function modifies the tree and returns the new root struct node *splay(struct node *root, int key) { // Base cases: root is NULL or key is present at root if (root == NULL || root->key == key) return root; // Key lies in left subtree if (root->key > key) { // Key is not in tree, we are done if (root->left == NULL) return root; // Zig-Zig (Left Left) if (root->left->key > key) { // First recursively bring the key as root of left-left root->left->left = splay(root->left->left, key); // Do first rotation for root, second rotation is done after else root = rightRotate(root); } else if (root->left->key < key) // Zig-Zag (Left Right) { // First recursively bring the key as root of left-right root->left->right = splay(root->left->right, key); // Do first rotation for root->left if (root->left->right != NULL) root->left = leftRotate(root->left); } // Do second rotation for root return (root->left == NULL)? root: rightRotate(root); } else // Key lies in right subtree { // Key is not in tree, we are done if (root->right == NULL) return root; // Zag-Zig (Right Left) if (root->right->key > key) { // Bring the key as root of right-left root->right->left = splay(root->right->left, key); // Do first rotation for root->right if (root->right->left != NULL) root->right = rightRotate(root->right); } else if (root->right->key < key)// Zag-Zag (Right Right) { // Bring the key as root of right-right and do first rotation root->right->right = splay(root->right->right, key); root = leftRotate(root); } // Do second rotation for root return (root->right == NULL)? root: leftRotate(root); } } // The search function for Splay tree. Note that this function // returns the new root of Splay Tree. If key is present in tree // then, it is moved to root. struct node *search(struct node *root, int key) { return splay(root, key); } // A utility function to print preorder traversal of the tree. // The function also prints height of every node void preOrder(struct node *root) { if (root != NULL) { printf("%d ", root->key); preOrder(root->left); preOrder(root->right); } } /* Driver program to test above function*/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 class GFG { // An AVL tree node static class node { int key; node left, right; }; /* Helper function that allocates a new node with the given key and null left and right pointers. */static node newNode(int key) { node Node = new node(); Node.key = key; Node.left = Node.right = null; return (Node); } // A utility function to right // rotate subtree rooted with y // See the diagram given above. static node rightRotate(node x) { node y = x.left; x.left = y.right; y.right = x; return y; } // A utility function to left // rotate subtree rooted with x // See the diagram given above. static node leftRotate(node x) { node y = x.right; x.right = y.left; y.left = x; return y; } // This function brings the key at // root if key is present in tree. // If key is not present, then it // brings the last accessed item at // root. This function modifies the // tree and returns the new root static node splay(node root, int key) { // Base cases: root is null or // key is present at root if (root == null || root.key == key) return root; // Key lies in left subtree if (root.key > key) { // Key is not in tree, we are done if (root.left == null) return root; // Zig-Zig (Left Left) if (root.left.key > key) { // First recursively bring the // key as root of left-left root.left.left = splay(root.left.left, key); // Do first rotation for root, // second rotation is done after else root = rightRotate(root); } else if (root.left.key < key) // Zig-Zag (Left Right) { // First recursively bring // the key as root of left-right root.left.right = splay(root.left.right, key); // Do first rotation for root.left if (root.left.right != null) root.left = leftRotate(root.left); } // Do second rotation for root return (root.left == null) ? root : rightRotate(root); } else // Key lies in right subtree { // Key is not in tree, we are done if (root.right == null) return root; // Zag-Zig (Right Left) if (root.right.key > key) { // Bring the key as root of right-left root.right.left = splay(root.right.left, key); // Do first rotation for root.right if (root.right.left != null) root.right = rightRotate(root.right); } else if (root.right.key < key)// Zag-Zag (Right Right) { // Bring the key as root of // right-right and do first rotation root.right.right = splay(root.right.right, key); root = leftRotate(root); } // Do second rotation for root return (root.right == null) ? root : leftRotate(root); } } // The search function for Splay tree. // Note that this function returns the // new root of Splay Tree. If key is // present in tree then, it is moved to root. static node search(node root, int key) { return splay(root, key); } // A utility function to print // preorder traversal of the tree. // The function also prints height of every node static void preOrder(node root) { if (root != null) { System.out.print(root.key + " "); preOrder(root.left); preOrder(root.right); } } // Driver code 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); } } // This code is contributed by 29AjayKumar 

C#

// C# implementation for above approach using System; class GFG { // An AVL tree node public class node { public int key; public node left, right; }; /* Helper function that allocates a new node with the given key and null left and right pointers. */static node newNode(int key) { node Node = new node(); Node.key = key; Node.left = Node.right = null; return (Node); } // A utility function to right // rotate subtree rooted with y // See the diagram given above. static node rightRotate(node x) { node y = x.left; x.left = y.right; y.right = x; return y; } // A utility function to left // rotate subtree rooted with x // See the diagram given above. static node leftRotate(node x) { node y = x.right; x.right = y.left; y.left = x; return y; } // This function brings the key at // root if key is present in tree. // If key is not present, then it // brings the last accessed item at // root. This function modifies the // tree and returns the new root static node splay(node root, int key) { // Base cases: root is null or // key is present at root if (root == null || root.key == key) return root; // Key lies in left subtree if (root.key > key) { // Key is not in tree, we are done if (root.left == null) return root; // Zig-Zig (Left Left) if (root.left.key > key) { // First recursively bring the // key as root of left-left root.left.left = splay(root.left.left, key); // Do first rotation for root, // second rotation is done after else root = rightRotate(root); } else if (root.left.key < key) // Zig-Zag (Left Right) { // First recursively bring // the key as root of left-right root.left.right = splay(root.left.right, key); // Do first rotation for root.left if (root.left.right != null) root.left = leftRotate(root.left); } // Do second rotation for root return (root.left == null) ? root : rightRotate(root); } else // Key lies in right subtree { // Key is not in tree, we are done if (root.right == null) return root; // Zag-Zig (Right Left) if (root.right.key > key) { // Bring the key as root of right-left root.right.left = splay(root.right.left, key); // Do first rotation for root.right if (root.right.left != null) root.right = rightRotate(root.right); } else if (root.right.key < key)// Zag-Zag (Right Right) { // Bring the key as root of // right-right and do first rotation root.right.right = splay(root.right.right, key); root = leftRotate(root); } // Do second rotation for root return (root.right == null) ? root : leftRotate(root); } } // The search function for Splay tree. // Note that this function returns the // new root of Splay Tree. If key is // present in tree then, it is moved to root. static node search(node root, int key) { return splay(root, key); } // A utility function to print // preorder traversal of the tree. // The function also prints height of every node static void preOrder(node root) { if (root != null) { Console.Write(root.key + " "); preOrder(root.left); preOrder(root.right); } } // Driver code 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); } } // This code is contributed by 29AjayKumar 

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

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.

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

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

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

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

Перед прочтением этой статьи настоятельно рекомендуется ознакомиться с первой частью: 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 is25 20 50 30 40 100 200

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

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