Splay-дерево. Вставка

Перед прочтением этой статьи настоятельно рекомендуется ознакомиться с первой частью: 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  ";      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  ");     preOrder(root);     return 0; }

Вывод:

Preorder traversal of the modified Splay tree is  25 20 50 30 40 100 200

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



		Splay-дерево. Вставка
МЕНЮ Главная страница Поиск Регистрация на сайте Помощь проекту Архив новостей ТЕМЫ Новости ИИ Голосовой помощник Городские сумасшедшие ИИ в медицине ИИ проекты Искусственные нейросети Искусственный интеллект Слежка за людьми Угроза ИИ Разработка ИИ ИИ теория Компьютерные науки Машинное обуч. (Ошибки) Машинное обучение Машинный перевод Нейронные сети начинающим Психология ИИ Реализация ИИ Реализация нейросетей Создание беспилотных авто Трезво про ИИ Философия ИИ Внедрение ИИ Big data Генетические алгоритмы Капсульные нейросети Основы нейронных сетей Распознавание лиц Распознавание образов Распознавание речи Творчество ИИ Техническое зрение Чат-боты Работа разума и сознание Изучение сна Изучение сознания Нейроинтерфейс Психология Работа мозга Работа памяти Работа разума Модель мозга Модель мозга Робототехника, БПЛА Беспилотные автомобили БПЛА Робототехника Трансгуманизм Трансгуманизм Обработка текста Анализ социальных сетей Компьютерная лингвистика Лингвистика Поисковые алгоритмы Теория эволюции Головной мозг Нейронные сети Поведение животных Теория эволюции Дополненная реальность Виртулаьная реальность Дополненная реальность Железо Интернет вещей Квантовый компьютер Нейронные процессоры облачные вычисления Суперкомпьютеры Киберугрозы Кибербезопасность Научный мир Методы исследования Наука и образование Семинары ИТ индустрия ИТ-гиганты Новости ит Разработка ПО Разработка ПО Теория алгоритмов Теория информации Кластеризация Математика Актуальная математика Статистика Теория вероятности Теория информации Теория хаоса Цифровая экономика Технология блокчейн Цифровая экономика Авторизация RSS RSS новости		2021-04-06 10:00 Теория алгоритмов *Перед прочтением этой статьи настоятельно рекомендуется ознакомиться с первой частью:* *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 "; 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 "); preOrder(root); return 0; } Вывод: `Preorder traversal of the modified Splay tree is 25 20 50 30 40 100 200` Узнать подробнее о курсе «Алгоритмы и структуры данных».Зарегистрироваться на открытый урок «Заповедники двоичных деревьев поиска». Источник: habr.com Комментарии:

Splay-дерево. Вставка

Комментарии: